Intro to Linked Lists in JS

Overview

"A linked list is an ordered collection of data. The collection contains a number of different nodes. Each node contains some amount of data along with a reference to the next node. When we put a handful of these nodes together we refer to it as a linked list as it literally is a list of nodes linked together. We will also frequently refer to it as a chain. The list of nodes that form the chain has an order that won’t suddenly or randomly change, unless we want to change it of course. In every Linked List there are two special nodes; the head and the tail. The head node is always the very first node of the list. The tail node is always the very last node of the list. The tail node can always be identified by the fact that it does not have a reference to ANY other node."

The data that can be contained in the node can be absolutely any data type we want; string, number, array, object, any type of JS value can be contained in these nodes. The other part of the node is a reference to the next node.

There are pro's and con's of using linked lists. Check out this Quora forum on it!

I believe the best way to learn Linked Lists (and most data structure/algorithm questions) is to actually practice them yourself. Pop open a repl and let's start by creating the most basic Linked List we can.

const nodeOne = {
  data: "Hi"
}

const nodeTwo = {
  data: "Sofia"
}

nodeOne.next = nodeTwo

console.log(nodeOne) // => { data: 'Hi', next: { data: 'Sofia' } }

Essentially, we have just created our very own linked list... I really encourage you to do it yourself and see how it works as we are going to get a bit deeper here.

As we said before, a linked list is made up of nodes. This sounds like something we can break out. So, let us create Node and LinkedList functions. But, before I write this out... think about what these functions might contain. Well, we know a node has it's data and a reference to the next node. AND (for starters) we know that a linked list has a head. Boom! Let's start right there.

function Node(data, next = null) {
  this.data = data,
  this.next = next
}

function LinkedList() {
  this.head = null
}

Now, let's experiment with our linked list a little bit and perform some actions on it. Here I am going to use Prototype Delegation. If you are not certain what that is, I would highly recommend diving into the pros, cons, and differences of class vs prototypal inheritance here at some other time, but don't worry... you can still follow along.

Also, I might add, there are plenty of ways to do this and if you do it another way I would love to hear why.

The first thing we want to be able to do is to add a node to the front of our list. At this point, I am assuming you are following along in a repl.

Let's create a function addToFront that sets the head of the linked list to our new node!

LinkedList.prototype.addToFront = function(data) {
  this.head = new Node(data, this.head)
}

let list = new LinkedList()
let node = new Node(5)
list.head = node
list.addToFront(10)
console.log(list) // => LinkedList { head: Node { data: 10, next: Node { data: 5, next: null } } }

// You should continuously be testing in your repl like above ^^

Now, maybe we want to check the size of our linked list. We can create a function called size that counts every node in our list!

LinkedList.prototype.size = function() {
  let counter = 0
  let node  = this.head

  while (node) {
    counter++;
    node = node.next
  }
  return counter
}

Notice we use a while loop here. This is a really nifty technique that will come in handy for a lot of the other problems. We set the counter and then the node variable to the first node. While there is a node in our list (or until node === null) we increase the counter while simultaneously resetting our node variable to the next node in the list. Finally we return the counter.

Maybe we want to have different functions that will retrieve the first and last nodes. So, we create retrieveFirst and retrieveLast functions. For the sake of space, retrieving the first node would just be returning this.head, so we will not write that out, but you should. However, for retrieveLast we will have to do something somewhat similar to our size function.

LinkedList.prototype.retrieveLast = function() {
  let node = this.head
  if (!node) {
    return null
  }

  while(node) {
    if (node.next === null) {
      return node
    }
      node = node.next
  }
}

All we are trying to do is to return the last node in our list... the tail. But, if there is no first node, we return null. If there is, we get into our while loop only this time we make sure to check if the next node is there. If there is no reference to the next node, we know we have hit the tail and we return it.

Maybe we want to delete our entire linked list all together, or at least clear it up. Let's create a method called erase. This is actually a lot easier than it may seem. We know that a linked list begins with a head, which references the next node and so on. What if we just cut the head off of the monster?! If there is no initial reference point for the linked list, then it will be gone. Try it out.

LinkedList.prototype.erase = function() {
  return this.head = null
}

On the same note, what if we wanted to just remove the first node/head?

First, we would want to check if there even is one to remove. Then we could just make that first node equal to the next one!

LinkedList.prototype.removeFirst = function() {
  if (!this.head) {
    return;
  }
  return this.head = this.head.next
}

We are rollin' now! How about a few slightly more difficult ones?

Let's delete the last node and let's also try to create a new tail node. To delete the last node we first need to take care of a few edge cases. 1) We want to make sure that there is a head node and 2) we want to make sure that if there is only one head node that we just return null. After that there are a few different ways to do it, but I will walk you through the one that makes the most sense to me.

LinkedList.prototype.deleteLast = function() {
  if (!this.head) {
    return;
  }

  if (!this.head.next) {
    return this.head = null
  }

  let previous = this.head
  while(previous) {
    let node = previous.next
    if (!node.next) {
      return previous.next = null
    }
    previous = previous.next
  }
}

After our checks, we are setting two variables; the previous node that starts at the head and the node that will always be in front of the previous one. We want to continue our loop while there is a node there and once the reference to next node is null we know we have reached the last node and we will want to delete that node.

Aaaand finally if we are going to delete the last node, we might as well be able to add to the last node as well. I'll show you one final wrinkle. Above we created a prototype delegation method called retrieveLast(). Let's make it easy on ourselves and use this to find the last node to add onto.

Also, we will need to create a new Node here as we are adding one on, so our function will take in data. We then will set our retrieveLast() function to a variable. Finally, we will want to make sure the linked list isn't empty. If it is, we will set the new node to be the head, if not, we set it to last.next.

LinkedList.prototype.insertLast = function(data) {
  const newNode = new Node(data)
  const last = this.retrieveLast()

  if (last) {
    last.next = newNode
  } else {
    this.head = newNode
  }
}

Conclusion

Thanks for following along! I hope this helped and that you learned a little bit about linked lists for starters :)!

References

Check this great course out!