Linked Lists

In the styling of comedy great, Jerry Seinfeld, “Whats the deal with linked lists?”. Well, Jerry, much like an array, linked lists are a data structure used to store elements. However, unlike an array, elements in a linked list are not stored in contiguous memory locations. Instead, each element(or node) holds a reference to the next element in line. In other terms, a linked list consists of nodes where each node contains data and a reference(or link) to the next node in the list.

*Note — this article examines Single Link Lists*

Getting Started

Linked lists are generally represented using arrows, with each data in between being a node, looking something like this.

4 -> 3 -> 7 -> 12 (-> null)

Nodes can be thought of has having two attributes: data and points to. In this example:

data is 4, points to 3
data is 3, points to 7
data is 7, points to 12
data is 12, points to null

The first node is commonly referred to as the head, and the last node, the tail. Each node has a value and points to a next node. If the node is the tail, and there is no subsequent node, it can be said that that node points to null.

To create a linked list in JavaScript, let’s first create a Node Class that looks like this.

class Node {
    constructor(element){
        this.element = element  // holds data of the current node
        this.next = null       // holds pointer to next node
    }
}

Now that our node is created, lets create a LinkedList Class.

class LinkedList {
    constructor(){
        this.head = null  // no first node exists
        this.size = 0    // since no nodes, size is 0
    }
}

Adding Nodes to Linked List

Now that we have a structure in place, let’s add nodes! Within our LinkedList Class, we’d add this function

addElement(element){
    let node = new Node (element)     //creating a new node
    let current;                     //assigning for later use
    
    //if there is no head, make this node the head
    if(this.head === null){
        this.head = node} 
    else {
        //let current node be equal to the head node
        current = this.head
        //while there is a next node
        while(current.next){
            //assign the current node to be the next node in order  
            current = current.next
        }
        //create new node to be the next of the newly formed current 
        current.next = node
    }
    //increase the size by one
    this.size++
}

Deleting Nodes

removeElement(element){
    let current = this.head
    let previous = null
    //while the current node isn't empty
    while(current !== null){
        //if current node is the node to delete
        if(current.element === element){
            //if current node is head
            if(previous.next === null){
                //assign the next node as the new head
                this.head = current.next
            } else 
                //since current node is being deleted, the reference   for it's next node now needs to be the next reference for the previous node
                previous.next = current.next
            }
            //subtract one from the total size
            this.size--
            //return the deleted node
            return current.element
        }
        //the previous node now becomes the current
        previous = current
        //shift the list down one
        current = current.next
    }
    //if element is not found
    return - 1
}

Summary

This may seem like a lot of code, boilerplate, and unnecessary work. Why go through all this trouble if we can just use an array? It’s all about time complexity. While accessing elements in array is fast, inserting or deleting can take more time, since each subsequent element would then need to be adjusted. Since linked lists nodes only hold a connection to the next link, to insert or delete a node, only the information for two nodes would needs to be changed, not the whole list. Linked lists also have the additional benefits of dynamic and flexible size, when memory is allocated during run time, and memory utilization.

As always, when to use certain data sets if specific to the application and use case. So, play around with linked lists and enjoy. Happy coding!