Double your linked list, double your fun!

Doubly linked lists may not be the sexiest complex data structures around — we’re lookin’ at you, hash tables — but when you browse the internet or use a music player like Spotify, chances are you’ve traversed one of these complex data structures.

Much like a linked list, a doubly linked list consists of non-contiguous nodes in memory that are connected via “pointers” that tell the computer where the next piece of the chain is in memory. They both also have a head, which points to the first node in the list, and a tail that points to the end, but while the nodes of single linked lists only reference the node that follows them in the chain, nodes in double linked lists refer both to the node that follows and the one that came before.

This gives doubly linked lists an advantage when it comes to time complexity, but puts them at a disadvantage when it comes to the amount of memory they take up compared with singly linked lists. Because they require not just one, but two references to other nodes, the nodes in a double linked list take up more space in memory, but, if you know the “address” of a node in the chain, that extra information makes tasks like lookups, insertions and deletions much more efficient. Because a single linked list must be traversed from the head, all operations are at least linear time complexities, but double linked lists can be traversed from either the head or the tail, and the time complexity of deletion and insertion of specific nodes is constant because the only references that need to change are the nodes on either side of our target node — and we already know where to point them thanks to the information provided by our target node.
These lists are helpful for providing the forward and back buttons on a music player or web browser, giving undo and redo functionality to applications, and offering the ability to serve up a “recently used” list of files in an application’s file menu.