10.2 Linked lists
10.21¶
Can you implement the dynamicset operation $\text{INSERT}$ on a singly linked list in $O(1)$ time? How about $\text{DELETE}$?

$\text{INSERT}$: can be implemented in constant time by prepending it to the list.

$\text{DELETE}$: you can copy the value from the successor to element you want to delete, and then you can delete the successor in $O(1)$ time. This solution is not good in situations when you have a large object, in that case copying the whole object will be a bad idea.
10.22¶
Implement a stack using a singly linked list $L$. The operations $\text{PUSH}$ and $\text{POP}$ should still take $O(1)$ time.

$\text{PUSH}$: adds an element in the beginning of the list.

$\text{POP}$: removes the first element from the list.
10.23¶
Implement a queue by a singly linked list $L$. The operations $\text{ENQUEUE}$ and $\text{DEQUEUE}$ should still take $O(1)$ time.

$\text{ENQUEUE}$: inserts an element at the end of the list. In this case we need to keep track of the last element of the list. We can do that with a sentinel.

$\text{DEQUEUE}$: removes an element from the beginning of the list.
10.24¶
As written, each loop iteration in the $\text{LISTSEARCH}'$ procedure requires two tests: one for $x \ne L.nil$ and one for $x.key \ne k$. Show how to eliminate the test for $x \ne L.nil$ in each iteration.
10.25¶
Implement the dictionary operations $\text{INSERT}$, $\text{DELETE}$, and $\text{SEARCH}$ using singly linked, circular lists. What are the running times of your procedures?

$\text{INSERT}$: $O(1)$.

$\text{DELETE}$: $O(n)$.

$\text{SEARCH}$: $O(n)$.
10.26¶
The dynamicset operation $\text{UNION}$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S = S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2$. The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support $\text{UNION}$ in $O(1)$ time using a suitable list data structure.
If both sets are a doubly linked lists, we just point link the last element of the first list to the first element in the second. If the implementation uses sentinels, we need to destroy one of them.
LISTUNION(L[1], L[2])
L[2].nil.next.prev = L[1].nil.prev
L[1].nil.prev.next = L[2].nil.next
L[2].nil.prev.next = L[1].nil
L[1].nil.prev = L[2].nil.prev
10.27¶
Give a $\Theta(n)$time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that needed for the list itself.
LISTREVERSE(L)
p[1] = NIL
p[2] = L.head
while p[2] != NIL
p[3] = p[2].next
p[2].next = p[1]
p[1] = p[2]
p[2] = p[3]
L.head = p[1]
10.28 $\star$¶
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 all pointer values can be interpreted as $k$bit integers, and define $x.np$ to be $x.np = x.next \text{ XOR } x.prev$, the $k$bit "exclusiveor" of $x.next$ and $x.prev$. (The value $\text{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 $\text{SEARCH}$, $\text{INSERT}$, and $\text{DELETE}$ operations on such a list. Also show how to reverse such a list in $O(1)$ time.
LISTSEARCH(L, k)
prev = NIL
x = L.head
while x != NIL and x.key != k
next = prev XOR x.np
prev = x
x = next
return x
LISTINSERT(L, x)
x.np = NIL XOR L.tail
if L.tail != NIL
L.tail.np = (L.tail.np XOR NIL) XOR x // tail.prev XOR x
if L.head == NIL
L.head = x
L.tail = x