Implementing Singly Linked Lists in JavaScript

A singly linked list is a type of data structure commonly used in JavaScript to store and manage collections of elements. It consists of a sequence of nodes, where each node contains a value and a reference (or a pointer) to the next node in the sequence. In this article, we will dive deeper into the concept of singly linked lists and explore how they work.

Creating a Singly Linked List

To create a singly linked list in JavaScript, we first need to define a Node class that represents each element in the list. The Node class typically contains two properties: the value of the node and a reference to the next node.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Once the Node class is defined, we can create a LinkedList class to manage the list. This class keeps track of the head of the list (the first node) and provides methods to perform various operations on the list.

class LinkedList {
  constructor() {
    this.head = null;
  }

  // methods for adding, removing, searching, and manipulating nodes
}

Inserting Nodes

To insert a new node into a singly linked list, we need to find the appropriate position in the list. This involves updating the reference of the previous node to point to the new node and setting the next reference of the new node to the node originally referenced by the previous node.

Here’s an example of inserting a new node with the value of 5 after an existing node with the value of 3:

const list = new LinkedList();
// Assume the list already contains nodes with values 1 and 3

// Find the node with value 3
let currentNode = list.head;
while (currentNode.value !== 3) {
  currentNode = currentNode.next;
}

// Create a new node with value 5
const newNode = new Node(5);

// Insert the new node into the list
newNode.next = currentNode.next;
currentNode.next = newNode;

Removing Nodes

To remove a node from a singly linked list, we need to update the reference of the previous node to point to the node that appears after the node being removed. This effectively bypasses the node and removes it from the list.

Here’s an example of removing a node with the value of 3 from a list:

// Assume the list contains nodes with values 1, 3, and 5

let currentNode = list.head;
let prevNode = null;

while (currentNode.value !== 3) {
  prevNode = currentNode;
  currentNode = currentNode.next;
}

prevNode.next = currentNode.next;

Searching for Nodes

To search for a specific node within a singly linked list, we need to iterate through the list and compare the value of each node to the desired value. If a match is found, the node is considered to be found.

Here’s an example of searching for a node with the value of 5 in a list:

let currentNode = list.head;

while (currentNode) {
  if (currentNode.value === 5) {
    console.log("Node found!");
    break;
  }

  currentNode = currentNode.next;
}

Conclusion

Singly linked lists are powerful data structures in JavaScript that provide flexibility for storing and manipulating collections of elements. By understanding how they work and the various operations that can be performed on them, you can leverage them to solve a wide range of problems efficiently.

Whether it’s inserting, removing, or searching for nodes, singly linked lists are versatile and efficient when it comes to managing and organizing data. They are widely used in many applications, including implementing stacks, queues, and hash tables.

Start utilizing singly linked lists in your JavaScript projects and witness their impact on optimizing your code’s performance and efficiency.