## 10.2-1

Can you implement the dynamic-set 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.

LIST-INSERT(L, x)

• $\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.2-2

Implement a stack using a singly linked list $L$. The operations $\text{PUSH}$ and $\text{POP}$ should still take $O(1)$ time.

STACK-EMPTY(L)
return true
else return false

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

PUSH(L, x)

• $\text{POP}$: removes the first element from the list.

POP(L)
if STACK-EMPTY(L)
error "underflow"
else
return x


## 10.2-3

Implement a queue by a singly linked list $L$. The operations $\text{ENQUEUE}$ and $\text{DEQUEUE}$ should still take $O(1)$ time.

QUEUE-EMPTY(L)
return true
else return false

• $\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.

ENQUEUE(L, x)
if QUEUE-EMPTY(L)
else L.tail.next = x
L.tail = x
x.next = NIL

• $\text{DEQUEUE}$: removes an element from the beginning of the list.

DEQUEUE(L)
if QUEUE-EMPTY(L)
error "underflow"
else
L.tail = NIL
return x


## 10.2-4

As written, each loop iteration in the $\text{LIST-SEARCH}'$ 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.

LIST-SEARCH'(L, k)
x = L.nil.next
L.nil.key = k
while x.key != k
x = x.next
return x


## 10.2-5

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)$.

LIST-INSERT''(L, x)
x.next = L.nil.next
L.nil.next = x

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

LIST-DELETE''(L, x)
prev = L.nil
while prev.next != x
if prev.next == L.nil
error "element not exist"
prev = prev.next
prev.next = x.next

• $\text{SEARCH}$: $O(n)$.

LIST-SEARCH''(L, k)
x = L.nil.next
while x != L.nil and x.key != k
x = x.next
return x


## 10.2-6

The dynamic-set 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.

LIST-UNION(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.2-7

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.

LIST-REVERSE(L)
p[1] = NIL
while p[2] != NIL
p[3] = p[2].next
p[2].next = p[1]
p[1] = p[2]
p[2] = p[3]


## 10.2-8 $\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 "exclusive-or" 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.

LIST-SEARCH(L, k)
prev = NIL
while x != NIL and x.key != k
next = prev XOR x.np
prev = x
x = next
return x

LIST-INSERT(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
L.tail = x

LIST-DELETE(L, x)
prev = NIL
while y != NIL
next = prev XOR y.np
if y != x
prev = y
y = next
else
if prev != NIL
prev.np = (prev.np XOR y) XOR next  // prev.prev XOR next

LIST-REVERSE(L)