Linked List Operations (Insertion, Deletion, Traversal)

Linked List Operations: Insertion, Deletion, Traversal

Building on our understanding of nodes and list types, let’s dive into the core operations you’ll perform on linked lists. We’ll use a singly linked list as our primary example, but note the same concepts apply with minor pointer‐adjustments in doubly or circular variants. As always, N denotes the current number of nodes in the list.

---

1. Insertion

1.1. At Head: .prepend(value)

Adds a new node before the current head.

• Concept:

  1. Create a new node.
  2. Point its .next to the old head.
  3. Update head to the new node.
  4. If the list was empty, also set tail to the new node.
  5. Increment length.

• Time Complexity: O(1) (constant pointer updates)

• Space Complexity: O(1) (one new node)

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

---

1.2. At Tail: .append(value)

Adds a new node after the current tail.

• Concept:

  1. Create a new node.
  2. If the list is empty, set both head and tail to it.
  3. Otherwise, link the old tail.next to the new node and update tail.
  4. Increment length.

• Time Complexity: O(1) (direct tail pointer)

• Space Complexity: O(1)

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++;
}

---

1.3. At Arbitrary Position: .insertAt(index, value)

Inserts a node at a given zero-based index.

• Concept:

  1. Validate index (0 ≤ index ≤ length).
  2. If index === 0, delegate to .prepend().
  3. If index === length, delegate to .append().
  4. Otherwise, traverse to the node just before the target position.
  5. Splice in the new node.
  6. Increment length.

• Time Complexity: O(N) (may traverse up to index)

• Space Complexity: O(1)

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;
}

---

2. Deletion

2.1. Remove Head: .removeHead()

Deletes the first node and returns its value.

• Concept:

  1. If empty, return null.
  2. Store the old head.
  3. Update head to head.next.
  4. If now empty, also clear tail.
  5. Decrement length.
  6. Return removed value.

• Time Complexity: O(1)

• Space Complexity: O(1)

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;
}

---

2.2. Remove Tail: .removeTail()

Deletes the last node and returns its value.

• Concept:

  1. If empty, return null.
  2. If only one node, clear both head and tail.
  3. Otherwise, traverse to the node just before the tail.
  4. Update its .next to null and set it as new tail.
  5. Decrement length.
  6. Return removed value.

• Time Complexity: O(N) (must find the penultimate node)

• Space Complexity: O(1)

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

---

2.3. Remove at Index: .removeAt(index)

Deletes a node at a specified index.

• Concept:

  1. Validate index (0 ≤ index < length).
  2. If index === 0, delegate to .removeHead().
  3. If index === length − 1, delegate to .removeTail().
  4. Otherwise, traverse to the node just before the target.
  5. Splice out the target node.
  6. Decrement length.
  7. Return removed value.

• Time Complexity: O(N)

• Space Complexity: O(1)

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;
}

---

3. Traversal & Search

3.1. Traverse: .traverse(callback)

Visits each node in order, invoking a provided callback on its value.

• Concept:

  1. Start at head.
  2. While current node exists, call callback(current.value).
  3. Advance to current.next.

• Time Complexity: O(N)

• Space Complexity: O(1)

traverse(callback) {
  let curr = this.head;
  while (curr) {
    callback(curr.value);
    curr = curr.next;
  }
}

---

3.2. Search: .find(value)

Locates the first node containing the given value.

• Concept:

  1. Iterate from head to null.
  2. If current.value === value, return the node.
  3. If end is reached, return null.

• Time Complexity: O(N)

• Space Complexity: O(1)

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

---

Tip: Always keep track of length and tail pointers when relevant—they let you optimize many operations to O(1). For operations at arbitrary positions, expect linear time due to traversal.