A doubly linked list allows two-way traversal

by Jii Yoo
…
Note
|
Writing

The main difference between a doubly linked list and a singly linked list is that the nodes in doubly linked lists hold two references: the next node and the previous node. This makes the list traversable in two directions.

           head                         tail
         ---------     ---------     ---------
NULL <-- | nodeA | <-> | nodeB | <-> | nodeC | --> NULL
         ---------     ---------     ---------

Since the basic structure are the same between single and doubly linked list, they share majority of the methods such as insert, remove, cat, etc…

Although they share same methods, the implementation will change slightly since doubly linked list can link to the preceding node as well. Here are couple methods where implementation will change:

  • insert(item)
  • pop_back
  • pop_front
  • remove(item)
  • cat(list) - catenate two lists together

Since doubly linked list can traverse backward, we can utilize this to implement more useful methods:

  • find_last(value) - get the last node that holds value
  • display(reverse=false) - print the contents in reverse order if reverse is true
Backlinks: