A crash course on Singly and Doubly Linked Lists: Single and ready to mingle or double the trouble?

In my own experience, singly and doubly linked lists have been a bit tricky to fully understand. On the surface, they appear as simple data structures. Under the surface, they require understanding how their design and nuances can lend to difficulty in programming robust and dynamic class methods. In understanding the core concepts and implementing this knowledge in class methods, creating new functions that use these data structures becomes much easier. So first, let’s start with the core building blocks of these lists: Nodes.

Nodes

Nodes are a basic data structure which contain data and one or more links to other nodes. Nodes can be used to represent a tree structure or a linked list. Nodes allow for the traversal from one node to another node.

Nodes contain two bits of information: data and link. The node stores data as a value and the link as a an address to another node. Think of the link as a pointer to the “next” node. In linking nodes, you can create an interconnected system that can be traversed on a path.

The link can also be null , meaning the node does not lead to any other node. This can be seen in node c, which has a null link and therefore points to no other nodes.

If a node has no other nodes pointing to it and contains no pointers to another node, the node is considered an orphan node. In the following example, node d is an orphan node because no other nodes point to it and its link pointer is null.

Now that we know what nodes are, let’s see how they are implemented as a class with some code:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }

  setNextNode(node) {
    if (node instanceof Node || node === null) {
      this.next = node;
    } else {
      throw new Error('Next node must be a member of the Node class.');
    }
  }

  getNextNode() {
    return this.next;
  }
}

Like any other Javascript class, the Node class consists of a constructor, as well as the necessary getter and setter methods. The constructor has a data parameter which can be passed a variety of data types as its argument. We use the this literal to access and set the data property to the provided data argument and as the default, set the next property — the constructed node’s link to other nodes — as null .

Then, we have a setNextNode method which has a node parameter and, therefore, receives an instance of the Node class. The first if statement checks to see if an instance of node is received as the argument, or an argument of null , accounting for the two possible things the next node can be set to. If the if statement evaluates to false, an error is thrown clarifying that the appropriate argument type must be used.

Finally, we have our getNextNode method which allows us to access the node instance’s next property, thereby returning the next node associated with the node that the method is called on.

Now that we have the understanding and code, let’s build a linked list with these nodes.

Single and Ready to Mingle: Singly Linked List

A linked list is a linear data structure where elements are not stored at contiguous location. This is different from arrays: the alternative to the linked list data structure. Linked lists comprise of nodes as their elemental building blocks, and these elements are linked together with pointers. Without pointers, we would have nodes floating around with no order and therefore no list.

A linked list comprises of the data and linked, inherited from the node, but now has a head, which is the first node of a linked list. The last node of a list is referred to as the tail.

The constructor of a singly linked list has an additional head property. For now, don’t worry about the tail not being a property. We’ll cover that later on in doubly linked lists.

const Node = require('./Node');

class LinkedList {
  constructor() {
    this.head = null;
  }
}

Adding to Head/Tail of Singly Linked Lists

Say you want to create a linked list and add a node to the beginning of the list, meaning the node added would precede the existing head. The code would look like this:

class LinkedList {
  constructor() {
    this.head = null;
  }

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

We first create a new instance of node for the new head, newHead . We then store the current head into a variable currentHead to reference it later. Because we are adding a node to the beginning of the list, this new node will become the new head, so we accomplish this in the line this.head = newHead; . If the linked list is empty, then the value of the head node is null . For that reason, we first check currentHead is not null in the next if statement to verify that we have a non-empty linked list and therefore a node to set as the next node. Then we set the head (remember, this already the new head) to point to the old head currentHead by using the setNextNode method from our Node class. This is important in ensuring we don’t have an error if we were to try to set the next node to something that doesn’t exist, like in the case of an empty list.

Another method we’ll need in our linked list class is one that would allow us to append a node to the end of a list. In other words, adding a node to the tail of the list. Let’s break down the code for that:

addToTail(data) {
    let tail = this.head;
    if (!tail) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }

Remember, singly linked lists are ready to mingle with the next node, but traversal only flows in one direction from head to tail. In order to get to the tail of the list, we must start at the head and iterative through until we satisfy a unique condition that lets us know we’ve made it to where we want to put the new node in. Since we know that tail is characterized by its next pointer being null, we can use this as the condition for our while loop. For that reason, our first step is to store a variable tail as the head to be the starting point for our journey to the tail. But before we set up a while loop, we have to think about what scenarios might exist when using this method. There exists the edge case of an empty list in which having no nodes and adding a new node to the tail would mean this new node also becomes the head. That is why we have our if statement to check if the tail we stored is a null value, in which case we set our new node as the head of the list, passing in our data argument in the node constructor. Then, we can move onto non-empty list scenarios and set up our while loop. The loop runs so long as the next node is not null, and in the body sets the tail to be the next node. This works similarly to a for loop traversing an array incrementing the index to move onto the next value and stopping when incriminator variable is less than the length of the array. So when the while loop condition is no longer met, the tail variable is at the tail and the next line outside the loop can run. Now we can finally set the next node to the new node being created, passing in our data argument.

The final class method I will explain is the method to remove the head:

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    return removedHead.data;
  }

