Explain how to implement doubly linked lists using only one pointer value \(x.np\) per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as \(k\)-bit integers, and define \(x.np\) to be \(x.np = x.next \oplus x.prev\), the \(k\)-bit “exclusive-or” of \(x.next\) and \(x.prev\). (The value \(NIL\) is represented by 0.) Be sure to describe what information you need to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in \(O(1)\) time.

Suppose we have a node with a previous value and a next value. Since these values can be interpreted as \(k\)-bit integers, we can \(\oplus\) them together to create another \(k\)-bit integer which we can then store in this new \(np\) value. But how to extract the value we need while operating on the list? Consider the following properties of our new \(np\) value:

\[next = prev \oplus np\] \[prev = next \oplus np\]

So we can always unpack the \(np\) value if we know the value of either \(next\) or \(prev\) which we will. As we traverse the list, we are moving from node to node and so when we arrive at the node we will always have the \(prev\) (or \(next\), depending on direction) value in hand and can use it to extract the other value from \(np\). In the event we are just starting and are arriving at either the \(head\) or \(tail\) node without a previous node value in hand then we simply use \(NIL\) because these lists are not circular.

LIST-SEARCH(L, k)

1 prev = NIL

2 x = L.head

3 while x != NIL and x.key != k

4      next = x.np XOR prev

5      prev = x

6      x = next

7 return x

LIST-SEARCH doesn’t change all that much. Line 4 showcases the extraction of a \(next\) value from \(np\) and we need to hold onto an extra value during the procedure to allow for this change.

LIST-INSERT(L, x)

1 x.np = L.head XOR NIL

2 if L.head != NIL

3      L.head.np = (L.head.np XOR NIL) XOR x

4 L.head = x

Similarly, LIST-INSERT just needs minor adjustments to account for our new storage pattern.

LIST-DELETE(L, x)

01 prev = NIL

02 y = L.head

03 while y != NIL:

04      next = y.np XOR prev

05      if y != x:

06          prev = y

07          y = next

08      else:

09          if prev != NIL:

10              prev.np = (prev.np XOR y) XOR next

11          else L.head = next

12          if next != NIL:

13              next.np = (next.np XOR y) XOR prev

14          else L.tail = prev

LIST-DELETE has a lot more going on. We must now traverse the list so that we can decode the node’s \(np\) value properly. If the node that we are removing was either the head or the tail of the list, then we must designate a new head or tail.

LIST-REVERSE(L)

1 x = L.tail

2 L.tail = L.head

3 L.head = x

This one is nifty. Due to the nature of these unique lists, the ‘order’ of the \(prev\) and \(next\) values no longer matter since they are combined together into \(np\). This means our entire list can be reversed simply by swapping the tail and the head of the list! This operation runs in \(O(1)\) time.