## 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.

 1 2 3 LIST-INSERT(L, x) x.next = L.head L.head = 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.

 1 2 3 4 STACK-EMPTY(L) if L.head == NIL return true else return false 
• $\text{PUSH}$: adds an element in the beginning of the list.

 1 2 3 PUSH(L, x) x.next = L.head L.head = x 
• $\text{POP}$: removes the first element from the list.

 1 2 3 4 5 6 7 POP(L) if STACK-EMPTY(L) error "underflow" else x = L.head L.head = L.head.next 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.

 1 2 3 4 QUEUE-EMPTY(L) if L.head == NIL 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.

 1 2 3 4 5 6 ENQUEUE(L, x) if QUEUE-EMPTY(L) L.head = x else L.tail.next = x L.tail = x x.next = NIL 
• $\text{DEQUEUE}$: removes an element from the beginning of the list.

 1 2 3 4 5 6 7 8 9 DEQUEUE(L) if QUEUE-EMPTY(L) error "underflow" else x = L.head if L.head == L.tail L.tail = NIL L.head = L.head.next 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.

 1 2 3 4 5 6 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)$.

 1 2 3 LIST-INSERT''(L, x) x.next = L.nil.next L.nil.next = x 
• $\text{DELETE}$: $O(n)$.

 1 2 3 4 5 6 7 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)$.

 1 2 3 4 5 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.

 1 2 3 4 5 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.

 1 2 3 4 5 6 7 8 9 LIST-REVERSE(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.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.

 1 2 3 4 5 6 7 8 LIST-SEARCH(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 
 1 2 3 4 5 6 7 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 if L.head == NIL L.head = x L.tail = x 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LIST-DELETE(L, x) y = L.head 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 else L.head = next if next != NIL next.np = prev XOR (y XOR next.np) // prev XOR next.next else L.tail = prev 
 1 2 3 4 LIST-REVERSE(L) tmp = L.head L.head = L.tail L.tail = tmp