Singly Linked List

This week I want to take a deep dive into Singly Linked Lists. A Singly Linked List is a linear data structure that uses pointers that reference the next element in the list.

Structure and Terminology

A single data item in a Singly Linked List is called a node. A node will store two things:

1. A Value (I will use val), which is the thing you want stored
2. A Next reference (I will use next), which is the pointer that references the next item in the list

As for the list itself, it will always keep track of something called the head, which is simply the node that starts the Linked List. The head's next will point to the next item in the Linked List, and then that node's next will point to the next item in the Linked List, and so on. The final node in the list is called the tail, and its next will simply be set to null.

Sometimes, in addition to tracking the head, a Linked List will also keep track of its tail. This is definitely not necessary, and with certain Linked List implementations it may be more trouble than it's worth. While keeping track of the tail doesn't take up a lot of memory, it does add extra steps when you're implementing certain operations, like insertion or deletion within the list. I will be implementing a Linked List that tracks its tail.

Finally the last thing that most Linked Lists will keep track of is the size of the list, usually saved as size or length. I'll be using length here. I think I like it as a carry-over from Arrays.

So what does a Singly Linked List look like? Here's a very basic example:

1 -> 10 -> 100 -> 1000

In this little example, each number represents a node within the list, and for each node, the number represents that node's value, and the arrow represents the next pointer reference. 1 would be the head of the list. Its next would reference 10. Then 10's next would reference 100. Then 100's next would reference 1000. Finally, 1000's next would be set to null, making it the list's tail. The length of the list is 4, as there are 4 items in the list.

Linked List vs. Array

So how does a Linked List differ from an Array, and what are its benefits? The big, glaring difference is that there is no native Linked List data structure in JavaScript. Arrays come bundled in with the language, along with a host of useful methods that have been tried in real-world applications for decades. With a Linked List, you need to create the Linked List data structure yourself, as well as implementations for things like insertion, deletion, or fetching. All of this before you even have a Linked List that you can use.

Beyond that, an Array requires contiguous memory to store all of its items. This can be very demanding if you have a huge array with thousands of items. A Linked List, however, doesn't need all of its nodes to be store in the same place, they just need to point to one another. This allows for Linked Lists to have dynamic size within memory, which is usually a benefit.

Another huge difference between the two data structures is in how you access individual items in them. As a trivial example, say you have an Array that has 5 items, and a Linked List that has 5 items, each holding the same values.

Array:
const arr = [10, 20, 30, 40, 50]

Linked List:
const list = 10 -> 20 -> 30 -> 40 -> 50

Now say that you want to access the 4th item of the Array, which is the item at index 3. You can simply pass it that index and retrieve it, which looks like arr[3].

There is no indexing in Linked Lists, though. Remember that a list only keeps track of its head and its length, and sometimes its tail. Instead, you need to have some mechanism that starts at the head, and keeps count of how many items you have looked at.

Imagine we have a while loop, where each iteration looks at an item in the Linked List, starting with the head. On the first iteration, 10 is the head that we're looking at. We've looked at 1 item. On the second iteration, we move onto the next value, which is 20. We've now looked at 2 items. On the third iteration, we move onto the next item, which is 30. We've now looked at 3 items. On the fourth iteration, the next item is 40, which is 4 items. We wanted the fourth item in the Linked List, so we can exit our while loop and return 40.

All of this is to illustrate that there is no random access in Linked Lists. Arrays index their items, making it easy to grab data from anywhere in the list, but in a Singly Linked List, in the worst case scenario the value you're looking for is found at the end of the list, so you have to iterate through the entire list, resulting in a time complexity of O(n) for Access.

Speaking of indexing though, you may recall that indexing is what makes insertion into an Array an expensive operation, especially if you are adding items to the beginning of the Array. The .unshift() method that adds something to the beginning of an Array requires re-indexing the entire rest of the Array.

let arr = [10, 20, 30, 40, 50];

arr.unshift(1); // we have to re-index everything in the array!!

