How to create a Singly Linked List in JavaScript

Singly Linked Lists can be easily implemented in JavaScript by structuring them into a class-based architecture consisting of Node elements.

This article aims to outline the core features of Singly Linked Lists by guiding you with examples written in JavaScript.

What is a Singly Linked List?

A Singly Linked List represents a linear collection of nodes, where each node contains data and a reference to the next node in the sequence.

The list can only be traversed in one direction, which differs from the bi-directional Doubly Linked List, where pointers exist for both the next and previous nodes in the list.

Why use Singly Linked Lists?

• Memory Efficiency: Singly linked lists allocate memory for their nodes dynamically, unlike static data structures like arrays. They are more memory-efficient compared to arrays when dealing with a variable number of elements, as they don’t require contiguous memory allocation and only allocate memory as new nodes are added, without reserving additional space.
• Ease of Insertions and Deletions: In singly linked lists, adding or removing nodes, especially at the beginning, is more efficient compared to arrays. There’s no need to shift elements, as you simply update the pointers, which makes operations like pushing and popping from the head extremely fast.
• Flexibility in Data Management: Singly linked lists provide a flexible structure for data management where the linear order is maintained without the constraint of contiguous memory allocation. This flexibility is particularly beneficial in scenarios where the data structure needs to frequently adjust to new data or remove existing data without concern for memory reallocation or data shifting.

In the diagram below, we can see three nodes, where the first node on the far left represents the ‘head’ or beginning of the linked list, and the farthest right represents the tail or end.

Singly Linked Lists are represented as a collection of nodes structured in a linear sequence

Each node contains two parts:
1. Data — The data the node will hold. For example, if we wanted to create a Singly Linked List of seasons, we might hold a string representation of each season as the data, per node.
2. Pointer — A reference to the next node in the list. The tail node will reference null to indicate the end of the list.

Node Class

Before we can create a Singly Linked List, we have to scaffold a class representation of its building blocks — nodes.

Let’s take a look at the code below and break it down.

class Node {
  constructor(data) {
    this.data = data; // Initialised to the argument passed to the constructor
    this.next = null; // Defaults to null
  }

  // Sets the next node in the list 
  setNextNode(node) {
    if (node instanceof Node || node === null) {
      this.next = node;
    }
  }

  // Gets the next node in the list
  getNextNode() {
    return this.next;
  }
}

module.exports = Node;

• Constructor — takes data as an argument and initialises the ‘data’ property with this value, while defaulting the initialisation of ‘next’ to null.
• setNextNode — this method assigns a node to the ‘next’ property, it checks if the provided node is an instance of the Node class or null, before making the assignment, ensuring type safety and allowing for the end of the list to be null.
• getNextNode — is a method which returns the node pointed to by the ‘next’ property.

This class represents the state and behaviour of a single node which we could use to create a Singly Linked List.

Let’s build a Singly Linked List class.

Singly Linked List Class

Now that we can instantiate Node objects with the above Node class, we can create another class that utilises nodes to produce a Singly Linked List.

const Node = require("./Node");

class SinglyLinkedList {
  constructor() {
    // Initialised to null for an empty list
    this.head = null;
  }

  // Add a node to the head of the linked list
  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

  // Add a node to the tail
  addToTail(data) {
    let tail = this.head;
    if (!tail) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }

  // Removes the head of the linked list
  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    return removedHead.data;
  }

  // Print the list in a readable form
  printList() {
    let currentNode = this.head;
    let output = "<head> ";
    while (currentNode !== null) {
      output += currentNode.data + " ";
      currentNode = currentNode.getNextNode();
    }
    output += "<tail>";
    console.log(output);
  }
}

module.exports = SinglyLinkedList;

• Constructor — initialises the Linked List with a ‘head’ property set to null, indicating an empty list.
• addToHead— inserts a new node at the beginning of the list. If the list is not empty, it adjusts the next pointer of the new node to link to the current head before updating the head to the new node.
• addToTail — appends a new node to the end of the list. If the list is empty, it sets the head to the new node; otherwise, it traverses the list to find the tail and links the new node there.
• removeHead— orphans the node at the beginning of the list. It updates the head to the next node and returns the data of the removed node.
• printList— outputs the data from each node in the list sequentially, from head to tail, aiding in visualising the list’s current state.

Singly Linked List of Seasons

Let’s utilise the Singly Linked List class to produce a collection of example seasons, taking advantage of all the methods we’ve created.

const SinglyLinkedList = require('./SinglyLinkedList');

const seasons = new SinglyLinkedList();
seasons.printList();

seasons.addToHead('summer');
seasons.addToHead('spring');
seasons.printList();

seasons.addToTail('fall');
seasons.addToTail('winter');
seasons.printList();

seasons.removeHead();
seasons.printList();

This will print a readable form of the list to the console:

<head> <tail>
<head> spring summer <tail>
<head> spring summer fall winter <tail>
<head> summer fall winter <tail>

Conclusion

In conclusion, singly linked lists are an essential data structure in JavaScript, providing a dynamic and efficient method for storing and managing data collections.

They excel in environments where memory allocation needs to be flexible, allowing for easy addition and removal of nodes without the need to shift other elements, unlike arrays.

While traversal is unidirectional, from head to tail, the ease of adding or removing nodes at either end of the list makes singly linked lists particularly useful in JavaScript for certain types of applications.

Mastering singly linked lists in JavaScript is a step toward understanding more intricate data structures and enhancing the efficiency of data manipulation and storage in software development.