Singly Linked List in JS

Data Structures - Singly Linked Lists

 

A singly linked list consists of many nodes each node contains data and points at the next node. The last node in the list points to null which is how you know you reached the end. The front of the list is the head node.

The following is some Javascript code showing initialization of the LinkedList and Node classes.

 

class LinkedList {

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


///Other methods here



end



class Node {

  constructor(data, next) {
    this.data = data
    this.next = next
  }

}

 

Head Node ---> Node ---> Node ---> Node --->...more nodes... --> null  

 

It is a very simple structure. It does not require that nodes are next to each other in memory and because of this is very easy to add and remove from the head of the list. It can be done in constant or O(1) time which is the best possible time complexity.

 

Javascript - add to head and remove from head

  addToHead(data) {
    let node
    if (!!data) {
      node = new Node(data, this.head)
      this.head = node
      this.size += 1
    } else {
      return null
    }
}

  removeFromHead() {
    if (this.size != 0) {
      this.head = this.head.next
      this.size -= 1
    }
}

 

A downside to this structure is that it is more expensive to search for something in the list or add/remove to the end (instead of th head). Every node has to be iterated through until we accidently run into the node that contains the data we are looking for or until we reach the end or until the next pointer points to null.

 

// finds the Node that contains the data. If it doesn't exist returns null
  find(data) {
    let current = this.head
      while (current != null) {
        if (current.data === data) {
          return current
        } else {
          current = current.next
        }
      }
    return null
}



  addToTail(data) {
    let node
    let size = this.size
    let current = this.head

    if (!!data) {

// when list is empty just add to head
      if (current === null) {
        this.addToHead(data)
      } else {

// otherwise find the end of the list and add a Node
        while (size > 0) {

// if size === 1 than it is the last node. Add new Node to end.
          if (size === 1) {
            node = new Node(data, null)
            current.next = node
            this.size += 1
          }
// size is > 1 than decrement size and check the next Node
          current = current.next
          size -= 1
        }
      }
    } else {
      return null
    }
}

 

Since we have to traverse the list each time this results in O(n) complexity which is not optimal.

 

Inserting and deleting from the middle of the list is equally as difficult since we have to create our new node and point it to the 'next' node before we mode the current node's next to the new node. Else we have no pointer and the list is lost.

 

  insertAtIndex(data, index) {
    let node
    let current
    let size = this.size

// check if !!data and if index is within bounds
    if (!!data && index >= size - 1 && index >= 0) {
      current = this.head

// base case if list is empty or if adding to head
      if (current == null && index === 0 || index === size-1) {
        this.addToHead(data)
        return true
      }
// base case when adding to tail
      if (index === 1) {
        this.addToTail(data)
        return true
      }

// find spot before index and insert to next Node
      while (size > index) {
        if (size - 1 === index) {
          node = new Node(data, current.next)
          current.next = node
          this.size += 1
          return true
        }
        current = current.next
        size -= 1
      }

    }
    return false
}

 

This is why the structures are often used for Stacks and Queues. It allows flexibility for the operating system because it doesn't need a block of memory like an array does which makes them optimal for Stacks and Queues in my opinion. With a Stack we are always manipulating the last thing added because it is a last in first out (LIFO) structure and a Queue is a first in first out (FIFO) data structure. We can talk about those a different day.

Here's a link to my JS linked-list code