10.2 Linked lists

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

STACK-EMPTY(L)
    if L.head == NIL
        return true
    else return false

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

PUSH(L, x)
    x.next = L.head
    L.head = x

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

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.

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

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.

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

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

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

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

LIST-REVERSE(L)
    tmp = L.head
    L.head = L.tail
    L.tail = tmp