A linked list is a collection of nodes connected by pointers. In a singly linked list, each node contains a value and a pointer to the next node.
The first node in a linked list is the root, and the last node in the list is tail.
A linked list is similar to an array. In fact, you could use a linked list in place of an array when solving some software engineering problems.
This does not mean array and linked list behave the same way; they have varying performance implications in different circumstances.
One of the significant differences between a linked list and an array is how they are represented in computer memory.
Let's see how array is stored in memory.
Imagine you and your five friends are going for a movie night on your birthday, and you all must sit together in a row.
Paul, who always comes late called that he would join later, leaving you and your four other friends.
At the movie theater, the unexpected happened. More than half of the seats have been taken. Gosh! People sat randomly, making it hard to find six open seats in a row.
If you're lucky to find five seats for you and your four friends, you'll still have to move when Paul joins.
An array can be likened to this story. Array is fixed size. When you create an array, computer finds a contiguous block of memory in a row to store it.
An array of 7 integers [5,7,3,8,4,9,20] could be represented in computer's memory by the image below, assuming the unshaded blocks are the free memory blocks that can be assigned.
const numbers = [5,7,3,8,4,9,20]
For a linked list, it's represented in memory differently. Assuming 5, 7,3,8,4,9,20 are nodes in a linked list. They don't have to be represented in a contiguous block of memory like the case of an array. The nodes are arbitrary, possibly stored far away from each other in memory.
You may be wondering why linked lists?
Well, array is not as efficient as linked list when adding and deleting data at run-time. This makes linked lists a good candidate for implementing queues and stacks.
Linked list also has its drawbacks. It's not efficient for finding the nth element too. Infact, to find the nth item in a linked list, you'll have to traverse from the root node, following the reference address to the nth element.
Besides, a linked list uses more memory space than an array. The is because a node in a linked list contains data and a memory reference to the next node.
Now that you have why linked list is important, let's move to implementation.
We can represent a node in a singly linked list as:
class Node {
constructor(value){
this.value = value
this.next = null
}
}
The code above should be understandable. The class Node has two attributes: value and the memory address of the next node. We denote these attributes as value and next.
Now, let's proceed to create a basic class for the linked list.
class LinkedList {
constructor() {
this.root = null;
this.tail = null
this.size = 0
}
isEmpty(){}
push(value){}
delete(index){}
}
In the following paragraphs, we'll implement each of the methods.
Checking if the list is empty
We can implement isEmpty() as follows:
isEmpty(){
return this.size === 0
}
isEmpty() checks the size of the list and returns a boolean value.
Adding a new node to the list
To add a new node to the list, we can implement the push() function as follows:
push(value) {
const node = new Node(value);
if (this.isEmpty()) {
this.root = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
}
The method push pushes a new node to the list. Since a tail node is the last node in the list, if a linked list has just a single node, the node becomes the root and the tail node. In the push() method, we checked for this condition.
Deleting a node from the list
We can implement a method to delete a node at an index as:
delete(index) {
if (this.isEmpty()) {
return;
}
if (index < 0 || index > this.size) {
return;
}
if (index === 0) {
const nodeToDelete = this.root;
this.root = nodeToDelete.next
this.size--
return nodeToDelete;
}
let previousNode;
let currentNode = this.root
let start = 0;
while (start < index) {
start++
previousNode = currentNode
currentNode = previousNode.next
}
previousNode.next = currentNode.next
// if node is at the end.
if (previousNode.next === null) {
this.tail = previousNode
}
this.size--
return currentNode;
}
Deleting a node from a linked list has a time complexity of O(1), excluding the time it takes to locate the actual node to delete.
Ideally, deleting the root node is more performant than deleting the node in the middle of the list.
A complete LinkedList class will look like this:
class LinkedList {
constructor() {
this.root = null;
this.tail = null
this.size = 0
}
isEmpty(){
return this.size === 0
}
push(value) {
const node = new Node(value);
if (this.isEmpty()) {
this.root = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
}
delete(index) {
if (this.isEmpty()) {
return;
}
if (index < 0 || index > this.size) {
return;
}
if (index === 0) {
const nodeToDelete = this.root;
this.root = nodeToDelete.next
this.size--
return nodeToDelete;
}
let previousNode;
let currentNode = this.root
let start = 0;
while (start < index) {
start++
previousNode = currentNode
currentNode = previousNode.next
}
previousNode.next = currentNode.next
// if node is at the end.
if (previousNode.next === null) {
this.tail = previousNode
}
this.size--
return currentNode;
}
}
To wrap this up, we learned about linked list and how to implement a singly linked list. If you want to build on this knowledge, I recommend that you extend the examples in this post.
If you find this interesting, you might also find my post on binary search interesting too.