Understanding Doubly Linked List: A Tutorial

Photo by JJ Ying on Unsplash

Are you trying to learn linked list? Doubly linked list? Well, I’m learning about it too right now, but I want to share what I already know about it. I am learning this data structure from this course right now, it’s great, and free. Linked list is a linear, and is a node based data structured. Every node has a pointer to another data within the list. There are 2 kinds of linked list, singly and doubly. I already share how I learn singly linked list in this post, now I want to share what I learn about doubly linked list so far.

In singly linked list, our node only has val and next properties, whereas next is become the pointer to the next node. Because we only have one pointer that points to the next node, once we walk through the list, we cannot walk back. For some use case it is not really ideal if we require to go back and forth within the list.

In doubly linked list, we have another pointer prev which points to the previous node, which fulfill our requirement to go back and forth within the list.

First let’s initiate the class for doubly linked list and its constructor. The reason we have tail variable is because we will have tail pointers to maintain. Most of the API that we will create is the same as we made in this post. Now lets start with append method.

First, dont forget to increase the size by 1, and initiate a new node. Since we want to add new node to the end of the list (which mean is its tail), then we check if the tail is null, we directly update the head to point to a new node, the same as the tail, then return.

Empty list after we insert a new node

Else, since we want to add new node to the end of the list, the steps are:

1. update new node prev to point to current tail (node.prev = this.#tail)
2. update current tail next to point to new node (this.#tail.next = node)
3. update the tail to point to new node (this.#tail = node)

Consider we want to add 3 to the list, below is the illustration.

Next we move on to the prepend method which look like below

First, we increase the size by one, and init a new node. Since we want to add new node to the beginning (which mean the head), then we check if head is null, we directly update the tail and head to new node, then return.

Else, these are the step to append it:

1. update new node next to point to current head (node.next = this.#head)
2. update current head prev to point to new node (this.#head.prev = node)
3. update the head to point to new node (this.#head = node)

Consider we want to add 1 to the list, below is the illustration.

Next we add insertAt method to the class so we can add a new node at specific index.

First we check if index is more than size, then we throw an error. There we have a counter variable with 1 initial value, this is because we already handle the case where index is 0, where we just use the prepend method since eventually it is the same operation.

If index is more than 0, increase the size, loop over the list, and break when counter is equal to index, then there are 4 operations to do:

1. update new node next to point to current next (node.next = curr.next)
2. update current next previous to point to node (curr.next.prev = node)
3. update current next to point to node (curr.next = node)
4. update node prev to point to curr (node.prev = curr)

Consider we made .insertAt(5, 2) operation to the list, below is the illustration.

Next we move to create 2 method removeHead and removeTail

In removeHead, which mean we want to remove from the beginning of the list, we update the head to become it’s next, then reduce the size by 1. The illustration is like below.

The same operation happened in removeTail, the difference is just we update the tail this time. The illustration is like below.

Next we move to create removeAt method that look like below

The first step is mostly the same as insertAt method, if index is equal 0 then we just call removeHead operation since it is the same operation. Else we loop through the list as long as the counter is less than the index, then we simply update the current next to equal its next next. Consider the case where we made .removeAt(3) operation. Below is the illustration to get better undertanding.

Last thing we want to create is get method, that just simply return the value after we loop through the list until a specific index is reached.

That is pretty much I know about linked list, hope it help someone out there learning about doubly linked list.

Full working code: doubly-linked-list.js (github.com)