doubly linked list

(data structure)

Definition: A variant of a linked list in which each item has a link to the previous item as well as the next. This allows easily accessing list items backward as well as forward and deleting any item in constant time.

Also known as two-way linked list, symmetrically linked list.

See also jump list.

Note: See [Stand98, p. 91].

Author: PEB

Implementation

Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list. Maksim Goleta's Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 31 May 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.

Cite this as:
Paul E. Black, "doubly linked list", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 31 May 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/doublyLinkedList.html