The Linked List doesn't have this difficulty. If we're inserting at the start of the list, it's simply a matter of updating the list's head property, or if we're working in the middle, the next property of the node that will be referencing the new node. Since it's only a couple of operations, Insertion is incredibly easy in a Linked List, achieving a Time Complexity of O(1). Deletion is also very easy in a Linked List (and difficult in Arrays) for the same reason.

Singly Linked List vs. Doubly Linked List

Finally, I want to distinguish the Singly Linked List from a Doubly Linked List. A Singly Linked List always keeps track of a head, and each node has a next pointer that references the next item in the list. That item has a next that references another item, and so on until we reach the tail, whose next property is set to null.

The nodes in a Doubly Linked List, on the other hand, will also have a prev pointer, which points to the previous item in the list. So the second item in the list has a prev reference that points to the head as well as a next reference that points to the third item. So in a Singly Linked List you can only start at the head and work in the direction of the tail, a Doubly Linked List allows you to also start at the tail and work backwards towards the head. This makes certain operations much easier, but it also adds to the memory needed for each node and means you need to keep track of more pointers if you're adding or deleting items.

I'll likely be writing about Doubly Linked Lists soon, so I won't go into more detail here. For the purposes of this post when I say "Linked List" or "list" (outside of this section) I'll be referring to a Singly Linked List.

Big O of a Singly Linked List

Insertion: Inserting things is really easy on a Singly Linked List. If we're adding the new item to the end of the list, we simply reassign the tail (that is, as long as the list keeps track of its tail). If we're adding it to the beginning, we reassign the head. Otherwise if we're inserting it into the middle of the list, we just need to make a new node and reassign the next pointer of the item before it. It doesn't matter if the list is 10 items or 10000 items. Contrast this with an Array, where adding something at the beginning means re-indexing every subsequent item in the Array.

Removal: It depends on where in the list we're removing the item from. If we're removing from the very beginning, it's O(1) as it's a simple matter of rea-ssigning the head. However, if we're removing from the very end, we need to traverse the entire Linked List to get to that last element. Even if we're keeping track of the tail, we will need to find the item before the tail, since that is what will become the new tail. That requires traversing the whole list.

Searching: In the worst case scenario, we need to look at every single item in the list to see if the desired value is present.

Access: Same as searching. As the list grows, so does the number of operations. Compare this to an Array, where Random Access is allowed; the indexing takes time, but if you have the index, it's much simpler to find an indexed item.

Singly Linked List Implementation

