Linked list is a linear data structure if we talk about access strategies, this means that there is a sequence and an order to how they are constructed and traversed. The linked list data structure is a good choice over arrays when you don't need to have random/indexed access to your data, and when you want to have efficient insertion or deletion of elements in the beginning or in the middle of a list. Both insertion and deletion work fast inside linked list because it doesn't require to do reindexing of elements, on the other hand accessing of an element in arrays is fast while for the linked list it takes a linear period of time to get this element.
Inside the linked list each element is stored in a form of Node. Node is made up of two items: data and a reference/pointer to a node.
The linked list is formed when many such nodes are linked together to form a chain. These are the most popular linked list types:
Singly linked list is the simplest implementation of the linked list data structure.
Each of the elements will keep data and a reference/pointer to a next node, in the last node next equals null
. The entry point into a linked list is called the Head of the list (it's a first node of the list).
The last Node in a linked list is called the Tail, this part isn't necessary to include in a linked list, but it allows to avoid list traversing when you need to get the last element inside a list.
First of all, we need to create a Node class for our list:
class Node {
/**
* @param {number} value of the Node
* @param {(Node | null)} next - reference to the next Node
*/
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
Next, let's create a class called LinkedList
that contains the head and the tail with the values null
by default.
class LinkedList {
constructor() {
this.head = null; // First element of the linked list
this.tail = null; // Second element of the linked list
}
}
Now, let's add some methods one by one to our LinkedList
class. The main actions for the linked list data structure are:
Based on requirements linked list insertion methods can be different. For example, if you need to insert values only to the start of the linked list, we simply need to update the head of our list, and tail if it's empty:
/**
* Creates new node and inserts at the start of the list
*
* @param {number} value
* @return {LinkedList}
*/
prepend(value) {
// Create new node with the next reference as the head
const newNode = new Node(value, this.head);
// Update our head to contain new element
this.head = newNode;
// If there is no tail update it too
if (!this.tail) {
this.tail = newNode;
}
return this;
}
Let's try it:
const linkedList = new LinkedList();
linkedList.prepend(5);
linkedList.prepend(2);
console.dir(linkedList);
To implement linked list search we need to know how to do traversing through the linked list. As mentioned above based on access strategy the linked list is a linear data structure, this means that we need to move from one element to another starting from the head to get to the needed Node.
The algorithm of linked list traversing is simple:
null
.Node
(if exists) and access the Node
information.Now let's implement our search method using this knowledge:
/**
* Finds element inside the linked list
*
* @param {number} value
* @return {(Node | null)}
*/
find(value) {
if (!this.head) {
return null;
}
// 🔂 Use traversing to find our node
let currentNode = this.head; // Save current position while moving from one Node to another.
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next; // Update current position
}
// 😞 Nothing found
return null;
}
ℹ️ The method above uses iteration to find value but it can be implemented using recursion.
Deletion of a Node can be also implemented in different ways: first node removal (using head), last node removal, or removal by value.
Implementation of the first node removal is simple, we just need to update the head to point to the next Node. For others we need to traverse singly linked list to get to the needed point. Let's implement deletion by value, from this it should be also clear how to remove the last node:
/**
* Removes Node from the list by its value
*
* @param {number} value to remove
* @return {Node | null} remove node or null
*/
delete(value) {
if (this.head === null) {
return null;
}
let deletedNode = null; // Keep deleted Node to return it
if (this.head.value === value) {
deletedNode = this.head;
// Now make next node to be a new head
this.head = this.head.next;
}
let currentNode = this.head;
// 🔂 Traverse the list only if both the head and deletedNode variables equal null
if (currentNode !== null && deletedNode === null) {
while (currentNode.next !== null) {
if (currentNode.next.value === value) {
deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
} else {
currentNode = currentNode.next;
}
}
}
// Check if tail contains Node with the value we are looking for
if (this.tail.value === value) {
this.tail = currentNode;
}
return deletedNode;
}
Doubly linked list is similar to the Singly linked list structure, difference is that Nodes store pointers to the next and previous elements.
The first Node has null
as a pointer for the previous element, and the last Node has pointer to the next element with the value null
.
So, in the doubly linked list we have the following:
head
- keeps first node.tail
- keeps last node.Our Node in the doubly linked list looks like the following:
class Node {
/**
* @param {number} value of the Node
* @param {(Node | null)} next - reference to the next Node
* @param {(Node | null)} previous - reference to the previous Node
*/
constructor(value, next = null, previous = null) {
this.value = value;
this.next = next;
this.previous = previous;
}
}
Doubly linked list operations are similar to the singly linked list, except that you need to keep updated previous
pointer of a Node too.
Let's take a look how our prepend method can look like for the doubly linked list:
class DoublyLinkedList {
constructor() {
this.head = null; // First element of the linked list
this.tail = null; // Last element of the linked list
}
/**
* Creates new node and inserts at the start of the list
*
* @param {number} value
* @return {DoublyLinkedList}
*/
prepend(value) {
const newNode = new Node(value, this.head);
// if there is head, then update it's previous reference as it won't be head anymore
if (this.head) {
this.head.previous = newNode;
}
this.head = newNode;
// If there is no tail create it
if (!this.tail) {
this.tail = newNode;
}
return this;
}
}
Full code implementation is available at the end of the article.
Operation | Complexity |
---|---|
Access | O(n) |
Insertion (to the head or tail) | O(1) |
Search | O(n) |
Deletion | O(n) |
^{N is the length of Linked List}
Code:
You can also visit the following links to learn more about linked lists:
Front-end Developer and CS student. Living and coding in Ukraine.