Chapter 10.2

We could implement the dynamic-set operation INSERT by the singly linked list LIST-INSERT operation, to achieve \(O(1)\) running time. But we cannot implement \(O(1)\) running time dynamic-set operation DELETE, because we must first call the LIST-SEARCH to find the element with the given key.

PUSH(L, x)
    nx = new node to carry x
    LIST-INSERT(L, nx)

POP(L)
    if L.head == NIL
        error "the stack underflows"
    x = L.head.data
    LIST-DELETE(L, L.head)
    return x

The singly linked list \(L\) should support \(L.tail\) attribute.

ENQUEUE(L, x)
    nx = new node to carry x
    if L.head == NIL
        LIST-INSERT(L, x)
        L.tail = x
    else L.tail.next = x

DEQUEUE(L)
    if L.head == NIL
        error "the queue underflows"
    x = L.head.data
    LIST-DELETE(L, L.head)
    return x

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

INSERT(L, k, v)
    x = SEARCH(L, k)
    if x == L.nil
        x = new node to carry v with key k
        x.next = L.nil.next
        L.nil.next = x
    else x.data = v

DELETE(L, k)
    x = L.nil
    while x.next != L.nil and x.next.key != k
        x = x.next
    x.next = x.next.next

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

The running times of INSERT, SEARCH and DELETE are \(O(n)\).

We can represent the dynamic set as a doubly linked list, and implement UNION as below.

UNION(S1, S2)
    S1.nil.prev.next = S2.nil.next
    S2.nil.next.prev = S1.nil.prev
    S1.nil.prev = S2.nil.prev
    S2.nil.prev.next = S1.nil
    return S1

REVERSE(L)
    x = L.head
    if x == NIL
        return
    y = x.next
    while y != NIL
        ny = y.next
        y.next = x
        x = y
        y = ny

(implementation)

We need the pointer to the head to access the head of the list.

The implementations of SEARCH, INSERT and DELETE operations are as below.

SEARCH(L, k)
    lx = NIL
    x = L.head
    while x != NIL and x.key != k
        temp = x
        x = x.np ^ lx
        lx = temp
    return x

INSERT(L, x)
    x.np = L.head
    if L.head != NIL
        L.head.np = L.head.np ^ x
    else L.tail = x
    L.head = x

DELETE(L, x)
    ly = NIL
    y = L.head
    while y != NIL and y != x
        temp = y
        y = y.np ^ ly
        ly = temp
    if y != NIL
        ny = ly ^ y.np
        if ly != NIL
            ly.np = ly.np ^ ly ^ y ^ y.np
        else L.head = ny
        if ny != NIL
            ny.np = ny.np ^ ny ^ y ^ y.np
        else L.tail = ly

We can reverse the list in \(O(1)\) time.

REVERSE(L)
    temp = L.head
    L.head = L.tail
    L.tail = temp