A linked list is a linear data structure that consists of a sequence of nodes. Each node in a linked list stores a reference to an object and a reference to the next node in the sequence. The last node in the list typically has a reference to null, indicating the end of the list.

Linked lists have several advantages over arrays.

• Insertions and deletions at the beginning of the list are very fast, as they only require updating a single reference. In contrast, inserting or deleting an element at the beginning of an array requires shifting all the elements of the array by one position, which can be time-consuming.
• Linked lists also don’t required consecutive memory space, because they store the data and a reference to the next node, rather than the entire list of elements together.

However, linked lists have some disadvantages compared to arrays.

• They do not provide constant-time access to individual elements, since you have to start at the beginning of the list and follow the references to find the element you are looking for.
• Linked lists also require more memory per element, because they store both the data and the reference to the next element.
• Because each element within an array only needs to store its value, compared to a linked list where there is also a pointer field along with the data field, an array takes up less memory.

Linked lists are often used in applications where the list is frequently modified, such as in the implementation of stacks, queues, and hash tables.

Here is an example of a simple linked list implementation in JavaScript:

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

class LinkedList {
  constructor(value) {
    this.head = new LinkedNode(value)
    this.tail = this.head
    this.length = 1
  }
  append(value) {
    const newNode = new LinkedNode(value)
    this.tail.next = newNode
    this.tail = newNode
    this.length++
  }
  prepend(value) {
    const newNode = new LinkedNode(value)
    newNode.next = this.head
    this.head = newNode
    this.length++
  }
  insert(index, value) {
    //check params
    if (index >= this.length) {
      this.append(value)
    } else {
      let targetNode = this.traverseToIndex(index)
      const newNode = new LinkedNode(value)
      newNode.next = targetNode.next
      targetNode.next = newNode
      this.length++
    }
  }
  remove(index) {
    if (index > this.length) return "Invalid Index Value"
    if (index === 0) {
      this.head = this.head.next
      this.length--
      return
    }
    let targetNode = this.traverseToIndex(index)
    targetNode.next = targetNode.next.next
    this.length--
  }
  traverseToIndex(index) {
    let currNode = this.head
    for (let i = 1; i < index; i++) {
      currNode = currNode.next
    }
    return currNode
  }
  reverse() {
    if (!this.head.next) return
    // Method 1
    // let curr = this.head
    // this.head = null
    // while(curr){
    //   this.prependNode(curr)
    //   curr = curr.next
    // }

    //method 2
    let first = this.head
    let second = first.next
    while (second) {
      let temp = second.next
      second.next = first
      first = second
      second = temp
    }
    this.head.next = null
    this.head = first
  }
  prependNode(node) {
    let newNode = new LinkedNode(node.value)
    newNode.next = this.head
    this.head = newNode
  }
  printList() {
    const array = []
    let currNode = this.head
    while (currNode !== null) {
      array.push(currNode.value)
      currNode = currNode.next
    }
    return array
  }
}

const sampleList = new LinkedList(10)
sampleList.append(20)
sampleList.append(30)
sampleList.prepend(5)
sampleList.prepend(15)
sampleList.insert(3, 56)
sampleList.printList()
sampleList.reverse()
sampleList.printList()

There are several types of linked lists that you can implement in JavaScript. Some common types of linked lists include:

Singly linked list:

A singly linked list is a linked list where each node stores a reference to the next node in the list, but not to the previous node. This means that you can only traverse the list in a single direction, starting from the head of the list. The linked list we have implemented above is a singly linked list. Singly Linked list node:

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

Doubly linked list:

A doubly linked list is a linked list where each node stores a reference to both the next and previous nodes in the list. This allows you to traverse the list in both directions, starting from either the head or the tail of the list.

Here is an example of a doubly linked list implementation in JavaScript:

class LinkedNode {
  constructor(data) {
    this.data = data
    this.next = null
    this.prev = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
  }

  add(data) {
    const newNode = new LinkedNode(data)
    if (this.head === null) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }
  }

  remove(data) {
    let current = this.head
    while (current !== null) {
      if (current.data === data) {
        if (current.prev !== null) {
          current.prev.next = current.next
        }
        if (current.next !== null) {
          current.next.prev = current.prev
        }
        if (current === this.head) {
          this.head = current.next
        }
        if (current === this.tail) {
          this.tail = current.prev
        }
        return
      }
      current = current.next
    }
  }

  contains(data) {
    let current = this.head
    while (current !== null) {
      if (current.data === data) {
        return true
      }
      current = current.next
    }
    return false
  }

  printForward() {
    let current = this.head
    while (current !== null) {
      console.log(current.data)
      current = current.next
    }
  }

  printBackward() {
    let current = this.tail
    while (current !== null) {
      console.log(current.data)
      current = current.prev
    }
  }
}

You can use this doubly linked list implementation by creating a new instance of the LinkedList class and adding nodes to the list using the add method:

const list = new LinkedList()
list.add(1)
list.add(2)
list.add(3)

console.log(list.contains(2)) // prints true
console.log(list.contains(4)) // prints false

list.remove(2)
console.log(list.contains(2)) // prints false

list.printForward() // prints 1 3
list.printBackward() // prints 3 1

Circular linked list:

