Doubly linked list

Doubly linked list

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

Doubly-linked-list.svg
A doubly linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

Contents

Nomenclature and implementation

The first and last nodes of a doubly linked list 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 gotten, 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 pointers, but (as in any linked data structure) they may also be address offsets or indices into an array where the nodes live.

Basic algorithms

Open doubly linked lists

Data type declarations

 record DoublyLinkedNode {
    prev // A reference to the previous node
    next // A reference to the next node
    data // Data or a reference to data
 }
 record DoublyLinkedList {
     Node firstNode   // points to first node of list
     Node lastNode    // points to last node of list
 }

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
 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 insert a node either after or before a given node, with the diagram demonstrating after:

Doubly linked list insert after.png
 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 == 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)

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:

 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 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
 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… …   Wikipedia

  • XOR linked list — XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly linked lists. An ordinary doubly linked… …   Wikipedia

  • Doubly Linked Face List — A Doubly Linked Face List or DLFL is an efficient data structure for storing 2 manifold mesh data. The structure stores linked lists for a 3D mesh s faces, edges, vertices, and corners. The structure guarantees the preservation of the manifold… …   Wikipedia

  • Doubly linked face list — In applied mathematics, a doubly linked face list (DLFL) is an efficient data structure for storing 2 manifold mesh data. The structure stores linked lists for a 3D mesh s faces, edges, vertices, and corners. The structure guarantees the… …   Wikipedia

  • Unrolled linked list — In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Doubly connected edge list — The doubly connected edge list (DCEL) is a data structure to represent an embedding of a planar graph in the plane and polytopes in 3D. This data structure provides efficient manipulation of the topological information associated with the objects …   Wikipedia

  • List (computing) — In computer science, a list is an ordered collection of entities/items. In the context of object oriented programming languages, a list is defined as an instance of an abstract data type (ADT), formalizing the concept of an ordered collection of… …   Wikipedia

  • Jump list — In computer science, a jump list is a data structure which resembles an ordered doubly linked list. Instead of only next and previous links, several nodes contain links to nodes farther away, with the distance increasing geometrically. This… …   Wikipedia

  • Deque — In computer science theory, a deque (short for double ended queue mdash; Deque is usually pronounced deck. ) is an abstract list type data structure, also called a head tail linked list, for which elements can be added to or removed from the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”