Insertion Operations

Types of Insertion Operations

There are three main ways to insert a node into a linked list:

1. Insert at the beginning (prepend)
2. Insert at the end (append)
3. Insert at a specific position

Let's explore each of these operations in detail.

1. Insert at the Beginning (Prepend)

Inserting a node at the beginning of a linked list is a simple operation:

1. Create a new node with the given value
2. Set the new node's next pointer to the current head
3. Update the head to point to the new node

prepend(value) {
  // Create a new node
  const newNode = new Node(value);
  
  // Set the new node's next pointer to the current head
  newNode.next = this.head;
  
  // Update the head to point to the new node
  this.head = newNode;
}

Time Complexity: O(1) - This is a constant-time operation as it only requires updating a few pointers, regardless of the list size.

2. Insert at the End (Append)

We've already seen the append operation in the previous tutorial. Here's a reminder of how it works:

1. Create a new node with the given value
2. If the list is empty, make the new node the head
3. Otherwise, traverse to the end of the list
4. Set the last node's next pointer to the new node

append(value) {
  // Create a new node
  const newNode = new Node(value);
  
  // If the list is empty, make the new node the head
  if (!this.head) {
    this.head = newNode;
    return;
  }
  
  // Traverse to the end of the list
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  
  // Set the last node's next pointer to the new node
  current.next = newNode;
}

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

3. Insert at a Specific Position

Inserting at a specific position combines elements of both previous operations:

1. If position is 0, use the prepend method
2. Create a new node with the given value
3. Traverse the list to the node just before the desired position
4. Update the pointers to insert the new node

insertAt(value, position) {
  // If position is 0, use prepend
  if (position === 0) {
    this.prepend(value);
    return;
  }
  
  // Create a new node
  const newNode = new Node(value);
  
  // Traverse to the node just before the desired position
  let current = this.head;
  let count = 0;
  
  while (current && count < position - 1) {
    current = current.next;
    count++;
  }
  
  // If position is beyond the length of the list, append to the end
  if (!current) {
    this.append(value);
    return;
  }
  
  // Update pointers to insert the new node
  newNode.next = current.next;
  current.next = newNode;
}

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

Interactive Example

Try inserting nodes at different positions in the linked list below:

Check Your Understanding