Here's the full implementation for future reference. Sections below will detail each method.

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }
    var counter = 0;
    var current = this.head;
    while (counter !== index) {
      current = current.next;
      counter++;
    }
    return current;
  }
  insert(index, val) {
    if (index < 0 || index > this.length) {
      return false;
    }
    if (index === this.length) {
      return !!this.push(val);
    }
    if (index === 0) {
      return !!this.unshift(val);
    }
    var newNode = new Node(val);
    var prev = this.get(index - 1);
    var temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
  pop() {
    if (!this.head) {
      return undefined;
    }
    var currentTail = this.head;
    var newTail = currentTail;
    while (currentTail.next) {
      newTail = currentTail;
      currentTail = currentTail.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return currentTail;
  }
  push(val) {
    var newTail = new Node(val);
    if (!this.head) {
      this.head = newTail;
      this.tail = this.head;
    } else {
      this.tail.next = newTail;
      this.tail = newTail;
    }
    this.length++;
    return this;
  }
  remove(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }
    if (index === 0) {
      return this.shift();
    }
    if (index === this.length - 1) {
      return this.pop();
    }
    var prev = this.get(index - 1);
    var removedNode = prev.next;
    prev.next = removedNode.next;
    removedNode.next = null;
    this.length--;
    return removedNode;
  }
  reverse() {
    var node = this.head;
    this.head = this.tail;
    this.tail = node;
    var next;
    var prev = null;
    for (var i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }
    return this;
  }
  set(index, val) {
    var foundNode = this.get(index);
    if (foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }
  shift() {
    if (!this.head) {
      return undefined;
    }
    var currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }
  unshift(val) {
    if (!this.head) {
      this.push(val);
    } else {
      var newHead = new Node(val);
      newHead.next = this.head;
      this.head = newHead;
      this.length++;
      return this;
    }
  }
}

I'd like to note that this is just one of many ways to implement a Linked List. Different implementations will have methods that work in different ways or return different values. .get() for example here returns the node itself that you're looking for. I have seen other .get() methods that return the value of the node instead. That's okay.

There is also optimization to be achieved here. What I'm aiming for is an exploration of the concepts behind a Linked List — if you know how to properly traverse the list using multiple pointers to find what you're looking for, and what it takes to add and remove values within the list then that is the important thing.

Operations like .pop(), or .shift() can be simplified with the use of the .get() method (and I do use .get() in the .set() and .insert() methods as an example), but I've written the methods here in a way (and detailed them below in an order) that I hope can help teach the fundamentals of working within a Singly Linked list.

Let's break it apart into smaller pieces and methods to figure out what's going on for each method.

Node Class

Each item within the Linked List is called a node. Any time we add a node into the Linked List, we'll do it using a Node Class. This class accepts a value, val, and also has a next property. By default next will be assigned the value of null, but we'll commonly be assigning next to point to another node in the list.

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

Singly Linked List Class

We'll also use a Singly Linked List Class to initialize the list itself. We're starting here just with its constructor, but we'll add in all of the needed methods as we go. On initialization, an empty Singly Linked List will have a head set to null, a tail also set to null, and a length set to 0.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

Methods and Operations

.push()

The first method we'll introduce is the .push() method, which adds a new node to the end of the linked list, in practical terms creating a new tail. This method accepts a value, val, that we want to attach to the end of the list.

Here are the steps we take to create the .push() method:

1. Create a new node with the value val. I'll store this in a variable called newTail
2. Check if the list is empty. We'll know we have an empty list if the list has no head
3. If the list is empty:
   1. Assign the new node as the head
   2. Assign the tail to also equal the head
4. If the list isn't empty:
   1. Set the current tail's next to equal the new node
   2. Assign the new node as the tail
5. Increment the length by 1
6. Return the list

.push() Implementation

push(val) {
  var newTail = new Node(val);
  if (!this.head) {
    this.head = newTail;
    this.tail = this.head;
  } else {
    this.tail.next = newTail;
    this.tail = newTail;
  }
  this.length++;
  return this;
}

.pop()

Now let's look at the .pop() method, which removes a node from the end of the Linked List. Unfortunately this method is kind of complicated, but I'll walk you through it.

1. Return undefined if the list is empty (again, if there's no head then it's an empty list)
2. We need to iterate through the list and find two things:
   • The current tail
   • The item that comes right before the current tail. This will become our new tail
3. Create two variables:
   1. currentTail - set this to equal the list's head
   2. newTail - set this to equal currentTail
4. Create a while loop that iterates as long as there is a currentTail.next. Within this loop:
   1. set newTail to equal currentTail
   2. set currentTail to equal currentTail.next
   • Once currentTail.next = null, our loop stops running. currentTail is equal to the current tail and newTail is equal to the item right before the current tail.
5. Set the tail to equal newTail
6. Set tail.next to equal null, breaking the link between this node and the old tail
7. Decrement the length by 1.
8. If length is now equal to 0, then we have now have an empty list, meaning we need to:
   1. Set the head to equal null
   2. Set the tail to equal null
9. Finally, return the node that we have removed from the list. Remember that this old tail is stored in the currentTail variable

.pop() Implementation

pop() {
  if (!this.head) {
    return undefined;
  }
  var currentTail = this.head;
  var newTail = currentTail;
  while (currentTail.next) {
    newTail = currentTail;
    currentTail = currentTail.next;
  }
  this.tail = newTail;
  this.tail.next = null;
  this.length--;
  if (this.length === 0) {
    this.head = null;
    this.tail = null;
  }
  return currentTail;
}

.unshift()

Let's now look at the .unshift() method, which adds a new value to the beginning of the Linked List. Fortunately for us this is very similar to the .push() method, but instead of reassigning the tail, we're reassigning the head.

1. Create a new node with the value val
2. Check if the list is empty. We'll know we have an empty list if the list has no head
3. If the list is empty:
   1. Assign the new node as the head
   2. Assign the head to also equal the tail
4. If the list isn't empty:
   1. Set the new node's next to point to the list's current head
   2. Assign the new node as the head
5. Increment the length by 1
6. Return the list

.unshift() Implementation

unshift(val) {
  var newHead = new Node(val);
  if (!this.head) {
    this.head = newHead;
    this.tail = this.head;
  } else {
    newHead.next = this.head;
    this.head = newHead;
  }
  this.length++;
  return this;
}

.unshift() Optimization

I want to go a step further and optimize this code a little bit. If there is no head and the list is empty, we can simply use the .push() method, since that would take care of the logic of assigning the head and tail. The rest of the logic would remain the same. This is completely optional, but I want to introduce the idea of using methods we've already written. This allows us to not have to repeat logic within our code, and some of the methods below will use several pre-written methods.

.unshift() Optimized Implementation

unshift(val) {
  if (!this.head) {
    this.push(val);
  } else {
    var newHead = new Node(val);
    newHead.next = this.head;
    this.head = newHead;
    this.length++;
    return this;
  }
}

.shift()

Now let's remove an item from the beginning of the list with a method called .shift(). This is much, much easier than the .pop() method.

1. Check again if the list is empty (this should be familiar by now). If so, return undefined
2. Store the current list's head in a variable named currentHead
3. Set the list's head to equal currentHead's next
4. Decrement the length
5. If length is now equal to 0, then we now have an empty list, meaning we need to set the tail to equal null
6. Return the old head that we have removed, which is stored in currentHead

.shift() Implementation

shift() {
  if (!this.head) {
    return undefined;
  }
  var currentHead = this.head;
  this.head = currentHead.next;
  this.length--;
  if (this.length === 0) {
    this.tail = null;
  }
  return currentHead;
}

.get()

.get() is a handy method that can retrieve a node at a specific index within the list. We'll be using it below in the .set() and .insert() methods, and could even likely use it in some of the methods we've written above.

.get() accepts an index, which corresponds to a place within the list. Like an array, the first item in the Linked List is at index 0, the second item is at index 1, the third item is at index 2, and so on.

1. Check to make sure the index is valid. If the index is invalid, return undefined. The index is invalid if:
   1. It is a negative value
   2. It is greater than or equal to the length of the list. If a list is 3 items long, then the highest index is 2. If the list is 100 items long, then the highest index is 99
2. Now we need to traverse the list. Set a counter variable equal to 0, and a current variable equal to the list's head
3. Within a while loop, check whether counter is equal to index. If not:
   1. Set current equal to current.next
   2. Increment counter by 1
4. Once counter is equal to index, current will be equal to the node that we're looking for. Return this node.

.get() Implementation

get(index) {
  if (index < 0 || index >= this.length) {
    return undefined;
  }
  var counter = 0;
  var current = this.head;
  while (counter !== index) {
    current = current.next;
    counter++;
  }
  return current;
}

.set()

.set() accepts an index and a value, val, and changes the value of the node at that index to val. We once again need to make sure that the index is valid, and then iterate through the list to the correct item. But luckily for us, the .get() method takes care of that logic for us.

1. Use the .get() method to retrieve the node at the provided index. Store this in a variable named foundNode
   1. .get() will return undefined for us if it's an invalid index
   2. .get() will also do all of the iteration for us
2. If .get() returns our foundNode:
   1. Set foundNode's val to the val that was passed to the .set() method
   2. Return true
3. Otherwise, return false

.set() Implementation

set(index, val) {
  var foundNode = this.get(index);
  if (foundNode) {
    foundNode.val = val;
    return true;
  }
  return false;
}

.insert()

The next method we'll work on is .insert(), which takes an index and a value, val. This method will insert val into the list at the desired index, shifting the item that was previously at that index later into the list. This method will return false if the index passed is invalid, or true if the index is valid and the insertion is done successfully.

1. Check to make sure the index is a valid number. This is the same as above. Return false if it is an invalid index.
2. If the index is equal to the list's length property, then we can just use the .push() method to add val as the new tail
   • We can use a !! double bang operator to return true after using the .push() method
3. If index is 0, then we can just use the .unshift() method to add val as the new head
   • We can use a !! double bang operator to return true after using the .unshift() method
4. If we've gotten this far, then the index is somewhere in the middle of the list and we can't just rely on the other methods we've written so far
5. Create a new node with the value val, and assign it to a variable named newNode
6. Retrieve the node right before the item currently located at index, and assign it to a variable named prev. We can use the .get() method and pass it index - 1 to achieve this
7. Retrieve the node currently at located at index (same as prev.next), and assign it to a variable named temp
8. Set prev's next pointer to reference newNode
9. Set newNode's next pointer to reference temp
10. Increment length by 1
11. Return true

.insert() Implementation

insert(index, val) {
  if (index < 0 || index > this.length) {
    return false;
  }
  if (index === this.length) {
    return !!this.push(val);
  }
  if (index === 0) {
    return !!this.unshift(val);
  }
  var newNode = new Node(val);
  var prev = this.get(index - 1);
  var temp = prev.next;
  prev.next = newNode;
  newNode.next = temp;
  this.length++;
  return true;
}

.remove()

Now let's look at the .remove() method, which accepts an index, removes the item at that index from the list, and returns the removed node. Fortunately this logic is very similar to .insert().

1. Check if it's a valid index. If it's not, return undefined
2. If index is 0, we can just use the .shift() method to remove the current head
3. If the index is equal to length - 1, we can just use the .pop() method to remove the current tail
4. Otherwise we need to go about removing a node from the middle of the list
5. Retrieve the node right before the item that we want to remove, and assign it to a variable named prev. We can use the .get() method and pass it index - 1 to achieve this
6. Retrieve the node currently at located at index (same as prev.next), and assign it to a variable named removedNode
7. Set prev's next pointer to refer to removedNode.next
8. Set removedNode's next to null, breaking the reference between the node you're removing and the list. This way the removedNode does not present a false head
9. Decrement length by 1
10. Return the node we removed, currently stored in the removedNode variable

.remove() Implementation

remove(index) {
  if (index < 0 || index >= this.length) {
    return undefined;
  }
  if (index === 0) {
    return this.shift();
  }
  if (index === this.length - 1) {
    return this.pop();
  }
  var prev = this.get(index - 1);
  var removedNode = prev.next;
  prev.next = removedNode.next;
  removedNode.next = null;
  this.length--;
  return removedNode;
}

.reverse()

Well here we go with our last method on the Singly Linked List. We're going to write the method to reverse our Linked List in place. This is a common tech interview question. It's not something that is likely done a whole lot in real world applications, but being able to illustrate how a list reversal is done demonstrates an understanding of the concepts behind a Singly Linked List and effectively using numerous pointers to keep track of data as you move it around. If SEO brought you here and you're reading this, welcome. I hope you find value in the rest of this post, as well as my other blog posts 🙂.

So here are some (probably poorly written) instructions for the .reverse() method:

1. Swap the head and the tail:
   1. Store head in a temporary node variable
   2. Assign the head to equal the tail
   3. Assign the tail to equal the temporary node variable
2. Create a next variable, but do not assign anything to it
3. Create a prev variable, assigned the value of null
4. Loop through the length of the list. Within this loop:
   1. Set the next variable to equal the temporary node's next value
   2. Set the temporary node's next to equal prev
   3. Set prev to equal what's currently in the temporary node variable
   4. Assign the temporary node to equal next
5. After the loop has finished, return the list, which will now be reversed

Step By Step Example of Linked List Reversal

So what's going on here? Let's slow down and walk through this with an example, following our variable names.

Here is our initial list:

10 -> 20 -> 30 -> 40 -> 50
- head: 10
- tail: 50

We start by swapping the head and tail, using a temporary node variable along the way.

var node = this.head;
this.head = this.tail;
this.tail = node;

Our list stays the same, but head and tail assignments have swapped. node still points to 10, which still has a next property that points to 20, which still has a next property that points to 30, and so on.

We also initialize prev and next variables. next can be left as undefined for now (but we immediately assign it at the start of each iteration of the loop), and prev can be set to null (this is where the new tail's next reference will point).

So as things currently stand, before we start our for loop, here is our list, and each of the variables:

10 -> 20 -> 30 -> 40 -> 50
- head: 50
- tail: 10
- node: 10
- prev: null
- next: (undefined)

Now we start looping. We immediately assign next to be node.next, storing the second item in the list into this temporary next variable. We reassign node.next to point to prev, so 10's next points to null.

null <- 10    20 -> 30 -> 40 -> 50
prev    node  next

So now all we have to do is move prev up to equal node, and move node up to equal next (this step is why we created the temporary next variable), which leaves us with the following:

null <- 10    20 -> 30 -> 40 -> 50
        prev  next
              node
- head: 50
- tail: 10
- node: 20
- prev: 10
- next: 20

That's it for our first iteration, and we move onto the second iteration. We once again assign next to be node.next, storing the third item in the list into the temporary variable. We reassign node.next to point to prev, so 20's next points to 10.

null <- 10 <- 20    30 -> 40 -> 50
        prev  node  next

Now we simply move prev up by setting it equal to node, and then move node up by setting it equal to next. This leaves us with the following:

null <- 10 <- 20    30 -> 40 -> 50
              prev  next
                    node
- head: 50
- tail: 10
- node: 30
- prev: 20
- next: 30

Now onto our third iteration. We reassign next to equal node.next, storing 40 into the temporary variable. We then reassign node.next to point to prev, so 30's next points to 20.

null <- 10 <- 20 <- 30    40 -> 50
              prev  node  next

With next reassigned, it's time to move up prev and node by setting prev equal to node and node equal to next. This leaves us with the following:

null <- 10 <- 20 <- 30    40 -> 50
                    prev  next
                          node
- head: 50
- tail: 10
- node: 40
- prev: 30
- next: 40

Hopefully the pattern is becoming clear now as we move onto the fourth iteration. We reassign next to equal node.next, storing 50 into the temporary variable. We then reassign node.next to point to prev, so 40's next points to 30.

null <- 10 <- 20 <- 30 <- 40    50
                    prev  node  next

Then we move prev and node up in the same manner as before.

null <- 10 <- 20 <- 30 <- 40    50
                          prev  next
                                node
- head: 50
- tail: 10
- node: 50
- prev: 40
- next: 50

Now it's time for our last iteration!! Move next. Remember that 50's next was previously null. Then set node.next to equal prev, making 50's next point to 40.

null <- 10 <- 20 <- 30 <- 40 <- 50    (null)
                          prev  node  next

Finally we move up prev and node one more time.

null <- 10 <- 20 <- 30 <- 40 <- 50    (null)
                                prev  next
                                      node
- head: 50
- tail: 10
- node: null
- prev: 50
- next: null

That's the end of our loop, and since waaaaaay back before the loop we reassigned the head to be 50 and the tail to be 10, our list has been fully reversed in place. We simply need to return the list:

return this;

With that, we get a list that looks like the following:

10 <- 20 <- 30 <- 40 <- 50

Whew, that was a lot! Now let's put it all together. And remember, this Linked List Reversal implementation is entirely dependent on how we have set up our Linked List, which tracks not just the head, but also the tail and the length. Other Linked Lists may not have these latter two properties, so solutions there would have some differences.

.reverse() Implementation

reverse() {
  var node = this.head;
  this.head = this.tail;
  this.tail = node;
  var next;
  var prev = null;
  for (var i = 0; i < this.length; i++) {
    next = node.next;
    node.next = prev;
    prev = node;
    node = next;
  }
  return this;
}