Deletion Operations

Types of Deletion Operations

There are several ways to delete nodes from a linked list:

1. Delete the first node (head)
2. Delete the last node (tail)
3. Delete a node at a specific position
4. Delete a node with a specific value

Let's explore each of these operations in detail.

1. Delete the First Node (Head)

Deleting the first node is straightforward:

1. Check if the list is empty
2. Update the head to point to the second node

deleteFirst() {
  // Check if the list is empty
  if (!this.head) {
    return;
  }
  
  // Update the head to point to the second node
  this.head = this.head.next;
}

Time Complexity: O(1) - This is a constant-time operation as it only requires updating the head pointer.

2. Delete the Last Node (Tail)

Deleting the last node requires traversing the list to find the second-to-last node:

1. Check if the list is empty or has only one node
2. Traverse the list to find the second-to-last node
3. Set the second-to-last node's next pointer to null

deleteLast() {
  // Check if the list is empty
  if (!this.head) {
    return;
  }
  
  // If there's only one node, delete it
  if (!this.head.next) {
    this.head = null;
    return;
  }
  
  // Traverse to find the second-to-last node
  let current = this.head;
  while (current.next.next) {
    current = current.next;
  }
  
  // Set the second-to-last node's next pointer to null
  current.next = null;
}

Time Complexity: O(n) - This operation requires traversing the list to find the second-to-last node, making it linear in the size of the list.

3. Delete a Node at a Specific Position

Deleting a node at a specific position combines elements of the previous operations:

1. If position is 0, use the deleteFirst method
2. Traverse the list to the node just before the target position
3. Update the pointers to skip the node to be deleted

deleteAt(position) {
  // Check if the list is empty
  if (!this.head) {
    return;
  }
  
  // If position is 0, delete the first node
  if (position === 0) {
    this.head = this.head.next;
    return;
  }
  
  // Traverse to the node just before the target position
  let current = this.head;
  let count = 0;
  
  while (current.next && count < position - 1) {
    current = current.next;
    count++;
  }
  
  // If the position is valid, update pointers to skip the node
  if (current.next) {
    current.next = current.next.next;
  }
}

Time Complexity: O(n) - In the worst case, we need to traverse to the end of the list, making this a linear-time operation.

4. Delete a Node with a Specific Value

Deleting a node with a specific value requires searching for the node first:

1. Check if the list is empty
2. If the head node has the target value, delete it
3. Otherwise, traverse the list to find the node with the target value
4. Update the pointers to skip the node to be deleted

delete(value) {
  // Check if the list is empty
  if (!this.head) {
    return;
  }
  
  // If the head node has the target value, delete it
  if (this.head.value === value) {
    this.head = this.head.next;
    return;
  }
  
  // Traverse the list to find the node with the target value
  let current = this.head;
  while (current.next && current.next.value !== value) {
    current = current.next;
  }
  
  // If the node is found, update pointers to skip it
  if (current.next) {
    current.next = current.next.next;
  }
}

Time Complexity: O(n) - This operation requires traversing the list to find the node with the target value, making it linear in the size of the list.

Interactive Example

Try deleting nodes from the linked list below:

Check Your Understanding