Linked List Insertion

Insertion

Linked List insertion involves adding new nodes to the linked data structure at various positions. Unlike arrays, linked lists allow efficient insertion at any point without reallocation or shifting of existing elements.

Insertion is a fundamental operation that enables dynamic growth of the list. The efficiency varies based on insertion position, from O(1) for head/tail (with tail pointer) to O(n) for arbitrary positions.

Mastering insertion techniques is crucial for building more complex data structures and algorithms that utilize linked lists as their foundation.

Key Insight: Linked list insertion doesn't require shifting elements like arrays, but does require careful pointer manipulation to maintain list integrity.

Insertion Types

Insertion at Head

Complexity: O(1)

Adds new node at the beginning, making it the new head

function insertHead(data) {
  const newNode = new Node(data);
  newNode.next = head;
  head = newNode;
}

Insertion at Tail

Complexity: O(1) with tail pointer, O(n) without

Appends new node at the end of the list

function insertTail(data) {
  const newNode = new Node(data);
  if (!head) {
    head = newNode;
    tail = newNode;
  } else {
    tail.next = newNode;
    tail = newNode;
  }
}

Insertion at Position

Complexity: O(n)

Inserts node at specific index (0-based)

function insertAt(data, position) {
  if (position === 0) return insertHead(data);
  
  let current = head;
  for (let i = 0; i < position-1 && current; i++) {
    current = current.next;
  }
  
  if (!current) return; // Position out of bounds
  
  const newNode = new Node(data);
  newNode.next = current.next;
  current.next = newNode;
  
  if (!newNode.next) tail = newNode;
}

Insertion After Node

Complexity: O(1)

Inserts new node after a given reference node

function insertAfter(refNode, data) {
  const newNode = new Node(data);
  newNode.next = refNode.next;
  refNode.next = newNode;
  
  if (refNode === tail) tail = newNode;
}

Insertion Processes

Head Insertion

  1. Create a new node with the given data
  2. Set the new node's next pointer to current head
  3. Update the head pointer to point to the new node
  4. Special case: If list was empty, update tail pointer too

Tail Insertion

  1. Create a new node with the given data
  2. If list is empty, set both head and tail to new node
  3. Otherwise, set current tail's next pointer to new node
  4. Update tail pointer to the new node

Middle Insertion

  1. Traverse the list to find the insertion position
  2. Create a new node with the given data
  3. Set new node's next to the next node of current position
  4. Set current node's next pointer to the new node
  5. Special case: If inserting at end, update tail pointer

Operation Visualization

OperationList State
Initial Statehead → [A] → [B] → [C] → null
insertHead(X)head → [X] → [A] → [B] → [C] → null
insertTail(Y)head → [X] → [A] → [B] → [C] → [Y] → null
insertAt(Z, 2)head → [X] → [A] → [Z] → [B] → [C] → [Y] → null

Edge Cases to Consider

Empty list (head = null)

Insertion at position 0 (becomes new head)

Insertion at position = list length (becomes new tail)

Insertion at position > list length (should handle gracefully)

Insertion after tail node (should update tail pointer)

Insertion with invalid node references

Best Practices

Always check for empty list condition

Maintain tail pointer for O(1) tail insertion

Validate position bounds before insertion

Update tail pointer when inserting at end

Consider using dummy nodes to simplify edge cases

Document whether position is 0-based or 1-based

Comparison with Array Insertion

FeatureArrayLinked List
Time ComplexityO(n) (requires shifting)O(1) head/tail, O(n) arbitrary
Space ComplexityO(1) (amortized)O(1) per insertion
Memory UsageMay need reallocationNo reallocation needed
ImplementationSimple indexingPointer manipulation
Best ForFrequent random accessFrequent insertions/deletions

When to Choose: Prefer linked lists when you need frequent insertions at arbitrary positions and don't require random access. Use arrays when you need index-based access and memory efficiency for small, fixed-size collections.

Implementation Notes

  • Memory Management: Remember to properly allocate memory for new nodes in languages that require manual memory management
  • Error Handling: Always validate input parameters and handle edge cases gracefully
  • Testing: Thoroughly test all insertion scenarios including empty list, single-node list, head/tail insertions
  • Optimizations: Consider maintaining both head and tail pointers for O(1) insertions at both ends

Visualize Linked List Insertion

Data
Next Pointer
No nodes added yet

Test Your Knowledge before moving forward!

Insertion Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Linked List Insertion Implementation

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

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

  // 1. Insert at beginning
  insertFirst(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // 2. Insert at end
  insertLast(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // 3. Insert at specific index
  insertAt(data, index) {
    if (index < 0 || index > this.size) {
      console.log("Invalid index");
      return;
    }
    
    if (index === 0) {
      this.insertFirst(data);
      return;
    }
    
    const newNode = new Node(data);
    let current = this.head;
    let count = 0;
    
    // Traverse to the node before the insertion point
    while (count < index - 1) {
      current = current.next;
      count++;
    }
    
    newNode.next = current.next;
    current.next = newNode;
    this.size++;
  }

  // Print the list
  printList() {
    let current = this.head;
    let result = "";
    while (current) {
      result += current.data + " -> ";
      current = current.next;
    }
    result += "null";
    console.log(result);
  }
}

// Usage Example
const sll = new SinglyLinkedList();
sll.insertFirst(100);  // List: 100 -> null
sll.insertFirst(200);  // List: 200 -> 100 -> null
sll.insertLast(300);   // List: 200 -> 100 -> 300 -> null
sll.insertAt(500, 1);  // List: 200 -> 500 -> 100 -> 300 -> null
sll.printList();

Explore Other Types

Traversal

Deletion

Searching

Merging

Comparison

Reverse