## What’s a doubly linked list, and how do you create one?

Aug 13 · 8 min read

You may be wondering why I chose to preface this article with a picture of a Metro North train—and if you live in New York, you may even be hating me for reminding you of the reason you’re always late. Doubly linked lists have many of the same characteristics as a train, however, and that’s how I’d like you to visualize them as we roll through a couple of methods.

So, how is it that a data structure resembles a train? Well, the way that the train cars are connected is very similar to how nodes are connected within a doubly linked list.

Each train car has a coupler (the thing that holds the cars together); in linked lists we have analogous things called pointers. With a doubly linked list, there two pointers, hence “doubly” (rather than singly linked lists where the pointers are unidirectional): one pointing forwards and one pointing backward. There are only two cars on the train that don’t have two couplers, and those cars are the front and back of the train. In a doubly linked list, these positions are typically called the head and the tail, and the train cars themselves are called nodes. All nodes are connected frontwards and backward with the exception of the head and tail, which just have one pointer each. So, doing away with the train metaphor for a moment, let’s code a skeleton of a doubly linked list, which I’ll name Doubly.

Here we have two classes, one which defines the nodes, and one which defines the doubly linked list, which again, I’ve called Doubly, but you can name it whatever you like. Each node is constructed with three properties, the val, which is declared upon creation, and the two pointers next and prev, which are set to null because they are currently not pointing to any other nodes, until we set up those connections.

Next, we define the Doubly class. In the constructor, it has three properties: the head, the tail, and the length. The length will increase as the nodes start falling into the list. For each node, the length increments by one, and the head and tail will only be null if there are no nodes within the list. The first method we’re going to add to this Doubly class is the push method, which will create a node and add it to the end of the list.

“But wait,” you may be thinking, “did you say push, like pushing to an array?” That’s exactly right. A linked list and an array are pretty similar, but a doubly linked list doesn’t have indexes like an array, and the values point to each other instead of said index. Let’s get some code for pushing to our doubly linked list, dubbed Doubly.

`What we see in the consoleDoubly {    head: Node{val: "Harry"},     next: null, prev: null},    tail: Node{val:"Harry"},     next: null, prev: null    length: 1}`

After initializing a new object called Doubly, with the head and tail we push a node, using our custom method with the value of Harry. Right now, the head and tail both have pointers pointing to nothing (if you’d like to imagine the front car of the Hogwarts Express, feel free).

It’s like a train with only one car; it’s not connected to anything, it just sits by its lonesome waiting for a train buddy. When a second car enters, it falls to the back of the line and is now the last train car. Now our two train cars need a coupler, but for now, there’s only one thing in the list; thus the current length is equal to 1. There are a few ways that we can check if any nodes exist within our list, and thus what actions Doubly should take. The first is the way that I’ve displayed above. If the list has a length of 0, then there are no nodes. You can also check by making sure the head isn’t null, like so:

`if (this.length === 0) // first way, meaning 0 nodes existif (this.head !== null) // second way to check, because if the head is null then nothing exists within our list. if (!!this.head) // same as above but less verbose`

This checks, is there a nodeset to the head of this list? No? So then we’re pushing for the first time, and both the head and tail are this new node. If there is a node, we’ll hit that else statement. Remember, all nodes are initialized with pointers: prev (for previous), and next, and both are set to null. So, we give our old tail’s next pointer a value, our new node. Then that new node simply points back at the old tail with it’s prev pointer. Then we declare our new tail, which is that new node. It’s very much like this meme.

So when we push a new node, for instance, Harry’s best friend Ron Weasley, the node that has Harry as a value points to that new node that has Ron as a value, and Ron points back at Harry. If we log this in the console, it looks like this:

`let doubly = new Doubly // our instance of a Doubly Linked Listlet doubly = new Doubly;doubly.push("Harry");doubly.push("Ron");Console.log(doubly);OUTPUT IN THE CONSOLE Doubly{  head: Node {  val: "Harry",   next: Node { val: "Ron", next: null, prev: [Circular]},  prev: null  },  tail: Node {  val: "Ron",   next: null,   prev: Node { val: "Harry", next: [Circular], prev: null}  } }`

That’s interesting: our head points to Ron and now both nodes have something in there called [Circular]. All circular signifies is that they point back and forth to each other ad infinitum. The node with Harry points to Ron, which points to Harry, which points to Ron, and it never stops.

So this is the way nodes hold values, and point to other nodes. Before moving on, it’s noteworthy to mention that although the head and the tail point to each other, both still have one pointer, set to null. The head will always have a previous value of null, and the tail will always have a next value of null, because there’s nothing before the head or after the tail. That’s what makes them the head and the tail (front and back).

That’s the point of a doubly linked list: to have a node with a value, pointing to other nodes with values. You can write methods on Doubly just like you would arrays. Methods like pop(), unshift(), or look up a value with get and remove from a particular node. Let’s write a quick method, pop, that removes the last element of the list.

Just like a normal array, we can define our own pop method, which literally pops off the last node and returns that node. There are a few conditions to check. The first one is if the node has no length, then there are no nodes, and we return undefined. If the length is 1, after it’s removed from the list, then there are no nodes remaining and we must reset the head and tail to null. If there’s more than one item, then we go to the back of the train (the last node) and set that node to be returned. Here’s how it would work in code:

`let doubly = new Doubly // our instance of a Doubly Linked Listdoubly.push("Harry");doubly.push("Ron");doubly.push("Hermione"); doubly.push("Draco");doubly.pop();// Returned node Node {val: "Draco", next: null, prev: null}`

Quickly running through, before we drop Draco: this node has a prev value of Hermione, and we set Hermione’s node equal to the temp variable:

`let temp = this.tail.prev // this.tail = draco's node, // his prev pointer points to Hermione's node`

Then we set Draco’s previous pointer to null so he’s no longer connected to the rest of the crew:

`let temp = this.tail.prev;this.tail.prev = null;this.tail = temp;`

So now that we have Hermione’s node in memory, we remove the reference to her node from Draco’s by setting our old tail’s previous pointer to null, and then setting our new tail to Hermione’s node, because Draco’s been kicked off the Hogwarts Express. The only thing left is to make sure there is no connection, by setting our new tail’s (Hermione’s ) next pointer to null. Now we have an instance of a doubly linked list where we can use push and pop methods, keep track of how many items are in the list, and get references to the following nodes with their pointers.

There’s much more to doubly linked lists. We’ll get into some more methods in another article as this one is running much longer than expected. I know doubly linked lists and arrays seem the same, and in some ways, they are. The differences will be in the next article. If you want to read up on some differences right now, you can find them here: Linked List vs Array.

This article wouldn’t have been possible without Colt Steele and his algorithm course. So Colt, even though you’ll never read this, thanks for teaching all of us out there who need it. These data structures can be really challenging, and it may seem you only need them for interviews, but I assure you they will make your coding journey a bit easier. New perspectives and knowledge are well worth the frustration of trying to understand these data structures.

I hope this made the doubly linked list a bit easier to grasp, and I look forward to writing the follow-up soon. Thanks so much for reading, and, happy coding!

Written by