Implementing LinkedList data structure in JavaScript

Lets start from the most obvious question in this context;

What are data structures in a programming?

In computer science, a data structure is a format to organize, manage and store data in a way that allows efficient access and modification.

Data structures are the most basic concept of any programming language that help us play with data. We store data in different data types based on the data and what we want to do with it.

For instance, if you want to store user form input, you would like to store it as an object as key value pairs, with keys being input name and value being the user input. If you want to store list of choices by user, i don't know about you, but I would store it as an array.

Different datastructures store data in a different way, work on that data in its own way, and expose data in a unique manner too. Lets have a look at Linked List data structure.

Linked list data structure:

LinkedList data structure can store list of different nodes, each node containing data and a reference to next node, previous node, or both. First node in the LinkedList is referred to as head and last node is called tail. List starts from the head, and moves towards tail, with each node storing data and pointing out to the next node in the list. Ofcourse, for the last node, there is not next node so it points to null. Infographically, LinkedList can be represented as;

You can see, each node contains data and has a reference to the next node.

Pros:

The main properties of a linked list data structure are mentioned below:

Effective element insertion and deletion: By simply updating the pointers, linked lists can insert or delete elements from anywhere in the list. There is no constant-time random access to elements in linked lists. While in arrays, values need to be re-indexed.
Sequential access: Linked lists can be used for various activities since they can be sequentially accessed in both the forward and backward directions.

Cons:

Since lists don't have indexes, we can't access values randomly. When we want to access a value, we always have to look for it by iterating through the list starting from its head or tail.
There is no built it linked list in JavaScript but there are plenty of examples out there. But its counter-part arrays are native to Javascript with plenty of support.
It is easier to read data in arrays compared to linked lists as we have to itterate through all the elements to reach at destined element.

To choose between array and linked list really comes torequirements of the algorithem actually.

Types of linked lists:

There are three kinds of linked lists, singly linked lists, doubly linked lists and circular linked list.

Singly-linked list:

In singly linked lists each node has a single pointer that indicates the next node on the list.

Doubly-linked list:

In doubly linked lists each node has a double pointer, one indicates the next node on the list and the other referencing to the previous node.

Circular-linked list:

Circular linked lists are similar as singly linked lists, with one difference that tail of the list points to the head, making it a circle (an infinite loop).

In this guide we will have a look at singly linked list implementation.

Singly linked list implementation:

Singly linked list looks like this;

const linkedListStructure = {
  head: {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null,
      },
    },
  },
  tail: {
    value: 3,
    next: null,
  },
  length: 3,
}

Lets start by creating a JavaScript ES6 Classes for ListNode and LinkedList.

For ListNode class, constructor function will intialize value and next properties of the node object. value property will store node data, and next property will reference to the next node.

For LinkedList class, we will define a constructor function to initialize head, tail, and length of the linked list.

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor(head = null) {
    // if head not specified, defaults to null
    // tail also defaults to null
    this.head = head;
    this.tail = this.head;
    // we increment/decrement it on nodes add/remove
    this.length = 0;
  }
}

Linked list methods:

We are gonna need to add some methods to our class like add, remove, addToHead, addAtPosition, getAtPosition, etc. to make our linked list useful.

Setters (add, addToHead, addAtPosition, set):

add:

Adds new node to the tail of the linkedlist.

class SinglyLinkedList {
  // ...
  add(value){
    let newNode = new ListNode(value)
    
    if(!this.head){
      // no head: no items in list
      this.head = newNode
      this.tail = newNode
    }else{
      // node(s) are present already
      // appends node to the end
      this.tail.next = newNode
      this.tail = newNode
    }
    
    // return newly added node, and increment nodes count
    this.length++
    return newNode
  }
}

addToHead:

Adds new node to the head of the list.

class SinglyLinkedList {
  // ...
  addToHead(value){
    let newNode = new ListNode(value)
    
    if(!this.head){
      // no head: no items in list
      this.head = newNode
      this.tail = newNode
    }else{
      // node(s) are present already
      // set head of list to next prop. of new node
      // set list head equal to new node.
      // this appends previous nodes to new node
      // and replaces head of list with new node
      newNode.next = this.head;
      this.head = newNode;
    }
    
    // return newly added node, and increment nodes count
    this.length++
    return newNode
  }
}

