DS & A Series - Singly & Doubly Linked Lists: Implementation & Insights

“Reverse a linked list” — Sound familiar? This article will help you grasp an understanding of one of the most popular data structures that is asked about in tech interviews.

In this article, I will go through each singly & doubly linked list data structures in JavaScript and their class implementation. These can be executed functionally, but I feel that a class implementation makes it easier to conceptualize them as data structures. Classes in JS are syntactical sugar, but that’s another story for another day!

Singly Linked List

The list of the methods that we will be implementing are the same for singly and doubly linked lists and are listed below:

1. Push
2. Pop
3. Shift
4. Unshift
5. Get
6. Set
7. Insert
8. Remove
9. Reverse

The only differences will be the implementation of some of those methods.

At a high level, what is a linked list? A linked list is a data structure that contains nodes (that contain some information) that have pointers to the next node. In a linked list you have a head and a tail node which indicate the beginning and end of the linked list. The only difference between a singly linked list and doubly linked list is that in a doubly linked list you have pointers for both directions meaning that you would have a .next property and .previous property whereas in a singly linked list you only have a .next property.

Before we start building out our linked list class, let’s make a Node class that defines the nodes in our linked list. This node class has a constructor that initializes a val that is passed in and sets its next attribute to null.

The next step is to define the linked list class, which will be initialized with three values: head, tail and length. The head and tail are initially set to null since we don’t have a head or tail (yet). The length is set to 0 because the list doesn’t have any nodes yet.

1. Push — The push method will accept a val that we want to add to our linked list. Now is the moment we’ll initialize a new node that we defined as a class earlier. In our code we check to see if there isn’t already a head defined for the list, if there is then we set our head and tail to equal this new node, if not then we have the next property of our tail point to the new node and then set our tail property to now be the new node. We increase the length of our list and finally return the list itself.

2. Pop — This method, just like the array method pop, will pop off the last element of the linked list. In a linked list, popping off an element isn’t as easy as doing it in an array, we need to be able to grab the penultimate element first to be able to do that. The reason is because we’ll be reassigning that element as the new tail of the list. We first check to see if there is a head, if there isn’t we return null. Next, we check and see if the list has a length of 1. If it does, we simply store the head in a variable, set the head and tail to null and return the element. If the length is greater than 1, we have to start from the head of the list and iterate through the list using the length of the list in a for loop or using a while loop with the condition of the current node having a .next.next property not equal to null. Once we grab that node, we can simply reassign that node’s next property to be null and reassign that node to be the new tail. We then return the previous tail.

3. Shift — This method is also similar to the array method shift: all that you’re doing is removing the first node of the list and reassigning the next node to be the new head. Again, we first check and see if there is a head node, if there isn’t we return null. If the length of the list is 1, we simply call our pop method (why write more code than you need to?). If the length of the list is longer than 1, we have to use a temporary variable to hold our ‘old’ head, reassign the node in its next property to be the new head, decrease the length of our list by 1 and finally return the old head.

4. Unshift — This method lets us add a value to the beginning of the linked list. We first check to see if there isn’t already a head in the list. If there isn’t, then we simply call the push method with the value passed in. If there already is a head, then we initialize a new node and set the next property of this new node to be the head of the list, we reassign the head property of the list to be the new node, increase the length of the list by 1 and finally return the list itself.

5. Get — This method accepts an argument of an index number (zero-based index) from which you retrieve the respective node in the linked list. We first check and see if the idx isn’t less than 0 or that it isn’t greater than or equal to the length of the list. If it is, we return null. Next, we check to see if the index is 0. If it is, we return the head node. If the index isn’t 0, then we need to iterate through the list using a for loop. We set the idx as our terminating condition: i should be less than the passed in index. In the block of our for loop, we have a current variable (that is initialized as the head node) to be reassigned as current.next. After the loop, we just return the current variable.

6. Set — This method is fairly easy to implement as we’ve done most of the leg work in the previous get method! This method accepts an argument of an index and a val that will be set to the node we want to change. We initialize a variable to be a call to our get method with the index that was passed in. If the node is truthy (meaning that a value was successfully retrieved), we change the val property of the node to be the value that was passed in to the set method and then return true. If the node was falsey (meaning that no node was found with the provided index) we return false.

7. Insert —This method is also fairly easy to implement at this point, because most of the leg work is already done. If the passed in index is 0, then we call the unshift method on our list with the passed in value. Instead of simply having a this.unshift(val) call, we also want to have the doubly bang (!!) in front of the call to coerce that into a boolean true value. In this method we will ultimately be returning either a true or false value. We next check if the idx is equal to the length of the list, if it is then we call the push method (with the double bang in front). If the value is less than 0 or greater than the length of the list we return false. Finally, we initialize and return a variable set to a get method call with the index that was passed in MINUS 1. The reason for that is because since we’re inserting a node at the specified index and not setting, so we want to grab the nodes around that index first. We then set the next property of that node to be the new node and then set that new nodes next property to be the next node that we grabbed using our get method. Finally, we increase the length of the list and return the list itself.

8. Remove — This method accepts an index that we will use to remove a node from our list. This method is pretty straightforward as well. We start by checking to see if the passed in index is less than 0 or greater than equal to the length of the list, if it is then we return false. If the index is within range, then we use the get method to grab the node before the specified index. Once we have that node, we have its next property to be equal to next node of the next node. The ‘removed’ node should be assigned to be a variable and have its next property to be set to null, we then decrease the length of the list and return the removed node.

