data-structures Linked List Doubly Linked List


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.

Example Code in C