TAOCP 2.2.4 Exercise 4

In representation (4), a circular linked list is maintained with a distinguished head node `HEAD`.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 4. [20] State insertion and deletion operations that give the effect of a stack, using representation (4).

Fig. 10. Addition of polynomials.

Verified: no
Solve time: 7m26s

Solution

In representation (4), a circular linked list is maintained with a distinguished head node HEAD. The list is empty when

$$ \operatorname{LINK}(\text{HEAD})=\text{HEAD}. $$

To obtain stack behavior, the top of the stack is always taken to be the first node after HEAD. Thus insertion and deletion are performed immediately after HEAD.

Since representation (4) uses an AVAIL list for free storage, allocation and deallocation must correctly maintain that list.

Insertion (Push)

To push an item $X$ onto the stack:

  1. If AVAIL = \Lambda, signal OVERFLOW.
  2. P \leftarrow AVAIL.
  3. AVAIL \leftarrow LINK(AVAIL).
  4. INFO(P) \leftarrow X.
  5. LINK(P) \leftarrow LINK(HEAD).
  6. LINK(HEAD) \leftarrow P.

After step 3, node $P$ has been removed from the free-space list. Steps 5 and 6 insert $P$ immediately after HEAD, so $P$ becomes the new top of the stack.

Deletion (Pop)

To pop the top item from the stack:

  1. If LINK(HEAD) = HEAD, signal UNDERFLOW.
  2. P \leftarrow LINK(HEAD).
  3. X \leftarrow INFO(P).
  4. LINK(HEAD) \leftarrow LINK(P).
  5. LINK(P) \leftarrow AVAIL.
  6. AVAIL \leftarrow P.

Step 4 removes the first node after HEAD. Steps 5 and 6 return that node to the front of the free-space list while preserving the remainder of the AVAIL chain.

Why This Gives a Stack

Maintain the invariant that the node immediately following HEAD is the top of the stack.

When an item is pushed, the new node is inserted immediately after HEAD. Therefore the most recently inserted item becomes the first node in the list.

When an item is popped, the node immediately after HEAD is removed. Since every push places its node in that position, the node removed is precisely the most recently inserted node that has not yet been deleted.

Hence the operations satisfy the last-in, first-out property required of a stack.

Both operations require only a constant number of pointer manipulations and therefore run in $O(1)$ time. ∎