Singly Linked List

A singly linked list is a sequence of nodes connected in one direction. Each node stores a value and a next reference to the following node.

The list keeps a head reference to its first node and a tail reference to its last node. The tail's next points to null, which marks the end of the list.

Think of the structure like a scavenger hunt:

• You only know where the first clue is.
• Each clue reveals a message and gives you directions to find the next clue.
• The final clue points to nothing (null), signaling that the hunt is over.

Anatomy of a Singly Linked List

Visualizing a Node

Each node is an independent object with two properties:

Defining the Node and List

To implement a singly linked list in code, we define two classes:

1. Node: Holds the data and the reference to the next node.
2. SinglyLinkedList: Manages the chain, tracking head, tail, and length.

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

Tracking tail and length gives us two immediate performance advantages:

• Appending items to the end runs in $O(1)$ constant time instead of requiring a full traversal.
• Checking the number of items or validating index boundaries runs in $O(1)$ time.

Core Operations

1. Adding to the End (push)

The push method appends a new node to the end of the list.

Step-by-Step Logic

1. Create a new node with the provided value.
2. If the list is empty (!this.head), point both head and tail to the new node.
3. Otherwise, set the current tail.next to point to the new node, and update tail to be the new node.
4. Increment length by 1.

push(val) {
  const newNode = new Node(val);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length++;
  return this;
}

Time Complexity: $O(1)$ — Direct pointer update through the tail pointer.

2. Adding to the Beginning (unshift)

The unshift method prepends a new node to the start of the list, making it the new head.

Step-by-Step Logic

1. Create a new node with the provided value.
2. If the list is empty, set both head and tail to the new node.
3. Otherwise, set the new node's next pointer to reference the current head.
4. Update head to reference the new node.
5. Increment length by 1.

unshift(val) {
  const newNode = new Node(val);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head = newNode;
  }
  this.length++;
  return this;
}

Time Complexity: $O(1)$ — Unlike arrays where prepending requires shifting every element to the right ($O(n)$), adding to the head of a linked list is instant.

3. Removing from the Beginning (shift)

The shift method removes the node at the head of the list and returns it.

Step-by-Step Logic

1. If the list is empty, return null.
2. Save the current head node in a temporary variable.
3. Advance head to head.next.
4. Decrement length by 1.
5. If length reaches 0, set tail to null.
6. Sever the removed node's next pointer and return it.

shift() {
  if (!this.head) return null;
  const removedNode = this.head;
  this.head = this.head.next;
  this.length--;
  if (this.length === 0) {
    this.tail = null;
  }
  removedNode.next = null;
  return removedNode;
}

Time Complexity: $O(1)$ — Constant time. In an array, removing from index 0 takes $O(n)$ time because all remaining elements must shift left.

4. Removing from the End (pop)

The pop method removes the node at the tail of the list and returns it.

Step-by-Step Logic

1. If the list is empty, return null.
2. Start two pointers at head: current and newTail.
3. Loop while current.next exists: advance newTail to current, and current to current.next.
4. When the loop finishes, current is the tail, and newTail is the second-to-last node.
5. Set tail to newTail and disconnect its next pointer (tail.next = null).
6. Decrement length by 1.
7. If length reaches 0, reset both head and tail to null.
8. Return current.

pop() {
  if (!this.head) return null;
  let current = this.head;
  let newTail = current;

  while (current.next) {
    newTail = current;
    current = current.next;
  }

  this.tail = newTail;
  this.tail.next = null;
  this.length--;

  if (this.length === 0) {
    this.head = null;
    this.tail = null;
  }

  return current;
}

Time Complexity: $O(n)$ — Must traverse to the second-to-last node.

5. Accessing by Index (get)

The get method retrieves the node at a given 0-based index.

Unlike arrays, where index lookups are instant ($O(1)$) using memory offsets, a singly linked list must count forward from head step by step.

Step-by-Step Logic

1. Validate the index: if index < 0 or index >= this.length, return null.
2. Start a pointer current at this.head.
3. Loop index times, moving current = current.next.
4. Return current.

get(index) {
  if (index < 0 || index >= this.length) return null;
  let current = this.head;
  for (let i = 0; i < index; i++) {
    current = current.next;
  }
  return current;
}

Time Complexity: $O(n)$ — Requires sequential traversal from the head.

6. Updating by Index (set)

The set method modifies the value stored in the node at a specific index.

Step-by-Step Logic

1. Call get(index) to find the target node.
2. If found, update its value and return true.
3. If not found (index out of bounds), return false.

set(index, val) {
  const foundNode = this.get(index);
  if (foundNode) {
    foundNode.val = val;
    return true;
  }
  return false;
}

Time Complexity: $O(n)$ — Inherited from the traversal in get.

7. Inserting at Any Position (insert)

The insert method inserts a new node at any valid index (0 through length).

Step-by-Step Logic

1. If index < 0 or index > this.length, return false.
2. If index === 0, call unshift(val) to insert at the beginning.
3. If index === this.length, call push(val) to append at the end.
4. For middle positions:
   • Locate the node right before the target index using get(index - 1).
   • Create the new node.
   • Point the new node's next to prev.next.
   • Re-route prev.next to point to the new node.
5. Increment length and return true.

insert(index, val) {
  if (index < 0 || index > this.length) return false;
  if (index === 0) return Boolean(this.unshift(val));
  if (index === this.length) return Boolean(this.push(val));

  const prev = this.get(index - 1);
  const newNode = new Node(val);
  newNode.next = prev.next;
  prev.next = newNode;
  this.length++;
  return true;
}

Time Complexity: $O(n)$ — Finding the position takes $O(n)$ traversal, but the pointer rewiring itself is instant ($O(1)$).

