It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first \(m\) index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how to implement the procedures ALLOCATE-OBJECT and FREE-OBJECT so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

Suppose we have \(A\) which is the entry-point to our doubly linked list which is already compact. This list contains \(m\) nodes that hold values and \(n\) nodes that do not. Suppose also that we maintain \(free\) which is a stack that holds an ordered list of these \(n\) available nodes starting with the node in position \(m + 1\).

In this scenario ALLOCATE-OBJECT changes very little. We simply POP the top value off the stack and return it resulting in basically just syntax adjustments:

ALLOCATE-OBJECT()

1 if STACK-EMPTY(free)

2      error "out of space"

3 else x = POP(free)

4      return x

On the other hand, FREE-OBJECT now has more work to do to ensure that the compactness remains undisturbed. The simplest approach is to take the tail value (the node at position \(m\)) and move it into the position that was just freed, doing nothing if they are one and the same. If we do this tail swap operation we need to also account for the nodes that pointed to the tail and update them accordingly.

FREE-OBJECT(x)

01 y = A

02 while y.next != NIL:

03      y = y.next

04 if x == y:

05      PUSH(free, x)

06 else:

07      x.key = y.key

08      x.prev = y.prev

09      x.next = y.next

10      if x.prev != NIL:

11          x.prev.next = x

12      else: A = x

13      if x.next != NIL:

14          x.next.prev = x

15      PUSH(free, y)