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.

Contents  [hide] 1 Nomenclature and implementation 2 Basic algorithms 2.1 Open doubly-linked lists 2.1.1 Data type declarations 2.1.2 Iterating over the nodes 2.1.3 Inserting a node 2.1.4 Deleting a node 2.2 Circular Doubly-linked lists 2.2.1 Iterating over the elements 2.2.2 Inserting a node 3 References 3.1 See also

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

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may bechallenged and removed. (April 2009)

See also

• XOR linked list
• SLIP (programming language)

from wikipedia:
http://en.wikipedia.org/wiki/Doubly-linked_list