9. Reverse — All roads lead to Rome, well in our case…to Reverse! We first check to see if there is a head in the list, if there isn’t we return null. Next, we initialize some variables: current, prev and next. Current we set to equal the head, prev we set to be null and next we don’t set as anything (yet). We then want to switch the tail and head so we set the head to be equal to the tail and tail to be equal to current (the reason we didn’t have it set to head is because we’d essentially be pointing to the new head, whereas we want the old head). We then use a while loop to loop through the list and swap the direction the list is going in. It helps to conceptualize the process as moving in segments up the list from the beginning to the end. What happens in the while loop is that we set next to be current.next, current.next to be prev, prev to be current and then finally current to be next. It can be a little hard to wrap your head around this at first so I will unpack what’s going on in the while block. Naturally, we’re setting next to be the next of the current element, which at first is the head. Current.next is set to prev (which is at first null), because remember the head of our list is now the end or tail of our list — so its next property should be null. Prev then becomes current (in the first iteration of the while block this is the head, which when you think about it is the next element of its next element when the list is reversed). Finally, current becomes the next variable so we can start this swapping process for the next segment of the list. Once we’re done with the loop, we return the list.

Doubly Linked List

A doubly linked list will have the same methods as the above singly linked list with a slight variation: the nodes have a previous property. The previous property needs to be set in all of the class’s methods. The prev property has some pros and cons to it that I will go into later in the article.

The node class in the doubly linked list looks like this:

1. Push — This method is similar to the singly linked list method except that if there is a head present in the list, we set our new node’s prev property to equal to the current tail in addition to having the old tail’s next property point to the new node.

2. Pop — The pop method’s implementation in the doubly linked list is actually easier, because we no longer have to iterate through the whole list to get the penultimate node. We can do that by just calling the prev property on the tail! If the head is null, we return null. If the length is 1 we the store the head in a variable, set both head and tail to null and return that. If the length is greater than 1, we then set a variable equal to the tail and then set the tail to be equal to its prev property. We decrease the length of the list and finally return the popped node.

3. Unshift — This method is essentially the same as the singly linked list implementation, except that you need to set the prev property of the old head to be equal to the new head.

4. Shift — Also similar to the singly linked list implementation. The only difference here is that you’re setting the new head’s prev property to be set to null (since its prev property initially pointed to the old head).

5. Get — The get method is the one method that is the most different from its singly counterpart. Since we have a prev property on our nodes, this means that we can iterate from the head going forward OR from the tail going backwards. Why is this useful you ask? Well, if the list is hundreds of thousands or millions of elements long, it would be better to have started searching from the end of the list that is closest to the index you’re searching for then to just blindly start searching from the beginning. Therefore, we first check to see if the passed in index is less than or equal to the length of the list divided by 2. If it is then we start iterating from the head of the list forward, if it isn’t then we iterate from the tail of the list going backward.

6. Set — Exactly the same as the singly implementation.

7. Insert — Also similar to the singly implementation, except that you’re also setting a prev property on the nodes involved.

8. Remove — Also similar to the singly implementation, here we’re also setting a prev property on the nodes involved.

9. Reverse — The reverse implementation in a doubly linked list is slightly different than the singly implementation. You do not have to use a prev variable unlike the singly implementation, because you already have a prev property to utilize in the nodes themselves. Your solution ends up using the .prev on the current property to track the previous node.

Insights: Implications of The Structure of Both Linked Lists

Note: In order to fully comprehend this section, please make sure you have a solid understanding of Big O and it’s meaning in time and space complexity.

In this section of the article I’m going to discuss the implications the structures of each list have on Big O and why either type of linked list is useful. Below is a table that shows the Big O of singly and doubly linked lists.

The access or ‘get’ method is O(n) because at worst case we would have to iterate through n elements to access the element we’re looking to access. Since a linked-list is not accessed through index like it is in an array, we have to start iterating from the head or tail (depending on if the list is singly or doubly and where the index lies respective to the length of the list).

Search is the same as access, when searching for an element we will have to iterate through the list and hence we get worst case O(n) time.

Insertion / deletion in the table are listed as O(1), which is true when the method of insertion is an unshift, shift or push in a singly linked list or additionally pop in a doubly linked list. The pop method in a singly linked list is O(n), because we have to iterate through the whole list to get to the penultimate node.

Although reverse is not listed here, the reverse method has a Big O of O(n) in both types of linked lists, because you have to iterate through the whole list to reverse direction.

The space complexity is an important thing to note for doubly linked lists. The table lists the space complexity for doubly linked lists as O(n), which is indeed true due to the convention of dropping constants from ’n’, but one must realize that in essence a doubly linked list will use double in memory of what the singly linked list uses because it also has a previous pointer.

Depending on what sort of value you wish to derive from you data structure, you can use either singly or doubly. If space isn’t an issue and you want the fastest possible retrieval then you can use a doubly linked list. If you’re using a strict FIFO structure such as in a queue, then you might be better off with a singly linked list. Figuring out which data structure is best for your use case will involve you having to sit down and figure out which methods will be needed and the frequency of their use.

Stay tuned for more articles in the DS & A series!