addAtPosition:

As linked lists are not-indexed, therefore we use positions starting from 1 instead of indexs. This method adds node at particular position.

class SinglyLinkedList {
  // ...
  addAtPosition(position, value){
    let newNode = new ListNode(value)
    
    // add some checks
    if(position === 0){
      return "UnderFlow"
    }
    
    if(position === 1){
      // node needs to be added to head
      return this.addToHead(value)
    }
    
    if(position === this.length + 1){
      // this.length = current no. of nodes
      // this.length + 1 = tail + 1
      // means node needs to be added after tail
      return this.add(value)
    }
    
    if(position > this.length + 1){
      // invalid position
      return "OverFlow"
    }
    
    let i = 1;
    // set variable temp equal to current head
    let temp = this.head;
 
    while (i < position - 1) {
      // keep iterating unless we have reached
      // previous node to desired position
      temp = temp.next;
      i++;
    }

    if (temp) {
      // set new nodes next to previous nodes next
      // as these nodes plan to switch places
      newNode.next = temp.next;
      // set previous nodes next to new node
      temp.next = newNode;
      // we have succesfully added node at position p
      
      this.length++;
      return newNode;
    }
  }
}

set:

Sets new value of the node.

class SinglyLinkedList {
  // ...
  set(position, value) {
    // use getAtPosition (explained later) method to find node
    const foundNode = this.getNodeAtPosition(position);
    if (foundNode) {
      // if found set new value
      foundNode.value = value;
      // return true
      return true;
    }
    // if not found return false
    return false;
  }
}

Delete data(shift, pop, remove):

shift:

Shift method deletes head of the list.

class SinglyLinkedList {
  // ...
  shift() {
    if (!this.head) return undefined;

    // set currentHead variable = current head
    var currentHead = this.head;

    // set new head = next node of the previous head
    this.head = currentHead.next;

    // decrement nodes count
    this.length--;

    // after this operation, if list is empty
    // set tail to null
    if (this.length === 0) {
      this.tail = null;
    }

    return currentHead;
  }
}

pop:

Removes last node (tail) of the list and returns it.

class SinglyLinkedList {
  // ...
  pop() {
    if (!this.head) return undefined;
    // set current = current head

    if (this.length === 1) {
      let tail = this.head;
      this.head = 0;
      this.tail = 0;

      return tail;
    }

    let i = 1;
    // set variable temp equal to current head
    let nextTail = this.head;

    while (i < this.length - 1) {
      // keep iterating unless we have reached
      // previous node to desired position
      nextTail = nextTail.next;
      i++;
    }

    const currentTail = nextTail.next;
    nextTail.next = null;
    this.tail = nextTail;
    this.length--;

    return currentTail;
  }
}

remove:

Remove method removes a node at specific position in a linked list.

class SinglyLinkedList {
  // ...
  remove(position) {
    // invalid position
    if (position < 1 || position > this.length) return undefined;
    // position of head: remove head with shift method
    if (position === 1) return this.shift();
    // position of tail: remove tail with pop method
    if (position === this.length) return this.pop();

    // get previous node to target node
    // getNodeAtPosition is explained below
    let previousNode = this.getNodeAtPosition(position - 1);
    // bypass target node from referencing
    let removed = previousNode.next;
    previousNode.next = removed.next;
    
    this.length--;
    return removed;
  }
}

Getters (getHead, getTail, getAtPosition, getNodeAtPosition,print):

class SinglyLinkedList {
  // ...
  getHead(){
    return this.head.value
  }
  
  getTail(){
    return this.tail.value
  }
  
  getAtPosition(position) {
    // invalid position value
    if (position < 1 || position > this.length) return undefined;
    
    // set variable temp = current head
    let temp = this.head;
    
    for (let a = 1; a < position; a++) {
      // keep iterating over nodes, until position is reached
      temp = temp.next;
    }
    
    // return value of found node
    return temp.value;
  }
  