A circular linked list is a linked list where the last node in the list points back to the first node, forming a circular loop. This allows you to traverse the list in a loop, starting from any node in the list.

Here is an example of a circular linked list implementation in JavaScript:

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

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

  add(data) {
    const newNode = new LinkedNode(data)
    if (this.head === null) {
      this.head = newNode
      newNode.next = this.head
    } else {
      let current = this.head
      while (current.next !== this.head) {
        current = current.next
      }
      current.next = newNode
      newNode.next = this.head
    }
  }

  remove(data) {
    if (this.head === null) {
      return
    }
    let current = this.head
    while (current.next !== this.head) {
      if (current.next.data === data) {
        current.next = current.next.next
        return
      }
      current = current.next
    }
    if (this.head.data === data) {
      if (this.head.next === this.head) {
        this.head = null
      } else {
        current.next = this.head.next
        this.head = this.head.next
      }
    }
  }

  contains(data) {
    let current = this.head
    if (current === null) {
      return false
    }
    do {
      if (current.data === data) {
        return true
      }
      current = current.next
    } while (current !== this.head)
    return false
  }
}

You can use this circular linked list implementation by creating a new instance of the LinkedList class and adding nodes to the list using the add method:

const list = new LinkedList()
list.add(1)
list.add(2)
list.add(3)

console.log(list.contains(2)) // prints true
console.log(list.contains(4)) // prints false

list.remove(2)
console.log(list.contains(2)) // prints false

Skip list:

A skip list is a data structure that combines elements of linked lists and arrays to provide fast search and insertion operations. In a skip list, each node has multiple pointers to other nodes, allowing you to skip over large sections of the list when searching for an element. It is a linked list with multiple levels, where each level has a certain probability of being skipped during a search. This allows the skip list to have a search time that is logarithmic (O(log(n))) in the number of elements, similar to a balanced binary search tree. Skip lists are interesting data structures that rely on a random element in its design.

Here is an example of a Skip linked list implementation in JavaScript:

class SkipListNode {
  constructor(val) {
    this.val = val
    this.next = new Array(16 + 1).fill(null)
    this.level = 0
  }
}

class SkipList {
  constructor() {
    this.head = new SkipListNode(null)
    this.MAX_LEVEL = 16
    this.level = 0
  }

  randomLevel() {
    let level = 0
    while (Math.random() < this.P && level < this.MAX_LEVEL) {
      level++
    }
    return level
  }

  search(val) {
    let curr = this.head
    for (let i = this.level; i >= 0; i--) {
      while (curr.next[i] !== null && curr.next[i].val < val) {
        curr = curr.next[i]
      }
    }
    curr = curr.next[0]
    if (curr !== null && curr.val === val) {
      return curr
    }
    return null
  }

  insert(val) {
    let curr = this.head
    let update = new Array(this.MAX_LEVEL + 1).fill(null)
    for (let i = this.level; i >= 0; i--) {
      while (curr.next[i] !== null && curr.next[i].val < val) {
        curr = curr.next[i]
      }
      update[i] = curr
    }
    curr = curr.next[0]
    if (curr === null || curr.val !== val) {
      let level = this.randomLevel()
      if (level > this.level) {
        for (let i = this.level + 1; i <= level; i++) {
          update[i] = this.head
        }
        this.level = level
      }
      curr = new SkipListNode(val)
      for (let i = 0; i <= level; i++) {
        curr.next[i] = update[i].next[i]
        update[i].next[i] = curr
      }
    }
  }

  remove(val) {
    let curr = this.head
    let update = new Array(this.MAX_LEVEL + 1).fill(null)
    for (let i = this.level; i >= 0; i--) {
      while (curr.next[i] !== null && curr.next[i].val < val) {
        curr = curr.next[i]
      }
      update[i] = curr
    }
    curr = curr.next[0]
    if (curr !== null && curr.val === val) {
      for (let i = 0; i <= this.level; i++) {
        if (update[i].next[i] !== curr) {
          break
        }
        update[i].next[i] = curr.next[i]
      }
      while (this.level > 0 && this.head.next[this.level] === null) {
        this.level--
      }
    }
  }
}

const list = new SkipList()
list.insert(1)
list.insert(2)
list.insert(3)
list.insert(6)
console.log(list.search(2)) // prints Node with val 2
console.log(list.search(4)) // prints null
list.remove(2)
console.log(list.search(2)) // prints null

XOR linked list:

An XOR linked list is a data structure that uses a special type of pointer called an “exclusive or” (XOR) pointer to store the reference to the next node in the list. XOR linked lists can be used to implement a doubly linked list using only a single field in each node, rather than two fields (one for the next node and one for the previous node). This can be more memory-efficient, but can also be more complex to implement. We can not implement a proper XOR linked list in Javascript as we cannot access the memory address. So in js it will be equivalent to a doubly linked list.

Here are a few Leetcode problems that involve linked lists:

Reverse Linked List: Reverse a singly linked list.

Merge Two Sorted Lists: Merge two sorted linked lists and return it as a new sorted list.

Add Two Numbers: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Linked List Cycle: Given a linked list, determine if it has a cycle in it.

Linked List Cycle II: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Remove Nth Node From End of List: Given a linked list, remove the n-th node from the end of list and return its head.

Palindrome Linked List: Given a singly linked list, determine if it is a palindrome.

Conclusion