Doubly Linked Lists, Double the Trouble, but Double the Fun

What’s better than a Linked List? How about two Linked Lists?

Let’s do some quick background for context. Everyone loves reading the background context.

A Linked List is like an array

What’s an array? It’s kinda like a list of stuff.

What’s stuff? It’s whatever data or value you want the computer to know about.

What’s data or value? Like a name, or something. Whatever you want my dawg.

So a Linked List is a favorite amongst Computer Science nerds like myself who like to arrange their data sequentially. We like a Linked List because it’s fast, and just like the dodgeball captains during gym class, we don’t like slow. A Linked List can be used for anything sequential like building a queue or a stack. You get the gist. But when many of us build Linked Lists in our spare time, we often forget that sometimes the best way forwards is backwards.

I mean to say that we build Linked Lists that go in one direction, but sometimes it’s not about going forward fast, it’s about turning around. For instance, it is possible to get to any location on Earth by traveling in one direction, including if your destination is directly behind you, it just takes a while.

Now imagine we can walk backwards. Behold, for this is the power of the Doubly Linked List! We can travel forwards and backwards in our data structure. When is this useful? I wager for most people reading my article it’s pretty useful, as a Doubly Linked List enables the “back” button on the browser to work. Instead of sending a brand new request and doing a whole thing, we can simply go backwards in our data structure to display information that the computer already has loaded in its memory. What a blessing!

You want to see what it looks like? It looks like this:

This image was taken from another Medium article which does an excellent job explaining the concepts.

We can see in the image that the Singly Linked List travels in one direction, while the Doubly Linked List goes in two directions. That’s the magic in a nutshell. We have now the freedom of transversal.

Now then, I know you’re all curious to see the code, so let’s get rockin’ and rollin’.

This is a Node helper class. Sometimes people don’t include this code but I wanted you to see everything needed to make it work.

And this is the Doubly Linked List! Horray! It has a head, and it has a tail. Or rather, it doesn’t yet, but it will soon.

So what’s some things we can do with this code? Well, let’s look at a few examples.

Here’s how you would append to your Doubly Linked List:

This is an interesting example because we’re dealing with both a head node and a tail node with their own pointers.

First we’re checking to see if the DLL is empty, and if so, we have a snake eating itself with the head pointing at the tail and the tail pointing at the head. Otherwise we set the new nodes previous pointer to the tail, and set the tail next pointer to be the new node.

What would the remove function look like then?

Here we see a similar story unfolding. We have to deal with both the head and tail nodes. Looking at it now, I’m not entirely sure that this code is complete, but it worked when I ran it, and I didn’t do much testing. If it’s incomplete, I’ll leave it as a fun exercise for the reader.

In sum, we can use a Doubly Linked List when we are interested in moving backwards and forwards in our data structure, like the next and back buttons on a web browser or a music playlist, and knowing about Doubly Linked Lists makes you a hit at the bangers engineers throw (I would assume). There’s some code to get started, so have fun!