For small devices to be cost effective, manufacturers often need to impose restrictions on memory size for the software components. Such situations often require developers to find alternative implementations of data structures. It is well known that a node of a linked list uses a pointer to reference its successor. A doubly linked list, while more flexible, requires two such pointers to reference both the next node and the previous node.

This paper proposes an alternative approach: defining the node structure using only one pointer (the field ptrdiff), a pointer that captures the difference between the pointer to the next node and the pointer to the previous node, shown as follows (with C++ syntax): typedef struct dlistNode { T elm; struct dlistNode *ptrdiff; };.

It is interesting to observe that, if next and previous are two pointers, ptrdiff = nextXOR previous (where XOR refers to a bitwise exclusive OR operator) finds bits where next differs from previous. In this way, the next (or previous) pointer can be recovered by applying XOR between the previous or next pointer and the ptrdiff field. This is the essential idea of the implementation. The details, however, can be left as an interesting student project in a data structures class.

It was shown anecdotally that the memory overhead is about 66 percent for a conventional node, and 50 percent for this alternative approach, which takes up about two-thirds of the total memory requirement for a conventional doubly linked list, while maintaining roughly the same processing time for the primitive operations. Obviously, such savings would be even greater if multidimensional doubly linked lists were used to form a dynamic grid. I would be surprised, however, if similar ideas had not been previously suggested.