Wed 30 Nov 2005
Posted by pete under Uncategorized
Comments Off on Dual-Linked List with One Pointer Field
Normally, a dual-linked circular list would contain both previous and next pointer fields and the current position in the list would be identified by a single pointer. By using two current pointers, one to the node in question and the other to the one just before/after it, it becomes possible to store only a single pointer value in each node. The value stored in each node is the XOR of the next and previous pointers that normally would have been stored in each node. Decoding is obvious.
Unfortunately, using this trick in C is awkward because the XOR operation is not defined for pointers.
No Responses to “ Dual-Linked List with One Pointer Field ”
Sorry, comments for this entry are closed at this time.