data-structures Linked List Doubly Linked List
Example
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.
