TAOCP 2.2.5 Exercise 1
In representation (1) of a doubly linked list, there are distinguished variables `LEFT` and `RIGHT` giving the locations of the leftmost and rightmost nodes, respectively.
Section 2.2.5: Doubly Linked Lists
Exercise 1. [21] Give specifications for the insertion and deletion of information at the left end of a doubly linked list represented as in (1). (With the dual operations at the right end, which are obtained by symmetry, we therefore have all the actions of a general deque.)
Verified: no
Solve time: 39s
Solution
In representation (1) of a doubly linked list, there are distinguished variables LEFT and RIGHT giving the locations of the leftmost and rightmost nodes, respectively. Each node contains fields LLINK and RLINK, and the null link is denoted by $\Lambda$.
To insert information at the left end, let P be the newly available node and let INFO(P) receive the new information. The specification must account for both the empty and nonempty list cases.
If the list is empty, so that LEFT = \Lambda, the new node becomes both ends of the list:
$$ P \Leftarrow \text{AVAIL},\qquad \text{LLINK}(P) \leftarrow \Lambda,\qquad \text{RLINK}(P) \leftarrow \Lambda, $$
$$ \text{LEFT} \leftarrow P,\qquad \text{RIGHT} \leftarrow P. $$
If the list is nonempty, let the former leftmost node be LEFT. The new node is inserted immediately to its left:
$$ P \Leftarrow \text{AVAIL},\qquad \text{LLINK}(P) \leftarrow \Lambda,\qquad \text{RLINK}(P) \leftarrow \text{LEFT}, $$
$$ \text{LLINK}(\text{LEFT}) \leftarrow P,\qquad \text{LEFT} \leftarrow P. $$
For deletion of information at the left end, assume the list is nonempty. Let P denote the node currently at the left end:
$$ P \leftarrow \text{LEFT}. $$
If RLINK(P)=\Lambda, the list contains exactly one node. After deletion the list becomes empty:
$$ \text{LEFT} \leftarrow \Lambda,\qquad \text{RIGHT} \leftarrow \Lambda,\qquad \text{AVAIL} \Leftarrow P. $$
If RLINK(P)\ne\Lambda, let the second node become the new left end:
$$ \text{LEFT} \leftarrow \text{RLINK}(P),\qquad \text{LLINK}(\text{LEFT}) \leftarrow \Lambda,\qquad \text{AVAIL} \Leftarrow P. $$
These operations are the left-end analogues of insertion and deletion at the right end. By symmetry, replacing LEFT by RIGHT and interchanging LLINK with RLINK gives the corresponding right-end operations. Together they provide all deque operations.
$$ \boxed{\text{Left-end insertion and deletion are specified as above}} $$