8. Removing from Any Position (remove)

The remove method deletes the node at a given index and returns it.

Step-by-Step Logic

1. If index < 0 or index >= this.length, return null.
2. If index === 0, delegate to shift().
3. If index === this.length - 1, delegate to pop().
4. For middle positions:
   • Locate the previous node: prev = this.get(index - 1).
   • Identify the node to remove: removedNode = prev.next.
   • Bypass the removed node: prev.next = removedNode.next.
   • Clear removedNode.next = null.
5. Decrement length and return the removed node.

remove(index) {
  if (index < 0 || index >= this.length) return null;
  if (index === 0) return this.shift();
  if (index === this.length - 1) return this.pop();

  const prev = this.get(index - 1);
  const removedNode = prev.next;
  prev.next = removedNode.next;
  removedNode.next = null;
  this.length--;
  return removedNode;
}

Time Complexity: $O(n)$ — Locating the node takes $O(n)$, while unlinking is $O(1)$.

9. Reversing the List (reverse)

Reversing a singly linked list in-place is one of the classic data structure algorithms. It inverts the direction of all pointer links so that the head becomes the tail, the tail becomes the head, and all intermediate links point backward.

The Three-Pointer Algorithm

To flip links without losing references to the rest of the list, we maintain three pointers as we traverse:

1. prev: Starts at null.
2. current: Starts at this.head.
3. next: Temporarily preserves the upcoming node (current.next).

Step-by-Step Loop

1. Swap this.head and this.tail.
2. Loop while current is not null:
   • Store next = current.next (saves remaining chain).
   • Reverse pointer: current.next = prev.
   • Shift prev forward: prev = current.
   • Shift current forward: current = next.
3. Return the reversed list.

reverse() {
  let current = this.head;
  this.head = this.tail;
  this.tail = current;

  let prev = null;
  let next = null;

  while (current) {
    next = current.next;     // 1. Save next node
    current.next = prev;     // 2. Reverse pointer direction
    prev = current;          // 3. Step prev forward
    current = next;          // 4. Step current forward
  }

  return this;
}

Time Complexity: $O(n)$ — Single pass through all $n$ nodes.
Space Complexity: $O(1)$ — Done entirely in-place with three temporary pointer variables.

10. Displaying the List (print)

A helper method to print the elements of the list sequentially for debugging and inspection:

print() {
  const values = [];
  let current = this.head;
  while (current) {
    values.push(current.val);
    current = current.next;
  }
  console.log(values.join(" -> ") + " -> null");
}

Complete Implementation

Here is the complete, cohesive SinglyLinkedList implementation with all methods unified:

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  unshift(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  shift() {
    if (!this.head) return null;
    const removedNode = this.head;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    removedNode.next = null;
    return removedNode;
  }

  pop() {
    if (!this.head) return null;
    let current = this.head;
    let newTail = current;

    while (current.next) {
      newTail = current;
      current = current.next;
    }

    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }

    return current;
  }

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }

  set(index, val) {
    const foundNode = this.get(index);
    if (foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return Boolean(this.unshift(val));
    if (index === this.length) return Boolean(this.push(val));

    const prev = this.get(index - 1);
    const newNode = new Node(val);
    newNode.next = prev.next;
    prev.next = newNode;
    this.length++;
    return true;
  }

  remove(index) {
    if (index < 0 || index >= this.length) return null;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const prev = this.get(index - 1);
    const removedNode = prev.next;
    prev.next = removedNode.next;
    removedNode.next = null;
    this.length--;
    return removedNode;
  }

  reverse() {
    let current = this.head;
    this.head = this.tail;
    this.tail = current;

    let prev = null;
    let next = null;

    while (current) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    return this;
  }

  print() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.val);
      current = current.next;
    }
    console.log(values.join(" -> ") + " -> null");
  }
}

// Example Usage
const list = new SinglyLinkedList();
list.push(10).push(20).push(30);
list.print(); // 10 -> 20 -> 30 -> null

list.unshift(5);
list.print(); // 5 -> 10 -> 20 -> 30 -> null

list.insert(2, 15);
list.print(); // 5 -> 10 -> 15 -> 20 -> 30 -> null

list.reverse();
list.print(); // 30 -> 20 -> 15 -> 10 -> 5 -> null

Performance Summary

Singly Linked List vs. Arrays

Understanding the performance trade-offs between linked lists and arrays allows you to choose the right data structure for your specific use case.

Applications and When to Use a Singly Linked List

Optimal Use Cases

• Frequent changes at the head: Prepending and removing nodes both take $O(1)$ time.
• Stacks: Use unshift and shift to add and remove from the same end in $O(1)$ time.
• Queues: Use push at the tail and shift at the head; both operations take $O(1)$ time.
• Dynamic collections: The list grows and shrinks one node at a time.
• Building other structures: Singly linked lists can support chaining in hash maps and adjacency lists in graphs.

When to Avoid

• Frequent Random Index Lookups: If your application constantly reads values by index (e.g., data[450]), arrays provide instant $O(1)$ access whereas linked lists require slow $O(n)$ traversal.
• Strict Memory Limitations: Every node needs an additional next reference.
• Backward Traversal: A singly linked list cannot move directly from a node to its predecessor.

Key Takeaways

• Every node stores a value and one next reference.
• Links move from head to tail; there is no direct backward traversal.
• Push, unshift, and shift run in $O(1)$ time when the list tracks its tail.
• Pop takes $O(n)$ because the list must traverse from the head to find the node before the tail.
• Index-based access takes $O(n)$ because linked lists do not provide random access.
• Reversing the list takes $O(n)$ time and $O(1)$ auxiliary space.