Doubly linked list

Basic algorithms

Consider the following basic algorithms written in Ada:

Open doubly linked lists

<b id="mwJQ">record</b> <i id="mwJg">DoublyLinkedNode</i> { next <i id="mwJw">// A reference to the next node</i> prev <i id="mwKA">// A reference to the previous node</i> data <i id="mwKQ">// Data or a reference to data</i> }

<b id="mwKw">record</b> <i id="mwLA">DoublyLinkedList</i> { <i id="mwLQ">DoublyLinkedNode</i> firstNode <i id="mwLg">// points to first node of list</i> <i id="mwLw">DoublyLinkedNode</i> lastNode <i id="mwMA">// points to last node of list</i> }

Traversing the list

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 iteration, 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 <b id="mwNw">while</b> node ≠ <b id="mwOA">null</b> <do something with node.data> node := node.next

Backwards

node := list.lastNode <b id="mwPA">while</b> node ≠ <b id="mwPQ">null</b> <do something with node.data> node := node.prev

Inserting a node

These symmetric functions insert a node either after or before a given node:

<b id="mwQQ">function</b> insertAfter(<i id="mwQg">List</i> list, <i id="mwQw">Node</i> node, <i id="mwRA">Node</i> newNode) newNode.prev := node <b id="mwRQ">if</b> node.next == <b id="mwRg">null</b> newNode.next := <b id="mwRw">null</b> <i id="mwSA">-- (not always necessary)</i> list.lastNode := newNode <b id="mwSQ">else</b> newNode.next := node.next node.next.prev := newNode node.next := newNode

<b id="mwSw">function</b> insertBefore(<i id="mwTA">List</i> list, <i id="mwTQ">Node</i> node, <i id="mwTg">Node</i> newNode) newNode.next := node <b id="mwTw">if</b> node.prev == <b id="mwUA">null</b> newNode.prev := <b id="mwUQ">null</b> <i id="mwUg">-- (not always necessary)</i> list.firstNode := newNode <b id="mwUw">else</b> 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:

<b id="mwVg">function</b> insertBeginning(<i id="mwVw">List</i> list, <i id="mwWA">Node</i> newNode) <b id="mwWQ">if</b> list.firstNode == <b id="mwWg">null</b> list.firstNode := newNode list.lastNode := newNode newNode.prev := null newNode.next := null <b id="mwWw">else</b> insertBefore(list, list.firstNode, newNode)

A symmetric function inserts at the end:

<b id="mwXw">function</b> insertEnd(<i id="mwYA">List</i> list, <i id="mwYQ">Node</i> newNode) <b id="mwYg">if</b> list.lastNode == <b id="mwYw">null</b> insertBeginning(list, newNode) <b id="mwZA">else</b> insertAfter(list, list.lastNode, newNode)

Removing a node

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

<b id="mwag">function</b> remove(<i id="mwaw">List</i> list, <i id="mwbA">Node</i> node) <b id="mwbQ">if</b> node.prev == <b id="mwbg">null</b> list.firstNode := node.next <b id="mwbw">else</b> node.prev.next := node.next <b id="mwcA">if</b> node.next == <b id="mwcQ">null</b> list.lastNode := node.prev <b id="mwcg">else</b> 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.

Circular doubly linked lists

Traversing the list

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 <b id="mwgA">do</b> do something with node.value node := node.next <b id="mwgQ">while</b> node ≠ someNode

Backwards

node := someNode <b id="mwhQ">do</b> do something with node.value node := node.prev <b id="mwhg">while</b> 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.

Inserting a node

This simple function inserts a node into a doubly linked circularly linked list after a given element:

<b id="mwjQ">function</b> insertAfter(<i id="mwjg">Node</i> node, <i id="mwjw">Node</i> 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:

<b id="mwkw">function</b> insertEnd(<i id="mwlA">List</i> list, <i id="mwlQ">Node</i> node) <b id="mwlg">if</b> list.lastNode == <b id="mwlw">null</b> node.prev := node node.next := node <b id="mwmA">else</b> 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:

<b id="mwnA">function</b> remove(<i id="mwnQ">List</i> list, <i id="mwng">Node</i> node); <b id="mwnw">if</b> node.next == node list.lastNode := <i id="mwoA">null</i> <b id="mwoQ">else</b> node.next.prev := node.prev node.prev.next := node.next <b id="mwog">if</b> node == list.lastNode list.lastNode := node.prev; <b id="mwow">destroy</b> node

Deleting a node

As in doubly linked lists, "removeAfter" and "removeBefore" can be implemented with "remove(list, node.prev)" and "remove(list, node.next)".

Advanced concepts

Asymmetric doubly linked list

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.

As long as a node is in a list, its previous link is never null.

Inserting a node

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.

<b id="mwvA">function</b> insertBefore(<i id="mwvQ">Node</i> node, <i id="mwvg">Node</i> newNode) <b id="mwvw">if</b> node.prev == <b id="mwwA">null</b> <b id="mwwQ">error</b> "The node is not in a list" newNode.prev := node.prev atAddress(newNode.prev) := newNode newNode.next := node node.prev = addressOf(newNode.next)

<b id="mwww">function</b> insertAfter(<i id="mwxA">Node</i> node, <i id="mwxQ">Node</i> newNode) newNode.next := node.next <b id="mwxg">if</b> newNode.next != <b id="mwxw">null</b> newNode.next.prev = addressOf(newNode.next) node.next := newNode newNode.prev := addressOf(node.next)

Deleting a node

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

<b id="mwzA">function</b> remove(<i id="mwzQ">Node</i> node) atAddress(node.prev) := node.next <b id="mwzg">if</b> node.next != <b id="mwzw">null</b> node.next.prev = node.prev <b id="mw0A">destroy</b> node