Doubly Linked Lists are a type of linked list. A doubly linked list's nodes have two "pointers" to other nodes, "next" and "previous." It is called a double linked list because each node only has two "pointers" to other nodes. A doubly linked list may have a head and/or tail pointer.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐ null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │ │"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null └─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘ ▲ △ △ HEAD │ │ DOUBLE │ └──── REFERENCE ────┘
Doubly linked lists are less space efficient than singly linked lists; however, for some operations, they offer significant improvements in time efficiency. A simple example is the
get function, which for a doubly linked list with a head and tail reference will start from head or tail depending on the index of the element to get. For an
n-element list, to get the
n/2 + i indexed element, a singly linked list with head/tail references must traverse
n/2 + i nodes, because it cannot "go back" from tail. A doubly linked list with head/tail references only has to traverse
n/2 - i nodes, because it can "go back" from tail, traversing the list in reverse order.