(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].
Binary search may be effective with an ordered, doubly linked list. It makes O(n) traversals, as does linear search, but it only performs O(log n) comparisons. For more explanation, see Tim Rolfe's Searching in a Sorted Linked List.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 23 May 2011.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "doubly linked list", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/doublyLinkedList.html