Linked List Operations: Insert, Delete, and Search

The core operations on a linked list are inserting and deleting nodes (at the head, tail, or a middle position) and searching for a value. Each comes down to carefully rewiring next pointers in the right order. This page covers every case with its complexity, and introduces the dummy-head trick that makes the messy edge cases disappear. Examples use a singly linked list node.

Insert at the head — O(1)

Point the new node at the current head, then return it as the new head. No walking needed.

Node* insertHead(Node* head, int value) {
    Node* node = new Node(value);
    node->next = head;
    return node;
}

Node insertHead(Node head, int value) {
    Node node = new Node(value);
    node.next = head;
    return node;
}

function insertHead(head, value) {
  const node = new Node(value);
  node.next = head;
  return node;
}

def insert_head(head, value):
    node = Node(value)
    node.next = head
    return node

Insert at the tail — O(n)

Walk to the last node, then attach. (With a stored tail pointer this is O(1), but the bare version must traverse.)

Node* insertTail(Node* head, int value) {
    Node* node = new Node(value);
    if (head == nullptr) return node;
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
    return head;
}

Node insertTail(Node head, int value) {
    Node node = new Node(value);
    if (head == null) return node;
    Node cur = head;
    while (cur.next != null) cur = cur.next;
    cur.next = node;
    return head;
}

function insertTail(head, value) {
  const node = new Node(value);
  if (head === null) return node;
  let cur = head;
  while (cur.next !== null) cur = cur.next;
  cur.next = node;
  return head;
}

def insert_tail(head, value):
    node = Node(value)
    if head is None:
        return node
    cur = head
    while cur.next is not None:
        cur = cur.next
    cur.next = node
    return head

Insert at a middle position — O(n)

To insert at 0-based index pos, stop at the node before it, then splice. Order matters: set the new node’s next before rewiring the predecessor, or you lose the rest of the list.

Node* insertAt(Node* head, int pos, int value) {
    if (pos <= 0 || head == nullptr) return insertHead(head, value);
    Node* cur = head;
    for (int i = 0; i < pos - 1 && cur->next != nullptr; i++)
        cur = cur->next;
    Node* node = new Node(value);
    node->next = cur->next;   // first
    cur->next = node;         // then
    return head;
}

Node insertAt(Node head, int pos, int value) {
    if (pos <= 0 || head == null) return insertHead(head, value);
    Node cur = head;
    for (int i = 0; i < pos - 1 && cur.next != null; i++)
        cur = cur.next;
    Node node = new Node(value);
    node.next = cur.next;     // first
    cur.next = node;          // then
    return head;
}

function insertAt(head, pos, value) {
  if (pos <= 0 || head === null) return insertHead(head, value);
  let cur = head;
  for (let i = 0; i < pos - 1 && cur.next !== null; i++)
    cur = cur.next;
  const node = new Node(value);
  node.next = cur.next;       // first
  cur.next = node;            // then
  return head;
}

def insert_at(head, pos, value):
    if pos <= 0 or head is None:
        return insert_head(head, value)
    cur = head
    i = 0
    while i < pos - 1 and cur.next is not None:
        cur = cur.next
        i += 1
    node = Node(value)
    node.next = cur.next      # first
    cur.next = node           # then
    return head

Delete by value with a dummy head — O(n)

Deletion is where edge cases bite: removing the head is different from removing a middle node. The fix is a dummy node that sits before the real head, so every node has a predecessor and the head case stops being special. Return dummy.next as the new head.

Node* deleteValue(Node* head, int target) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next != nullptr) {
        if (prev->next->data == target) {
            Node* doomed = prev->next;
            prev->next = doomed->next;   // unlink
            delete doomed;
            break;                       // remove first match only
        }
        prev = prev->next;
    }
    return dummy.next;
}

Node deleteValue(Node head, int target) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node prev = dummy;
    while (prev.next != null) {
        if (prev.next.data == target) {
            prev.next = prev.next.next;  // unlink
            break;                       // remove first match only
        }
        prev = prev.next;
    }
    return dummy.next;
}

function deleteValue(head, target) {
  const dummy = new Node(0);
  dummy.next = head;
  let prev = dummy;
  while (prev.next !== null) {
    if (prev.next.data === target) {
      prev.next = prev.next.next;        // unlink
      break;                             // remove first match only
    }
    prev = prev.next;
  }
  return dummy.next;
}

def delete_value(head, target):
    dummy = Node(0)
    dummy.next = head
    prev = dummy
    while prev.next is not None:
        if prev.next.data == target:
            prev.next = prev.next.next   # unlink
            break                        # remove first match only
        prev = prev.next
    return dummy.next

Search — O(n)

Walk forward, returning the 0-based index of the first match or -1.

int indexOf(Node* head, int target) {
    int i = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next, i++)
        if (cur->data == target) return i;
    return -1;
}

int indexOf(Node head, int target) {
    int i = 0;
    for (Node cur = head; cur != null; cur = cur.next, i++)
        if (cur.data == target) return i;
    return -1;
}

function indexOf(head, target) {
  let i = 0;
  for (let cur = head; cur !== null; cur = cur.next, i++)
    if (cur.data === target) return i;
  return -1;
}

def index_of(head, target):
    i = 0
    cur = head
    while cur is not None:
        if cur.data == target:
            return i
        cur = cur.next
        i += 1
    return -1

Complexity at a glance

Operation	Time	Space
Insert/delete at head	O(1)	O(1)
Insert/delete at tail	O(n)*	O(1)
Insert/delete at index	O(n)	O(1)
Search by value	O(n)	O(1)

*O(1) if you maintain a tail pointer.

For beginners: The rule that prevents most bugs — when relinking, save the node you’re about to skip before you overwrite its pointer. Once you reassign cur->next, the old successor is unreachable unless you grabbed it first.

Going deeper: The dummy-head pattern generalizes far beyond deletion. Any time the head might change — merging two sorted lists, partitioning, removing the Nth node — start from a dummy and return dummy.next. It removes an entire class of null-handling bugs.

Next: apply these to reversing a linked list and the fast & slow pointers technique, then test yourself with the exercises.