Linked lists are a linear data structure consisting of nodes that are not stored contiguously (right next to each other) in memory.
Each node of the linked list consists of data and a next pointer. Since (unlike the array) a linked list is not stored contiguously, the purpose of the next pointer is to provide a reference or link to the next node in the sequence. Hence the term "linked" list.
As seen in the image above, the last node's next pointer always points to null. This is how we know we've reached the end of the list.
Head is the name given to the first node in the list
Tail is the name given to the last node in the list
Pros of linked list
- insertion and deletion are done in O(1)
- not stored contiguously in memory
- dynamic (linked lists grow/shrink at runtime depending on its size)
Cons of linked list
- uses more memory than an array
- traversal is more time consuming compared to an array since there is no direct (index) access
- in a SLL, reverse traversing is not possible
- random access is not possible because there are no indices
Stepping away from linked lists for a while, when we think of the array in JavaScript, there are methods that allow us to interact and modify the array. Think, push(), shift(), etc. Similarly, there are linked list methods allowing us the ability to interact with and modify it. The only difference is that they're not built-in; we have to create them ourselves.
These methods include
- addToEnd() or push(): adds a node to the end of the list
- addToStart() or unshift(): adds a node to the start of the list
- deleteFromEnd() or pop(): deletes a node from the end of the list
- deleteFromStart() or shift(): deletes a node from start of the list
- length(): returns the length of the linked list
Implementing a linked list node:
Remember, a node consists of data (val) and a next pointer which is initialized to null since the linked list will be empty when we start.
class Node {
constructor(val) {
this.value = val;
this.next = null;
}
}
Implementing a linked list:
Remember, the first node is called the head and the last node is called the tail. We have instant access to the first and last node which is why insertion and deletion is O(1). Also, the linked list will be empty initially, so both head and tail are initialized with null.
class LinkedList {
constructor(){
this.head = null
this.tail = null
this.length = 0;
}
addToEnd(val) {
let node = new Node(val)
if(!this.head) {
this.head = node
this.tail = node
}
this.tail.next = node
this.tail = node
this.length++
return this;
}
deleteFromEnd() {
if(!this.head) return undefined
let curr = this.head
let newTail = curr
while(curr.next) {
newTail = curr
curr = curr.next
}
newTail.next = null
this.tail = newTail
this.length--
if(this.length === 0) {
this.head = null;
this.tail = null
}
return curr;
}
addToStart(val) {
let node = new Node(val)
if(!this.head) {
this.head = node
this.tail = node
}
node.next = this.head
this.head = node
this.length++
return this;
}
deleteFromStart() {
if(!this.head) return undefined
let curr = this.head
this.head = curr.next
this.length--
if(this.length === 0) {
this.head = null
this.tail = null
}
return null
}
}
let list = new LinkedList();
list.addToEnd(21)
list.addToEnd(24)
list.addToEnd(35)
list.addToStart(99)
list.deleteFromEnd()
console.log(list)
