Linked Lists

4 min readJul 30, 2021

I’ve recently taken some time to start learning different data structures. The first one I looked at is a Linked List. I’m going to walk through how to set up a Linked List class in Javascript and how to implement a few basic methods on the list.

Unlike arrays, which store values in accessible indices, Linked Lists have no indexes. Instead lists consist of Nodes which contain both the value and a reference or link to the next node. Therefore with Linked Lists we cannot access a value in the middle of the list without going through every single item until we get there. However, to insert or remove a value from the list it becomes much easier because we only need to change/update the references. With an array, inserting involves changing the index of every item after. So if you don’t need to access random elements, if you don’t know the size, or if you need constant-time for inserting/deleting, a Linked List is the way to go!

To set up a Linked List, we make two classes. The first is our Node class which will contain the value and a reference to the next node. The second is our LinkedList class which will set a head(first element in the list), tail (last element in the list) and length.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}class SinglyLinkedList {
    constructor() {
       this.length = 0
       this.head = null
       this.tail = null
    }
}let list = new SinglyLinkedList() 
//prints SinglyLinkedList {length: 0, head: null, tail: null, push: ƒ, pop: ƒ}let node = new Node("hello")
//prints Node {val: "hello", next: null}

Now that we have set up the basic structure of our two classes, we can work on a few methods that help handle our list including push, pop, shift and unshift.

push(val)

With our push method, we want to add a value to the end of our Linked List. We need to create a new Node with the value, store the current tail in a variable, reset the tail and update the references. That may sound confusing, but it is fairly simple. If the list has no elements, then you set the head and the tail to the newly created node, add 1 to the length and return the list. If there are items, then you point the current tail’s next to the newly created node and reset the tail.

push = (val) => {
        let node = new Node(val)
        if (!this.head) {
            this.head = node
            this.tail = this.head
        } else {
            this.tail.next = node
            this.tail = node
        }
        this.length += 1
        return this
    }

pop()

The pop() method should remove the last element in the list and return that element. First we need to account for if the list is empty and return undefined. Now we need to loop through all our elements in order to access the one right before the tail. This element will become the new tail. So we create loop while our current Node has a next assigned. Once we get to the last element, the loop will break (because the tail’s next is set to “null”). This now gives us the new tail, so we reset the tail to this value and set this new tail’s next to “null”. Finally we decrement the length. If removing the element made the list empty, then we can set the head and tail to “null” since they no longer exist.

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

shift()

Shift removes the first element in our list and returns it. Pretty simple. First if the head doesn’t exist, we return undefined since there is nothing to remove. Next we create a variable to store the current head. We reset the lists head to equal the old head’s next node. Then decrement the length (and if it now equals 0, we set the tail to “null”. Finally return the head we removed!

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

unshift(val)

Finally, unshift takes in a value that we want to add to the beginning of the list. We create a node using that value. Next, we check if there is already a head. If not, we set the head and tail to the node we created as it is the only element in the list. Otherwise, if a head did exist, we set our newly created node’s next to equal the current head and reset the list’s head to our newly created node. Increase the length and return the list.

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

There are plenty of other methods that you can implement to enhance Singly Linked Lists: get (retrieves a node at a certain index), set (changes the value at a certain index), remove (removes a node at a certain index), etc. It was fascinating to learn about another way to store data that in certain situations is even better than using arrays! Doubly Linked Lists are very similar except each node also has a link pointing to the previous node so you can traverse the list in either direction. Fun stuff!

Linked Lists

Written by Andrew Smoker