Node and Linked List Structure

Linked lists are fundamental linear data structures that consist of nodes connected by pointers. Unlike arrays, linked lists do not store elements contiguously in memory; each element (node) contains a value and a reference (pointer) to the next node. This makes certain operations—like inserting or removing at the ends—very efficient, while others—like random access—inefficient. In the following lessons, we’ll use N to denote the number of nodes in the list when discussing time complexity.

---

Node Definition: class Node

Each element of a linked list is represented by a node.

• Syntax (JavaScript):

  class Node {
    constructor(value) {
      this.value = value;     // The data payload
      this.next = null;       // Pointer to the next node
    }
  }
  

• Time Complexity: O(1) – Creating a single node is a constant-time operation.

• Space Complexity: O(1) – One node instance holds exactly two properties.

let node = new Node(42);
console.log(node.value); // 42
console.log(node.next);  // null

---

Singly Linked List Class

A singly linked list maintains a reference to its head (first node), and optionally its tail (last node) and a length counter.

• Syntax (JavaScript):

  class LinkedList {
    constructor() {
      this.head = null;    // First node
      this.tail = null;    // Last node (for O(1) tail operations)
      this.length = 0;     // Number of nodes
    }
  }
  

• Initialization:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

let list = new LinkedList();
console.log(list.head, list.tail, list.length); // null, null, 0

---

Insertion Operations

1. Add at Head: .prepend(value)

Inserts a new node at the beginning of the list.

• Syntax:

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    if (!this.tail) this.tail = newNode;
    this.length++;
  }
  

• Time Complexity: O(1) – Only pointer reassignments.

• Space Complexity: O(1) – One new node.

list.prepend(10); // [10]
list.prepend(20); // [20 → 10]

---

2. Add at Tail: .append(value)

Inserts a new node at the end of the list.

• Syntax:

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

• Time Complexity: O(1) – Direct access via stored tail.

• Space Complexity: O(1) – One new node.

list.append(30); // [20 → 10 → 30]

---

3. Insert at Index: .insertAt(index, value)

Inserts at a specified position (0-based).

• Syntax:

  insertAt(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return this.prepend(value);
    if (index === this.length) return this.append(value);
  
    const newNode = new Node(value);
    let prev = this.head;
    for (let i = 1; i < index; i++) {
      prev = prev.next;
    }
    newNode.next = prev.next;
    prev.next = newNode;
    this.length++;
    return true;
  }
  

• Time Complexity: O(N) – Need to traverse up to index.

• Space Complexity: O(1) – One new node.

list.insertAt(1, 15); // [20 → 15 → 10 → 30]

---

Deletion Operations

1. Remove Head: .removeHead()

Removes the first node.

• Syntax:

  removeHead() {
    if (!this.head) return null;
    const removed = this.head;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return removed.value;
  }
  

• Time Complexity: O(1) – Direct pointer update.

• Space Complexity: O(1).

list.removeHead(); // returns 20, list is now [15 → 10 → 30]

---

2. Remove Tail: .removeTail()

Removes the last node.

• Syntax:

  removeTail() {
    if (!this.head) return null;
    if (this.head === this.tail) {
      const value = this.head.value;
      this.head = null;
      this.tail = null;
      this.length--;
      return value;
    }
    let current = this.head;
    while (current.next !== this.tail) {
      current = current.next;
    }
    const value = this.tail.value;
    current.next = null;
    this.tail = current;
    this.length--;
    return value;
  }
  

• Time Complexity: O(N) – Must traverse to the node before the tail.

• Space Complexity: O(1).

list.removeTail(); // returns 30, list is now [15 → 10]

---

3. Remove at Index: .removeAt(index)

Removes a node at a specific position.

• Syntax:

  removeAt(index) {
    if (index < 0 || index >= this.length) return null;
    if (index === 0) return this.removeHead();
    if (index === this.length - 1) return this.removeTail();
  
    let prev = this.head;
    for (let i = 1; i < index; i++) {
      prev = prev.next;
    }
    const removed = prev.next;
    prev.next = removed.next;
    this.length--;
    return removed.value;
  }
  

• Time Complexity: O(N) – Traverse to index - 1.

• Space Complexity: O(1).

list.removeAt(1); // returns 10, list is now [15]

---

Traversal & Search

Traversal

Visiting each node, e.g., to print values.

• Syntax:

  traverse() {
    let current = this.head;
    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
  

• Time Complexity: O(N) – Visits every node once.

• Space Complexity: O(1).

Search: .find(value)

Locate the first node containing the given value.

• Syntax:

  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }
  

• Time Complexity: O(N) – May check every node.

• Space Complexity: O(1).

console.log(list.find(15)); // Node { value: 15, next: null }

---

Practical Application: Reversing a Singly Linked List

Reversing a list in-place is a classic exercise.

Method 1: Iterative

• Concept: Walk through the list and reverse pointers one by one.
• Time Complexity: O(N) – Single pass.
• Space Complexity: O(1) – Three pointers only.

reverse() {
  let prev = null;
  let curr = this.head;
  this.tail = curr;
  while (curr) {
    let nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  this.head = prev;
}

Method 2: Recursive

• Concept: Recursively reverse the rest of the list, then fix the current node’s pointer.
• Time Complexity: O(N) – Each node processed once.
• Space Complexity: O(N) – Call stack frames.

reverseRecursive(node = this.head) {
  if (!node || !node.next) {
    this.head = node;
    return node;
  }
  const newHead = this.reverseRecursive(node.next);
  node.next.next = node;
  node.next = null;
  return newHead;
}

Note: Iterative reversal is generally preferred in production due to its constant space usage and no risk of call-stack overflow.