  // same as above mothod, only difference being
  // returns raw node instead of value
  getNodeAtPosition(position) {
    // invalid position value
    if (position < 1 || position > this.length) return undefined;

    // set variable temp = current head
    let temp = this.head;

    for (let a = 1; a < position; a++) {
      // keep iterating over nodes, until position is reached
      temp = temp.next;
    }

    // return value of found node
    return temp;
  }
  
  print() {
    // set variable temp = current head
    let temp = this.head;
    while (temp) {
      // keep iterating over nodes, until it is tail (detect null)
      // use any method to print: i use log.
      console.log(temp.value);
      temp = temp.next;
    }
  }
}

Utility methods (clear, reverse):

class SinglyLinkedList {
  // ...
  
  clear() {
    // clears list by setting head to null
    // clears out all nested nodes
    this.head = null;
    this.tail = null;
    this.length = 0
  }
  
  reverse() {
    if (this.length === 0) return false;
    
    // set temp variable = current head
    let temp = this.head;
    // change list head with list tail
    this.head = this.tail;
    // change list tail with list head
    this.tail = temp;
    
    let next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      // iterate over all nodes
      // keep replacing next node with the prev
      // and prev nodes with next one
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;
    }
    return this;
  }
}

Additional methods:

You can always add other linked list methods as it suits your case. Maybe you would want to add replace method that replaces particular node at a position. Give it a try,