Here we store the head we want to remove into the removedHead variable. As with our other cases, we want a method that would work with both empty and non-empty linked lists alike. Our if statement checks if removed head is a null value — and in the case that it is — the empty return breaks us out of the function, since there is no head to remove. The code that follows runs if the list is non-empty and makes the lists head to be the node that follows the head we want to remove. We then return the removed head’s data.

Double the Trouble: Doubly Linked Lists

Doubly linked lists have an extra layer of complexity to them that demand more care is taken to write its class methods and other functions, but nonetheless, provide a new value to linked lists in its functionality and applications.

While a singly linked list consists of nodes with links from the one node to the next, a doubly linked list also has a link to the node before it. These previous links, along with an added tail property, allow you to iterate backward through the list in the same way we were able to iterate forward through the singly linked list. Doubly linked lists are bi-directional which expands its real world applications. We can use it to represent a subway system or even web browser navigation forwards and backwards through pages.

With these new properties and now two pointers instead of one, our doubly linked list class constructor looks like this:

const Node = require('./Node');

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
}

Adding to Head/Tail of Doubly Linked Lists

Now our addToHead class method is a bit different:

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    if (currentHead) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;
    if (!this.tail) {
      this.tail = newHead;
    }
  }

One difference is that now when we run our first if statement for a non-empty list, we not only have to set the new head’s next pointer to be the current head, but we also have to set the current head to point to the new head, ensuring we have bi-directionality. Also, when working with an empty list, adding to the head would not only make the new addition the head, but also the tail, as is reflected in the body of the second if statement.

Let’s take a look at our new addToTail method as well:

addToTail(data) {
    const newTail = new Node(data);
    const currentTail = this.tail;
    if (currentTail) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;
    if (!this.head) {
      this.head = newTail;
    }
  }

You can see what was accounted for in adding to the head is also accounted for in adding to the tail. Due to how analogous the process is and cases to account for are, the code is same aside from the interchanging of head/tail.

Removing Head/Tail of Doubly Linked List

Again, removing the head of a doubly linked list is very similar to doing so for a singly linked list other than a couple of key differences due to the new properties and added direction.

removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    if (this.head) {
      this.head.setPreviousNode(null);
    }
    if (removedHead === this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }

The same logic of removing the head previously stated still applies in that we have to set the head’s next node to point to null, thereby removing the head. But now we have the tail property, which means that for a list consisting of one node, removing the head would also mean removing the tail. The second if statement checks is the head we’re removing is equivalent to the tail, and calls on a removeTail method, shown below:

  removeTail() {
    const removedTail = this.tail;
    if (!removedTail) {
      return;
    }
    this.tail = removedTail.getPreviousNode();
    if (this.tail) {
      this.tail.setNextNode(null);
    }
    if (removedTail === this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }

Likewise, the approach here is like that for singly linked lists, but in removing the tail, we must also check if the head and tail are the same so that we can call on the removeHead method. These removal methods call on each other for the instance of a singular node linked list. As you can see, understanding how the properties and function of the data structures lends to different cases is important in writing methods that can perform for any instance it is called on.

Linked list classes typically also contain a method for removing a node based on its data (allowing you to target a node and remove it by changing the surrounding/relevant pointers), but I will leave you to write that one for yourself as a great way to continue to explore the approaches for linked list methods. Whether a linked list has nodes mingling with only one node or engaging with two, it is a powerful data structure for modeling real world situations and coming up with resourceful solutions.