Linked List Data Structure in Javascript
Tags: javascript, webdev, beginners, computerscience
Published: 2020-03-03 17:45:46

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.

 ![Singly Linked List](https://neurabytes.com/wp-content/uploads/2018/10/linkedlist-1.jpg "Singly Linked List")


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. 
  

 ![Doubly Linked List](https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLL1.png "Doubly Linked List")


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.
```javascript
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.
```javascript
function createLinkedList() {
  return {
    head: null,
    tail: null,
    length: 0,

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

}
```

### Step3 - Push a new value to the LinkedList
```javascript
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
```javascript
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
```javascript
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
```javascript
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
```javascript
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 <img src="https://practicaldev-herokuapp-com.freetls.fastly.net/assets/emoji/emoji-one-unicorn-695106da1194513bfa0092f1a75943f59089be7d6addbc7459bdfab80f5709e6.png" alt="drawing" width="30" height="30"/> Follow this channel for more articles on Data Structures using Javascript.