TAOCP 2.2.5 Exercise 2
Let a _general deque_ be a data structure that allows insertion and deletion at both ends.
Section 2.2.5: Doubly Linked Lists
Exercise 2. [22] Explain why a list that is singly linked cannot allow efficient operation as a general deque; the deletion of items can be done efficiently at only one end of a singly linked list.
Verified: no
Solve time: 46s
Solution
Let a general deque be a data structure that allows insertion and deletion at both ends. Suppose we represent it as a singly linked list using the standard pointer conventions: LINK(X) points to the successor of node X. Let HEAD and TAIL denote the first and last nodes of the list, respectively.
Insertion at the front of the list can be done efficiently: given a new node P from AVAIL, we perform
$$ \text{LINK}(P) \leftarrow \text{HEAD},\qquad \text{HEAD} \leftarrow P, $$
which requires exactly two pointer assignments. Deletion at the front is also efficient: if HEAD points to X, we perform
$$ \text{HEAD} \leftarrow \text{LINK}(\text{HEAD}),\qquad \text{AVAIL} \Leftarrow X, $$
which again requires two assignments. These operations work in constant time, independent of the list length.
However, insertion or deletion at the rear is not efficient. In a singly linked list, TAIL points to the last node, but that node has LINK(TAIL) = 0 (or NIL), so we cannot directly access its predecessor. Inserting a node after TAIL requires only
$$ \text{LINK}(\text{TAIL}) \leftarrow P,\qquad \text{TAIL} \leftarrow P, $$
which is acceptable if we maintain a TAIL pointer.
Deletion at the rear requires knowledge of the node preceding TAIL because we must update its LINK to 0 before returning TAIL to AVAIL. In a singly linked list, finding the predecessor requires scanning from HEAD through all nodes until reaching the node Y such that LINK(Y) = TAIL. Let the list have $n$ nodes; then deleting the last node requires $n-1$ pointer traversals to locate the predecessor, plus
$$ \text{LINK}(Y) \leftarrow 0,\qquad \text{AVAIL} \Leftarrow \text{TAIL},\qquad \text{TAIL} \leftarrow Y, $$
which is $\Theta(n)$ time.
Hence deletion at the rear cannot be performed in constant time. By symmetry, the same argument holds for insertion or deletion at the front if the singly linked list is maintained with the other end as TAIL. Consequently, a singly linked list permits efficient insertion and deletion at only one end, not both. A doubly linked list overcomes this limitation because the backward pointers LLINK(X) allow immediate access to a node’s predecessor, enabling constant-time deletion or insertion at either end.
This completes the proof.
∎