TAOCP 2.2.5 Exercise 12
In the elevator simulation, the program must frequently insert and delete users from various lists representing queues on floors (`QUEUE[IN]`) and passengers inside the elevator (`ELEVATOR`).
Section 2.2.5: Doubly Linked Lists
Exercise 12. [22] Why is it a good idea to use doubly linked lists instead of singly linked or sequential lists in the simulation program of this section?
Verified: no
Solve time: 1m08s
Solution
In the elevator simulation, the program must frequently insert and delete users from various lists representing queues on floors (QUEUE[IN]) and passengers inside the elevator (ELEVATOR). These operations occur at arbitrary positions in the list, not only at the head or tail. A singly linked list requires knowledge of the predecessor node to delete a given node NODE(X); without it, one must traverse the list from the head to locate the preceding node, which incurs $O(n)$ time in the worst case for a list of length $n$. In contrast, a doubly linked list allows deletion given only the pointer X to the node itself, using the steps in equation (4):
$$ \text{RLINK}(\text{LLINK}(X)) \leftarrow \text{RLINK}(X),\qquad \text{LLINK}(\text{RLINK}(X)) \leftarrow \text{LLINK}(X),\qquad \text{AVAIL} \Leftarrow X. $$
These steps modify exactly two links and reclaim the node, independent of the list's length. Insertion adjacent to a given node is similarly simplified by equation (5), which changes five link fields to insert a node to the right of NODE(X). In a singly linked list, inserting before a node would require locating its predecessor, again requiring traversal.
Sequential lists (arrays) are inefficient for this application because deletions and insertions at arbitrary positions require shifting elements, which takes $O(n)$ time per operation. The elevator simulation may have many users entering and leaving at random floors, so the number of such operations is not bounded by a constant. Doubly linked lists provide $O(1)$ insertion and deletion at known positions, which is crucial for the performance of the simulation.
Moreover, doubly linked lists support bidirectional traversal, which can be useful in managing queues or handling the elevator’s current passenger list when updating CALLCAR[j] or removing users who give up waiting. This eliminates repeated scanning from the head of the list, reducing the total number of steps in the simulation.
Therefore, the choice of doubly linked lists minimizes both the number of link modifications and the time complexity of insertion and deletion operations in the simulation. The extra memory per node is compensated by the efficiency gained in frequent dynamic updates.
This completes the proof.
∎