A linked list is a fundamental data structure where each element (called a node) contains two parts: the data and a reference (or pointer) to the next node in the sequence. Although JavaScript has built-in data structures like arrays, understanding how to implement a linked list helps improve your grasp of low-level data structures and their operations. In this post, we'll explore how to implement a singly linked list in JavaScript from scratch.
By the end of this tutorial, you'll know:
- The structure of a linked list in JavaScript
- How to insert elements at the beginning and the end of the list
- How to display and delete nodes
1. Understanding the Linked List Structure
A singly linked list is composed of nodes, where each node has two key properties:
- data: Stores the value of the node.
- next: Points to the next node in the sequence, or
nullif it’s the last node.
Example of a Node Class:
class Node {
constructor(data) {
this.data = data; // Stores the data
this.next = null; // Initially, the next pointer is null
}
}
In this class:
dataholds the node’s value.nextis a reference to the next node in the list, ornullif there are no more nodes.
2. Creating a Linked List
Now that we have a Node class, let’s create a LinkedList class that will manage the linked list. It will store the head of the list (the first node).
Example:
class LinkedList {
constructor() {
this.head = null; // Initialize the list with an empty head
}
isEmpty() {
return this.head === null; // Check if the list is empty
}
}
Here, the LinkedList class initializes with an empty head (null), which means the list starts out empty.
3. Inserting Nodes into the Linked List
You can insert nodes into the list in two common ways:
- At the beginning: The new node becomes the head of the list.
- At the end: The new node is added after the last node.
a) Inserting at the Beginning
To insert a node at the beginning, the new node's next should point to the current head, and then we update the head to the new node.
insertAtBeginning(data) {
const newNode = new Node(data);
newNode.next = this.head; // New node points to current head
this.head = newNode; // Update head to the new node
}
b) Inserting at the End
To insert a node at the end, we need to traverse the list until we find the last node (where next is null) and then link the new node to it.
insertAtEnd(data) {
const newNode = new Node(data);
if (this.isEmpty()) { // If the list is empty, make new node the head
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode; // Set the next of the last node to the new node
}
4. Displaying the Linked List
To display the nodes of the linked list, you need to start from the head and traverse the list while printing the value of each node until you reach the last node.
Example:
display() {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
let current = this.head;
let listStr = "";
while (current !== null) {
listStr += current.data + " -> ";
current = current.next;
}
listStr += "null";
console.log(listStr);
}
In this method:
- We traverse the linked list, adding each node’s
datato a string. - After printing all the nodes, we append
"null"to signify the end of the list.
5. Deleting a Node
Deleting nodes from a linked list can be done in multiple ways:
- Deleting the first node (head).
- Deleting a node by its value.
a) Deleting the First Node (Head)
To delete the first node, we simply update the head to the next node in the list.
deleteFirst() {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
this.head = this.head.next; // Move head to the next node
}
b) Deleting a Node by Value
To delete a node by value, we need to traverse the list, find the node with the matching value, and adjust the previous node’s next pointer to skip over the node to be deleted.
deleteNode(value) {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
// If the node to be deleted is the head node
if (this.head.data === value) {
this.head = this.head.next;
return;
}
let current = this.head;
let previous = null;
while (current !== null && current.data !== value) {
previous = current;
current = current.next;
}
if (current === null) {
console.log("Value not found in the list");
return;
}
previous.next = current.next; // Unlink the node from the list
}
6. Complete Example
Here’s a full implementation of a basic linked list in JavaScript. It includes methods to insert nodes at the beginning or end, display the list, and delete nodes.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
isEmpty() {
return this.head === null;
}
insertAtBeginning(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
insertAtEnd(data) {
const newNode = new Node(data);
if (this.isEmpty()) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
display() {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
let current = this.head;
let listStr = "";
while (current !== null) {
listStr += current.data + " -> ";
current = current.next;
}
listStr += "null";
console.log(listStr);
}
deleteFirst() {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
this.head = this.head.next;
}
deleteNode(value) {
if (this.isEmpty()) {
console.log("List is empty");
return;
}
if (this.head.data === value) {
this.head = this.head.next;
return;
}
let current = this.head;
let previous = null;
while (current !== null && current.data !== value) {
previous = current;
current = current.next;
}
if (current === null) {
console.log("Value not found in the list");
return;
}
previous.next = current.next;
}
}
// Example usage:
const list = new LinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
console.log("Initial List:");
list.display();
list.deleteFirst();
console.log("After deleting first node:");
list.display();
list.deleteNode(20);
console.log("After deleting node with value 20:");
list.display();
Conclusion
In this post, you've learned how to manually implement a basic singly linked list in JavaScript, including how to insert, display, and delete nodes. Understanding the inner workings of a linked list is crucial when learning data structures and algorithms. This knowledge will also help you when working with more complex structures like stacks, queues, and graphs.