In computer science, a doubly-linked list is a linked data structure that
consists of a set of data records, each having two special link fields that
contain references to the previous and to the next record in the sequence.
It can be viewed as twosingly-linked lists formed from the same data items,
in two opposite orders. A doubly-linked list whose nodes contains three fields:
an integer value, the link to the next node, and the link to the previous node.
The two links allow walking along the list in either direction with equal ease.
Compared to a singly-linked list, modifying a doubly-linked list usually requires
changing more pointers, but is sometimes simpler because there is no need to
keep track of the address of the previous node.
Nomenclature and implementationThe
references stored in the link fields are
usually implemented by pointers; but
(as in any linked data structure) they may also be address offsets or indices into
an array where the nodes live.
The link fields are often called forward and backwards, or next and previous.
A pointer to any node of a doubly-linked list gives access to the whole list. However,
it's usually convenient to handle the list by the pointers of the first and last nodes,
e.g. when passing it to subroutines.
Basic algorithms
Open doubly-linked lists
Data type declarations
record Node {
data // The data being stored in the node
next // A reference to the next node; null for last node
prev // A reference to the previous node; null for first node
}
record List {
Node firstNode // points to first node of list; null for empty list
Node lastNode // points to last node of list; null for empty list
}
Iterating over the nodes
Iterating through a doubly linked list can be done in either direction. In fact, direction can
change many times, if desired.
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
Inserting a node
These symmetric functions add a node either after or before a given node, with the
diagram demonstrating after:
function insertAfter(List list, Node node, Node newNode)
newNode.prev := node
newNode.next := node.next
if node.next == null
list.lastNode := newNode
else
node.next.prev := newNode
node.next := newNode
function insertBefore(List list, Node node, Node newNode)
newNode.prev := node.prev
newNode.next := node
if node.prev is null
list.firstNode := newNode
else
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)
Deleting a node
Removing a node is easier, only requiring care with the firstNode and 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
destroy node
One subtle consequence of this procedure is that deleting the last element 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.
Circular Doubly-linked lists
Iterating over the elements
Assuming that someNode is some node in a non-empty list, this code iterates 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.
Inserting a node
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
References
See also
from wikipedia:
http://en.wikipedia.org/wiki/Doubly-linked_list