C Linked List: Insert and Delete

insert_head is O(1). insert_tail is O(n). delete_node walks until the value is found, splices it out, frees. Three operations that build on the linked-list basics.

Building on episode 42, today we add the operations that make a linked list useful: insert at head, insert at tail, delete by value.

Insert at head

Node *insert_head(Node *head, int value) {
  Node *n = create_node(value);
  n->next = head;
  return n;
}

Three steps:

1. Create the new node.
2. Point its next at the old head.
3. Return the new node — caller reassigns to head.

head = insert_head(head, 5);

O(1) — fast regardless of list size. For most workloads where order doesn't matter, prepend.

Insert at tail

void insert_tail(Node *head, int value) {
  Node *n = create_node(value);
  Node *c = head;
  while (c->next != NULL) {
    c = c->next;
  }
  c->next = n;
}

Walk to the last node (whose next is NULL). Set its next to the new node. O(n).

For frequent tail inserts, store a tail pointer alongside head:

typedef struct {
  Node *head;
  Node *tail;
} List;

void insert_tail(List *list, int value) {
  Node *n = create_node(value);
  if (list->head == NULL) {
    list->head = list->tail = n;
  } else {
    list->tail->next = n;
    list->tail = n;
  }
}

Now both head and tail inserts are O(1).

The function takes a List * because it modifies head (when empty) and tail. Pointer-to-struct.

Insert at index

Node *insert_at(Node *head, int index, int value) {
  if (index == 0) return insert_head(head, value);

  Node *c = head;
  for (int i = 0; c != NULL && i < index - 1; i++) {
    c = c->next;
  }
  if (c == NULL) return head;   // index out of range

  Node *n = create_node(value);
  n->next = c->next;
  c->next = n;
  return head;
}

Walk to the node before the target index. Splice in the new node:

... -> c -> next ...
becomes:
... -> c -> n -> next ...

O(n) — same as walking to the position.

Delete by value

Node *delete_node(Node *head, int value) {
  if (head == NULL) return NULL;

  // delete first node?
  if (head->data == value) {
    Node *next = head->next;
    free(head);
    return next;
  }

  // find the predecessor of the target
  Node *c = head;
  while (c->next != NULL && c->next->data != value) {
    c = c->next;
  }

  if (c->next != NULL) {
    Node *temp = c->next;
    c->next = temp->next;
    free(temp);
  }

  return head;
}

Two cases:

1. Head matches. Save the new head; free the old; return the new.
2. Inner node matches. Walk to its predecessor; splice it out; free.

For "delete all occurrences," loop:

Node *delete_all(Node *head, int value) {
  while (head != NULL && head->data == value) {
    Node *next = head->next;
    free(head);
    head = next;
  }
  if (head == NULL) return NULL;

  Node *c = head;
  while (c->next != NULL) {
    if (c->next->data == value) {
      Node *temp = c->next;
      c->next = temp->next;
      free(temp);
    } else {
      c = c->next;
    }
  }
  return head;
}

The first loop strips matching prefix nodes. The second loop walks the rest, splicing out matches.

Delete by index

Node *delete_at(Node *head, int index) {
  if (head == NULL) return NULL;
  if (index == 0) {
    Node *next = head->next;
    free(head);
    return next;
  }

  Node *c = head;
  for (int i = 0; c->next != NULL && i < index - 1; i++) {
    c = c->next;
  }
  if (c->next == NULL) return head;   // index out of range

  Node *temp = c->next;
  c->next = temp->next;
  free(temp);
  return head;
}

Same pattern as insert_at — walk to predecessor, splice.

The "previous" trick

Many linked-list operations need the predecessor of the target. Two ways:

1. Two-pointer walk.

Node *prev = NULL;
Node *c = head;
while (c != NULL && c->data != target) {
  prev = c;
  c = c->next;
}
// prev points to the predecessor (or is NULL if c is head)

2. Look one ahead.

Node *c = head;
while (c->next != NULL && c->next->data != target) {
  c = c->next;
}
// c->next is the target

Both work. The "look ahead" version (used in our delete_node) is slightly cleaner for splice operations.

Sentinel nodes

A "dummy head" node that always exists simplifies edge cases:

typedef struct {
  Node sentinel;   // dummy; sentinel.next is the real head
} List;

Now:

• The list is never NULL — sentinel always exists.
• Inserting at head and at index N have the same code (no special case for index 0).
• Deleting head and any other has the same code.

Trade-off: extra node, slightly different API. Common in production linked-list libraries.

Detecting cycles

If your code accidentally creates a cycle (e.g., last->next = head), traversal loops forever. Detect with Floyd's algorithm:

int has_cycle(Node *head) {
  Node *slow = head;
  Node *fast = head;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return 1;
  }
  return 0;
}

Two pointers, one moving at 2× speed. If they meet, there's a cycle. Otherwise, fast hits NULL first.

Common mistakes

Losing the head reference. Functions that modify head must return the new head (or take Node **).

Not freeing the deleted node. Splicing alone doesn't free — you have to free the node too.

Iterating off-by-one for index operations. "Walk to index N" vs "walk to predecessor of index N" differ by one step.

Forgetting to handle empty list. head == NULL is a valid state; insert/delete must handle it.

Tail pointer staleness. When deleting, if you remove the tail, your stored tail pointer is stale. Update it.

Walking past NULL. c->next->data when c->next is NULL crashes. Always test c->next != NULL before dereferencing.

What's next

Episode 44: traverse, count, search. More walking patterns — count nodes, find by value, get by index.

Recap

insert_head is O(1) — make node, point at head, return. insert_tail is O(n) — walk to NULL, link. With a tail pointer, both are O(1). delete_node finds the predecessor and splices the target out, then frees. For "delete all," loop. Sentinel nodes simplify edge cases. Detect cycles with Floyd's two-pointer algorithm. Always free what you splice out; always return the new head if it changed.

Next episode: traverse, count, search.