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
| Linked List Type | Insertion Complexity | Access Complexity | Pros | Cons |
|---|---|---|---|---|
| Singly Linked List | O(1) | O(n) | Simple to implement. | Poor performance for certain operations. (e.g. inserting at a specific position.) |
| Doubly Linked List | O(1) | O(n) | Allows for insertion and deletion at both ends of the list. | Requires more memory due to additional pointers. |
| Circular Linked List | O(1) | O(n) | Allows for efficient insertion at the end of the list. | Poor performance for certain operations. (e.g. inserting at a specific position.) |
| Skip List | O(log n) | O(log n) | Allows for efficient search and insertion. | Requires more memory due to additional pointers. |
| XOR Linked List | O(1) | O(n) | Uses less memory than doubly linked list. | Complex to implement and may have poor performance for certain operations. |
Top comments (0)