Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Insertion in a Singly Linked List

Explore how to perform node insertion in singly linked lists using JavaScript. Understand the differences between inserting at the beginning, end, and specific positions, along with pointer updates and time complexity. Gain insight into optimizing insertions with tail pointers to improve performance in list operations.

We'll cover the following...

By now, you understand how traversal works and why it is necessary in a singly linked list. The next important operation is insertion, which allows new nodes to be added to the list.

Insertion in a linked list is different from insertion in an array. Instead of shifting elements, insertion is performed by updating references between nodes. Understanding how these references change is important for implementing insertion correctly and analyzing its time complexity.

Linked list insertion

Insertion means adding a new node to a singly linked list. Unlike arrays, insertion does not require shifting elements, but it still requires careful pointer updates so the list remains connected.

Insertion is usually discussed in three common cases:

  1. Insertion at the beginning

  2. Insertion at the end

  3. Insertion at a specific position

Before implementing these cases, it helps to remember one rule: insertion is done by changing next references. If the references are updated in the wrong order, part of the list can become unreachable.

Insertion at the beginning

Insertion at the beginning is the most direct case because only the head reference needs to change.

This insertion takes two pointer updates:

  • The new node’s next points to the current head.

  • The head is updated to point to the new node.

The following interactive visualizer shows the step-by-step insertion at the beginning of a linked list.

JavaScript implementation

The method below implements insertion at the beginning of the list.

Javascript (babel-node)
insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node
    newNode.next = this.head; // Link new node to current first node
    this.head = newNode; // Update head to the new node
}
Insertion at the beginning of a Linked List

  • Time complexity: Insertion at the beginning takes O(1) ...