A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Doubly Linked Lists

Linked lists actually come in a number of different flavors. The linked list we’ve discussed until this point is the “classic” linked list, but with some slight modifications, we can grant linked lists additional superpowers.

One variant form of the linked list is the doubly linked list.

A doubly linked list is like a linked list except that each node has two links—one that points to the next node, and another that points to the previous node. In addition, the doubly linked list always keeps track of both the first and last nodes, instead of just the first node.

Here’s what a doubly linked list looks like:

We can implement ...