Linked List Data Structure in Javascript

A Linked List is a linear collection of data elements that are called nodes.
So this is sort of like an array, but a little bit different. Each of these nodes has a value field(eg integer, character, etc) and another field called next
which is a reference to the next node in the list. So conceptually, a linked list looks like this. In this case, the nodes contain integer numbers as their data.

The first item in the list is used as a reference to traverse the list and is called the HEAD.The last item in the list has a field that points to null, which indicates that it is the end of the list. The diagram you saw above represents what's called a singly-linked list because each item only knows about its next neighbor. But there's no reason we couldn't have a doubly Linked List, which is shown below.

In this case, each data item has a reference to both the previous and next items that are its neighbors.

Benefits of using a Linked List over arrays

Linked Lists provide a benefit over regular arrays in that it's fast O(1) time complexity and easy to add and remove items from the linked list as opposed to O(n) in the worst case, insertion and deletion in arrays. Inserting a new element in an array of elements is expensive because existing elements have to be shifted in order to create room for the new elements. Also, it's not necessary to reorganize the underlying memory that holds the data because the individual nodes don't have to be stored contiguously like they do in an array.

Implementation in Javascript

Step1 - Creating the node object

To make our linked list, we first want to create a node object for each item in our list. Our node has two properties, the value stored at this node and a next property which gets pointed to the next item in our list. This next property defaults to null.

function createNode(value) {
  return {
    value,
    next: null
  }
}

Step2 - Next, we want to make our list data structure.

Our list will have several properties we want to keep track of -- a head property (defaults to null), a tail property(defaults to null), and a length(defaults to 0) property.
We'll also want to create several methods for our list -- push, pop, get, delete, and isEmpty.

We can also implement the isEmpty method which just returns whether or not the length is 0.

function createLinkedList() {
  return {
    head: null,
    tail: null,
    length: 0,

    isEmpty() {
      return this.length === 0
    }
  }

}

Step3 - Push a new value to the LinkedList

push(value) {
  const node = createNode(value)
  //If we don't currently have a head, our list `head` and `tail` property is set to our new node.  Since this is a special case, we increment the length here and return the node now.
  if (this.head === null) {
    this.head = node
    this.tail = node
    this.length++
    return node
  }
  this.tail.next = node
  this.tail = node
  this.length++
}

Step4 - Pop an item from the list

pop() {
  if (this.isEmpty()) {
    return null
  }
  const node = this.tail

  if (this.head === this.tail) {
    this.head = null
    this.tail = null
    this.length--
    return node
  }

  let current = this.head
  let penultimate
  while (current) {
    if (current.next === this.tail) {
      penultimate = current
      break
    }

    current = current.next
  }

  penultimate.next = null
  this.tail = penultimate
  this.length--

  return node
}

Step 5 - get item at particular index in the linked list

get(index) {
  if (index < 0 || index > this.length) {
    return null
  }

  if (index === 0) {
    return this.head
  }

  let current = this.head
  let i = 0
  while (i < index) {
    i++
    current = current.next
  }

  return current
}

Step 6 - Delete item from the linked list

delete(index) {
  if (index < 0 || index > this.length) {
    return null
  }

  if (index === 0) {
    const deleted = this.head

    this.head = this.head.next
    this.length--

    return deleted
  }

  let current = this.head
  let previous
  let i = 0

  while (i < index) {
    i++
    previous = current
    current = current.next
  }

  const deleted = current
  previous.next = current.next
  this.length--

  return deleted
}

Step 7 - Print the linkedlist

print() {
  const values = []
  let current = this.head

  while (current) {
    values.push(current.value)
    current = current.next
  }

  return values.join(' => ')
}

Drawback of Linked list

The main drawback of a Linked List, though, is that it's not possible to do constant-time random access of any item in the Linked list like an array can. Looking up an arbitrary item is linear in time complexity.So to find item 5 in this list, we'd first have to start at the head, and then work our way down the list until we found the item.

In the next article of this series, we will be implementing Graph data structure in Javascript.

If you found this article helpful, please tap the Follow this channel for more articles on Data Structures using Javascript.