10.2 Linked lists

10.2-1

We can implement INSERT in O(1) time, but cannot implement DELETE in O(1) time, it's O(n).

10.2-2

PUSH(S, x)

S.L.insert(x)

POP(S)

if S.L.head == NIL
    error "underflow"
x = S.L.head
S.L.head = S.L.head.next
return x

10.2-3

ENQUEUE(Q, x)

new = SINGLY-LINKED-NODE(x)
if Q.L.head == NIL
    Q.L.head = new
    Q.L.tail = new
else
    Q.L.tail.next = new
    Q.L.tail = new

DEQUEUE(Q)

if Q.L.head == NIL
    error "underflow"
x = Q.L.head
Q.L.head = Q.L.head.next
return x

10.2-4

LIST-SEARCH'(L, k)

x = L.nil.next
L.nil.key = k
while x.key != k
    x = x.next
if x != L.nil
    return x
else
    return NIL

10.2-5

SEARCH(D, k)

x = D.L.search(k)

if x != D.L.nil
    return x
else
    return NIL

INSERT(D, k, v)

x = SEARCH(D, k)

if x != D.L.nil:
    error "The specified key already exists"
else:
    INSERT(D.L, k, v)

DELETE(D, k)

x = SEARCH(D, k)

if x == D.L.nil:
    error "The specified key does not exist"
else:
    DELETE(D.L, k)

The running time of INSERT, DELETE and SEARCH are all O(n).

10.2-6

We can use two singly linked lists to represent s1 and s2. In order to union s1 and s2, we simply let the tail of s1 points to the head of s2, and let the tail of s2 be the tail of s1.

SET-UNION(s1, s2)

s1.tail.next = s2.head
s1.tail = s2.tail

return s1

10.2-7

REVERSE-SINGLY-LINKED-LIST(L)

prev = L.head
current = prev.next if prev != NIL else NIL

while current != NIL
    next = current.next
    current.next = prev
    prev = current
    current = next

L.head.next = NIL
temp = L.head
L.head = L.tail
L.tail = temp

10.2-8

We can use the memory addresses of the pointers as the k-bit integers, so x.np = memory-address(x.next) XOR memory-address(x.pre).

SEARCH(L, k)

node = L.head
prev-pointer = 0

while node != NIL and node.key != k:
    if node == L.tail:
        return NIL

    new-prev-pointer = memory-address(node)
    node = value-at-memory-address(node.np XOR prev-pointer)
    prev-pointer = new-prev-pointer

return node

INSERT(L, k)

new = ONE-POINTER-DOUBLY-LINKED-NODE(key)

if L.head is NIL:
    L.head = new
    L.head.np = 0 XOR 0
    L.tail = new
    L.tail.np = 0 XOR 0
else:
    new.np = memory-address(L.head) XOR 0
    L.head.np = (L.head.np XOR 0) XOR memory-address(new)
    L.head = new

DELETE(L, k)

node = L.head
prev-pointer = 0
prev-node = NIL

while node != NIL and node.key != key:
    if node == L.tail:
        error "The specified key does not exist"

    new-prev-pointer = memory-address(node)
    prev-node = node
    node = value-at-memory-address(node.np XOR prev-pointer)
    prev-pointer = new-prev-pointer

if node == NIL:
    error "The specified key does not exist"

if node == L.head:
    if L.head == L.tail:
        L.head = NIL
        L.tail = NIL
    else:
        next = value-at-memory-address(node.np XOR 0)
        next.np = (next.np XOR memory-address(node)) XOR 0
        L.head = next
else if node == L.tail:
    prev-node.np = (prev-node.np XOR memory-address(node)) XOR 0
    L.tail = prev-node
else:
    next = value-at-memory-address(node.np XOR prev_pointer)
    next.np = (next.np XOR memory-address(node)) XOR prev-pointer
    prev-node.np = (prev-node.np XOR memory-address(node)) XOR memory-address(next)

REVERSE(L)

temp = L.head
L.head = L.tail
L.tail = temp