Doubly linked list

<h2 id="nomenclature-and-implementation">Nomenclature and implementation</h2>
The first and last nodes of a doubly linked list for all practical applications are immediately accessible (i.e., accessible without traversal, and usually called head and tail) and therefore allow traversal of the list from the beginning or end of the list, respectively: e.g., traversing the list from beginning to end, or from end to beginning, in a search of the list for a node with specific data value. Any node of a doubly linked list, once obtained, can be used to begin a new traversal of the list, in either direction (towards beginning or end), from the given node.
The link fields of a doubly linked list node are often called next and previous or forward and backward. The references stored in the link fields are usually implemented as <a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointers</a>, but (as in any linked data structure), they may also be address offsets or indices into an <a href="/facts/Array_data_structure/BKGvF8AM">array</a> where the nodes live.

<h2 id="basic-algorithms">Basic algorithms</h2>
Consider the following basic algorithms written in Ada:

<h3>Open doubly linked lists</h3>
record DoublyLinkedNode {
 next // A reference to the next node
 prev // A reference to the previous node
 data // Data or a reference to data
}

record DoublyLinkedList {
 DoublyLinkedNode firstNode // points to first node of list
 DoublyLinkedNode lastNode // points to last node of list
}

<h4>Traversing the list</h4>
Traversal of a doubly linked list can be in either direction. In fact, the direction of traversal can change many times, if desired. Traversal is often called <a href="/facts/Iteration/AMc1p7BL">iteration</a>, but that choice of terminology is unfortunate, for iteration has well-defined semantics (e.g., in mathematics) which are not analogous to traversal.
Forwards

node  := list.firstNode
while node ≠ null
 <do something with node.data>
 node  := node.next

Backwards

node  := list.lastNode
while node ≠ null
 <do something with node.data>
 node  := node.prev

<h4>Inserting a node</h4>
These symmetric functions insert a node either after or before a given node:

function insertAfter(List list, Node node, Node newNode)
 newNode.prev  := node 
 if node.next == null
 newNode.next  := null -- (not always necessary)
 list.lastNode  := newNode
 else
 newNode.next  := node.next
 node.next.prev  := newNode
 node.next  := newNode

function insertBefore(List list, Node node, Node newNode)
 newNode.next  := node
 if node.prev == null
 newNode.prev  := null -- (not always necessary)
 list.firstNode  := newNode
 else
 newNode.prev  := node.prev
 node.prev.next  := newNode
 node.prev  := newNode

We also need a function to insert a node at the beginning of a possibly empty list:

function insertBeginning(List list, Node newNode)
 if list.firstNode == null
 list.firstNode  := newNode
 list.lastNode  := newNode
 newNode.prev  := null
 newNode.next  := null
 else
 insertBefore(list, list.firstNode, newNode)

A symmetric function inserts at the end:

function insertEnd(List list, Node newNode)
 if list.lastNode == null
 insertBeginning(list, newNode)
 else
 insertAfter(list, list.lastNode, newNode)

<h4>Removing a node</h4>
Removal of a node is easier than insertion, but requires special handling if the node to be removed is the firstNode or lastNode:

function remove(List list, Node node)
 if node.prev == null
 list.firstNode  := node.next
 else
 node.prev.next  := node.next
 if node.next == null
 list.lastNode  := node.prev
 else
 node.next.prev  := node.prev

One subtle consequence of the above procedure is that deleting the last node of a list sets both firstNode and lastNode to null, and so it handles removing the last node from a one-element list correctly. Notice that we also don't need separate "removeBefore" or "removeAfter" methods, because in a doubly linked list we can just use "remove(node.prev)" or "remove(node.next)" where these are valid. This also assumes that the node being removed is guaranteed to exist. If the node does not exist in this list, then some error handling would be required.

<h3>Circular doubly linked lists</h3>
<h4>Traversing the list</h4>
Assuming that someNode is some node in a non-empty list, this code traverses through that list starting with someNode (any node will do):
Forwards

node  := someNode
do
 do something with node.value
 node  := node.next
while node ≠ someNode

Backwards

node  := someNode
do
 do something with node.value
 node  := node.prev
while node ≠ someNode

Notice the postponing of the test to the end of the loop. This is important for the case where the list contains only the single node someNode.

<h4>Inserting a node</h4>
This simple function inserts a node into a doubly linked circularly linked list after a given element:

function insertAfter(Node node, Node newNode)
 newNode.next  := node.next
 newNode.prev  := node
 node.next.prev  := newNode
 node.next  := newNode

To do an "insertBefore", we can simply "insertAfter(node.prev, newNode)".
Inserting an element in a possibly empty list requires a special function:

function insertEnd(List list, Node node)
 if list.lastNode == null
 node.prev := node
 node.next := node
 else
 insertAfter(list.lastNode, node)
 list.lastNode := node

To insert at the beginning we simply "insertAfter(list.lastNode, node)".
Finally, removing a node must deal with the case where the list empties:

function remove(List list, Node node);
 if node.next == node
 list.lastNode := null
 else
 node.next.prev := node.prev
 node.prev.next := node.next
 if node == list.lastNode
 list.lastNode := node.prev;
 destroy node

<h4>Deleting a node</h4>
As in doubly linked lists, "removeAfter" and "removeBefore" can be implemented with "remove(list, node.prev)" and "remove(list, node.next)".

<h2 id="advanced-concepts">Advanced concepts</h2>
<h3>Asymmetric doubly linked list</h3>
An asymmetric doubly linked list is somewhere between the singly linked list and the regular doubly linked list. It shares some features with the singly linked list (single-direction traversal) and others from the doubly linked list (ease of modification)
It is a list where each node's previous link points not to the previous node, but to the link to itself. While this makes little difference between nodes (it just points to an offset within the previous node), it changes the head of the list: It allows the first node to modify the firstNode link easily.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
As long as a node is in a list, its previous link is never null.

<h4>Inserting a node</h4>
To insert a node before another, we change the link that pointed to the old node, using the prev link; then set the new node's next link to point to the old node, and change that node's prev link accordingly.

function insertBefore(Node node, Node newNode)
 if node.prev == null
 error "The node is not in a list"
 newNode.prev  := node.prev
 atAddress(newNode.prev)  := newNode
 newNode.next  := node
 node.prev = addressOf(newNode.next)

function insertAfter(Node node, Node newNode)
 newNode.next  := node.next
 if newNode.next != null
 newNode.next.prev = addressOf(newNode.next)
 node.next  := newNode
 newNode.prev  := addressOf(node.next)

<h4>Deleting a node</h4>
To remove a node, we simply modify the link pointed by prev, regardless of whether the node was the first one of the list.

function remove(Node node)
 atAddress(node.prev)  := node.next
 if node.next != null
 node.next.prev = node.prev
 destroy node

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/XOR_linked_list/fKfwKXmI">XOR linked list</a></li>
<li><a href="/facts/SLIP_(programming_language)/d8E6xFqn">SLIP (programming language)</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Avoiding game crashes related to linked lists". 9 September 2012. <a href="http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists" target="_blank">http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"Coho, for "Code of Honor"". GitHub. 20 April 2022. <a href="https://github.com/webcoyote/coho/blob/master/Base/List.h" target="_blank">https://github.com/webcoyote/coho/blob/master/Base/List.h</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Doubly linked list open-in-new

Doubly linked list