Introduction
In this blog post, we’ll look at the basics of singly linked lists in JavaScript. We’ll see how they work and how to make and link nodes together.
Let’s begin by looking at some code that shows this idea:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Creating nodes for singly linked list
let node1 = new Node(3);
let node2 = new Node(7);
let node3 = new Node(2);
let node4 = new Node(9);
// Connecting nodes
node1.next = node2;
node2.next = node3;
node3.next = node4;
// Head of the singly linked list
let headSingly = node1;
This Node class is like a building block of a linked list. It has two important parts:
- data: This holds the value or information the node contains.
- next: This points to the next node in the list. When we create a new node, it starts with no connection, so ‘next’ is set to null
node1.next = node2;
node2.next = node3;
node3.next = node4;
Now let’s connect these nodes. We begin with node1 and set its ‘next’ property to point to node2. Then, we set node2’s ‘next’ to point to node3, and so on. This is how we create the sequence or ‘link’ between nodes.
let headSingly = node1;
Lastly, we create a variable called ‘headSingly’ that points to the first node in our linked list. This is often called the ‘head’ of the list. Using this ‘head’, we can go through the entire linked list by following the ‘next’ pointers.
Putting Everything Together If we picture our linked list:
3 -> 7 -> 2 -> 9 -> null
This is what we’ve made:
- node1 holds 3 and points to node2
- node2 holds 7 and points to node3
- node3 holds 2 and points to node4
- node4 holds 9 and points to nothing (null)
So, ‘headSingly’ points to node1, which is the start of our linked list.
Operations on Singly Linked List
Traversing the Linked List
Traversing means going from one node to another to see or show their data. We begin at the head and move to the next node until we reach the end, which is null.
function traverseLinkedList(head) {
let current = head; // Start from the head
while (current !== null) {
console.log(current.data); // Display data of the current node
current = current.next; // Move to the next node
}
}
// Usage
traverseLinkedList(head); // Will print: 3 -> 7 -> 2 -> 9
Inserting a Node
To add a new node, we have to change the pointers to keep the order. Let’s say we want to add 5 after 7.
function insertNodeAfter(node, newData) {
let newNode = new Node(newData); // Create a new node
newNode.next = node.next; // Point the new node to the next node
node.next = newNode; // Update the current node's next to the new node
}
// Insert 5 after node2 (which is 7)
insertNodeAfter(node2, 5);
// Now the list is: 3 -> 7 -> 5 -> 2 -> 9
Searching in the Linked List
Searching means going through the list to find a certain value. Let’s see how we can search for a value, like 2
function searchLinkedList(head, target) {
let current = head;
while (current !== null) {
if (current.data === target) {
return true; // Found the target
}
current = current.next;
}
return false; // Target not found
}
// Usage
console.log(searchLinkedList(head, 2)); // true
console.log(searchLinkedList(head, 10)); // false
Deleting a Node
Deleting means updating the pointers to take out a node from the list. Let’s say we want to delete the node with the value 5
function deleteNode(head, target) {
let current = head;
if (current.data === target) {
return head.next; // Move head if the target is the first node
}
while (current.next !== null) {
if (current.next.data === target) {
current.next = current.next.next; // Skip the target node
break;
}
current = current.next;
}
return head; // Return the updated head
}
// Delete node with value 5
head = deleteNode(head, 5);
// Now the list is: 3 -> 7 -> 2 -> 9
Conclusion
Singly Linked Lists are useful and efficient for certain tasks. They allow quick insertion and deletion at the beginning, but searching and deleting at a specific spot takes more time. Knowing these basic operations well is important for understanding linked lists and similar data structures. With this knowledge, you can create more advanced applications and algorithms that use linked lists.
Happy Coding 🙂