Complete implenetation will look like this;

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  add(value) {
    let newNode = new ListNode(value);

    if (!this.head) {
      // no head: no items in list
      this.head = newNode;
      this.tail = newNode;
    } else {
      // node(s) are present already
      // appends node to the end
      this.tail.next = newNode;
      this.tail = newNode;
    }

    // return newly added node, and increment nodes count
    this.length++;
    return newNode;
  }

  addToHead(value) {
    let newNode = new ListNode(value);

    if (!this.head) {
      // no head: no items in list
      this.head = newNode;
      this.tail = newNode;
    } else {
      // node(s) are present already
      // set head of list to next prop. of new node
      // set list head equal to new node.
      // this appends previous nodes to new node
      // and replaces head of list with new node
      newNode.next = this.head;
      this.head = newNode;
    }

    // return newly added node, and increment nodes count
    this.length++;
    return newNode;
  }

  addAtPosition(position, value) {
    let newNode = new ListNode(value);

    // add some checks
    if (position === 0) {
      return "UnderFlow";
    }

    if (position === 1) {
      // node needs to be added to head
      return this.addToHead(value);
    }

    if (position === this.length + 1) {
      // this.length = current no. of nodes
      // this.length + 1 = tail + 1
      // means node needs to be added after tail
      return this.add(value);
    }

    if (position > this.length + 1) {
      // invalid position
      return "OverFlow";
    }

    let i = 1;
    // set variable temp equal to current head
    let temp = this.head;

    while (i < position - 1) {
      // keep iterating unless we have reached
      // previous node to desired position
      temp = temp.next;
      i++;
    }

    if (temp) {
      // set new nodes next to previous nodes next
      // as these nodes plan to switch places
      newNode.next = temp.next;
      // set previous nodes next to new node
      temp.next = newNode;
      // we have succesfully added node at position p

      this.length++;
      return newNode;
    }
  }

  set(position, value) {
    // use getAtPosition (explained later) method to find node
    const foundNode = this.getNodeAtPosition(position);
    if (foundNode) {
      // if found set new value
      foundNode.value = value;
      // return true
      return true;
    }
    // if not found return false
    return false;
  }

  shift() {
    if (!this.head) return undefined;

    // set currentHead variable = current head
    var currentHead = this.head;

    // set new head = next node of the previous head
    this.head = currentHead.next;

    // decrement nodes count
    this.length--;

    // after this operation, if list is empty
    // set tail to null
    if (this.length === 0) {
      this.tail = null;
    }

    return currentHead;
  }

  pop() {
    if (!this.head) return undefined;
    // set current = current head

    if (this.length === 1) {
      let tail = this.head;
      this.head = 0;
      this.tail = 0;

      return tail;
    }

    let i = 1;
    // set variable temp equal to current head
    let nextTail = this.head;

    while (i < this.length - 1) {
      // keep iterating unless we have reached
      // previous node to desired position
      nextTail = nextTail.next;
      i++;
    }

    const currentTail = nextTail.next;
    nextTail.next = null;
    this.tail = nextTail;
    this.length--;

    return currentTail;
  }

  remove(position) {
    // invalid position
    if (position < 1 || position > this.length) return undefined;
    // position of head: remove head with shift method
    if (position === 1) return this.shift();
    // position of tail: remove tail with pop method
    if (position === this.length) return this.pop();

    // get previous node to target node
    // getNodeAtPosition is explained below
    let previousNode = this.getNodeAtPosition(position - 1);
    // bypass target node from referencing
    let removed = previousNode.next;
    previousNode.next = removed.next;

    this.length--;
    return removed;
  }

  getHead() {
    return this.head.value;
  }

  getTail() {
    return this.tail.value;
  }

  getAtPosition(position) {
    // invalid position value
    if (position < 1 || position > this.length) return undefined;

    // set variable temp = current head
    let temp = this.head;

    for (let a = 1; a < position; a++) {
      // keep iterating over nodes, until position is reached
      temp = temp.next;
    }

    // return value of found node
    return temp.value;
  }

  // same as above mothod, only difference being
  // returns raw node instead of value
  getNodeAtPosition(position) {
    // invalid position value
    if (position < 1 || position > this.length) return undefined;

    // set variable temp = current head
    let temp = this.head;

    for (let a = 1; a < position; a++) {
      // keep iterating over nodes, until position is reached
      temp = temp.next;
    }

    // return value of found node
    return temp;
  }

  print() {
    // set variable temp = current head
    let temp = this.head;
    while (temp) {
      // keep iterating over nodes, until it is tail (detect null)
      // use any method to print: i use log.
      console.log(temp.value);
      temp = temp.next;
    }
  }

  clear() {
    // clears list by setting head to null
    // clears out all nested nodes
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  reverse() {
    if (this.length === 0) return false;

    // set temp variable = current head
    let temp = this.head;
    // change list head with list tail
    this.head = this.tail;
    // change list tail with list head
    this.tail = temp;

    let next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      // iterate over all nodes
      // keep replacing next node with the prev
      // and prev nodes with next one
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;
    }
    return this;
  }
}

Testing implementation

Next most important step is to see if any of this works or you just spent 10 minutes for nothing 😁.

let linkedList = new SinglyLinkedList();

const l = console.log;

l(linkedList.print()); //
l(linkedList.length); // 0
linkedList.add(10);
linkedList.add(20);
linkedList.add(30);
l(linkedList.print()); // 10 20 30
l(linkedList.length); // 3

// delete head
linkedList.shift();
l(linkedList.print()); // 20 30

// add head
linkedList.addToHead(10);
l(linkedList.print()); // 10 20 30

// add at position
linkedList.addAtPosition(2, 15);
l(linkedList.print()); // 10 15 20 30

// set value
linkedList.set(2, 20);
linkedList.set(3, 30);
linkedList.set(4, 40);
l(linkedList.print()); // 10 20 30 40

// remove tail
linkedList.pop();
l(linkedList.print()); // 10 20 30

// remove at position
linkedList.remove(2);
l(linkedList.print()); // 10 30

// getters
l(linkedList.getHead()); // 10
l(linkedList.getTail()); // 30
linkedList.addAtPosition(2, 20);
l(linkedList.print()); // 10 20 30
l(linkedList.getAtPosition(2)); // 20
l(linkedList.getNodeAtPosition(2)); // {value: 20, next: next_node}

linkedList.reverse();
l(linkedList.print()); // 30 20 10
linkedList.clear();
l(linkedList.print()); //
l(linkedList.length); // 0

Have a good day. See you in next one.