Pre-requisites: This post requires basic knowledge of Javascript and object-oriented programming.

Why care about linked lists?

Linked List is one of the most important data structures out there. You might think why bother learning about linked lists when arrays do the trick. However, linked lists help us overcome many disadvantages of arrays. So before we can talk more about linked lists, let's see some of the disadvantages of arrays.

Disadvantages of arrays

Although Javascript arrays offer fast lookups, certain operations like inserting elements at the beginning of the array have O(n) time complexity. Moreover, arrays store elements in contiguous memory locations. Linked lists, on the other hand, are less rigid in the storage structure and may not store the elements in contiguous memory locations.

Linked Lists

A linked list is a linear data structure that represents a collection of nodes. Before we can jump into the implementation, here are some key pointers about linked lists:

• The main properties of a linked list are:

size : This represents the total elements present in the linked list.

head : The head points to the first node in the linked list.

• The last node in the linked list points to null.

• A linked can grow and shrink in size dynamically during the execution of the program.

• Unlike arrays which stores data in contiguous memory locations, linked lists allow you to add and delete nodes from the list without having to reorganize the entire data structure.

Now that we know some of the key pointers, let's implement a linked list in JavaScript.

A node includes a data value and a pointer to the next element in the linked list.

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

In the above code snippet, we have created a class Node which takes data as an argument and is initialized when an object is instantiated. node holds the pointer to the next node and is initialized to null by default.

Now, let's implement a Linked List class.

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

The linked list is instantiated with the head pointing to null initially. Therefore, whenever the head points to null, we can consider the linked list to have no elements. We also have a size data member which will be initialized to 0. Now that we have created a class for our linked list, let's create the methods to perform operations on the linked list.

Operations on Linked Lists

append(data) - This method adds an element to the end of the linked list.

    append(data) {
        let node = new Node(data);
        //checking if the LL is empty
        if (this.head === null) {
            this.head = node;
        } else {
            let temp = this.head;
            while (temp.next) {
                temp = temp.next;
            }
            temp.next = node;
        }
        //increase size
        this.size += 1
    }

insertAt(data) - This method adds an element at a specified position in the linked list. Therefore the method will accept two parameters: data and index. If the index is valid, we will traverse until the index and then insert the value.

insertAtIndex(data, index) {
    if (index < 0 || index > this.size) {
        throw Error("Invalid index")
    }
    let node = new Node(data);
    if (index === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        let current = this.head;
        let prev;
        let it = 0;
        while (it < index) {
            it++;
            prev = current;
            current = current.next
        }
        node.next = prev.next;
        prev.next = node;
    }
}

removeFrom(index) - This method removes an element from the specified index and returns the deleted element.

removeFrom(index) {
    if (index < 0 || index > this.size) {
        throw Error("Invalid index")
    }
    let it = 0;
    let current = this.head;
    let prev;
    while (it < index) {
        it++;
        prev = current;
        current = current.next;
    }
    let data = current.data;
    prev.next = current.next;
    this.size--;
    return data;
}

Now that we have defined some operations on the linked list, let's create some helper methods.

Printing all elements of the linked list:

printAll() {
      let temp = this.head;
      let allElements = "";
       while (temp) {
           allElements += temp.data + " -> ";
           temp = temp.next;
       }
      allElements += "END"
      console.log(allElements );
}

Drawbacks of Linked Lists

• When it comes to lookups, linked lists are left behind by arrays.