~/blog
Linked List Insertion and Deletion

Jun 2, 2026•15 min read•By Mohammed Vasim
dsapythondata-structuresalgorithmsproblem-solving
The Problem

Insert a node at a given position. Delete a node at a given position. These are the operations that make linked lists useful — O(1) at the point of operation, unlike an array where elements shift.
The difficulty is that insertion and deletion come in three variants, and the pointer order is different for each. Reverse two lines and you lose the rest of the list.
Insertion

Insert at Head

Example 1 — insert at head of a 3-node list.
Insert 99 at the head of 10 → 20 → 30 → None:
texttext
Before:  head → [10 | →] [20 | →] [30 | None]

Step 1:  new_node = Node(99)
  new_node = [99 | None]

Step 2:  new_node.next = head
  new_node = [99 | →] [10 | →] [20 | →] [30 | None]

Step 3:  head = new_node
  head → [99 | →] [10 | →] [20 | →] [30 | None]
```text

Three operations. Zero elements copied. Done.

**Example 2 — insert at head of an empty list.**

```texttext
Before:  head → None

Step 1:  new_node = Node(99)
  new_node = [99 | None]

Step 2:  new_node.next = None
  (head is None, so next is None — correct)

Step 3:  head = new_node
  head → [99 | None]
```text

New node becomes the only node. Works without a special case for empty lists because `head` is `None`, and `new_node.next = None` is exactly what the tail node should point to.

### Insert at Head — Code

```textpython
def insert_at_head(head: Node, data) -> Node:
    new_node = Node(data)
    new_node.next = head
    return new_node
```text

Line by line:

- `new_node = Node(data)` — create a new node. Its `.next` is initially `None`.
- `new_node.next = head` — wire the new node to point at whatever the current head is. If the list is empty, `head` is `None`, and `new_node.next` stays `None` — correct for a single-node list.
- `return new_node` — the new node is the new head. The caller must assign the return value: `head = insert_at_head(head, 99)`. Without this reassignment, the old head remains the head and the new node is unreachable.

The function returns the new head because the caller needs to update their reference. If the caller forgets to assign the return value, the list is corrupted.

**Time:** O(1) — two pointer operations regardless of list size. **Space:** O(1) — one new node.

Let us visualise insert-at-head on `10 → 20 → 30 → None`:

<svg role="img" aria-label="Before insert_at_head: head→10→20→30→None, new_node(99) created with next=None" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%">
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" font-weight="600" text-anchor="start" x="10" y="45">head</text>
  <path d="M 55 40 L 85 40" marker-end="url(#iaharrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="95" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="135" y="45">10</text>
  <path d="M 175 40 L 205 40" marker-end="url(#iaharrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1.5" x="215" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="255" y="45">20</text>
  <path d="M 295 40 L 325 40" marker-end="url(#iaharrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="335" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="375" y="45">30</text>
  <path d="M 415 40 L 445 40" marker-end="url(#iaharrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="455" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="490" y="45">None</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="13" font-weight="600" text-anchor="middle" x="135" y="80">existing list</text>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" stroke-dasharray="4 2" x="220" y="68"></rect>
  <text fill="#f59e0b" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="260" y="87">new_node(99)</text>
  <defs><marker id="iaharrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="After insert_at_head: new_node.next=head (points to 10), head=new_node. Result: head→99→10→20→30→None" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%">
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" font-weight="600" text-anchor="start" x="10" y="45">head</text>
  <path d="M 55 40 L 85 40" marker-end="url(#iah2arrow)" stroke="#f59e0b" stroke-width="2"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="95" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="135" y="45">99</text>
  <path d="M 175 40 L 205 40" marker-end="url(#iah2arrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="215" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="255" y="45">10</text>
  <path d="M 295 40 L 325 40" marker-end="url(#iah2arrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1.5" x="335" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="375" y="45">20</text>
  <path d="M 415 40 L 445 40" marker-end="url(#iah2arrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="455" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="490" y="45">30</text>
  <text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="135" y="80">new head</text>
  <text fill="#94a3b8" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="255" y="80">was head</text>
  <defs><marker id="iah2arrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

### Insert at Tail

**Example 3 — insert at tail of a 3-node list.**

Insert `99` at the tail of `10 → 20 → 30 → None`:

```text
Before:  head → [10 | →] [20 | →] [30 | None]

Walk:    current moves: 10 → 20 → 30
         current.next is None → stop at 30

Step 1:  current.next = Node(99)
After:   head → [10 | →] [20 | →] [30 | →] [99 | None]
```text

Walking to the tail is O(n). Without a tail pointer, you must traverse every time.

**Example 4 — insert at tail of an empty list.**

```text
Before:  head → None

Check:   head is None → return new_node as head
After:   head → [99 | None]
```text

The early return handles this case. Without it, `head.next` (or `current.next` starting from `head`) would raise `AttributeError`.

### Insert at Tail — Code

```textpython
def insert_at_tail(head: Node, data) -> Node:
    new_node = Node(data)

    if head is None:
        return new_node

    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head
```text

Line by line:

- `new_node = Node(data)` — create a new node.
- `if head is None: return new_node` — empty list case. The new node becomes the head.
- `current = head` — start at the first node.
- `while current.next:` — walk until `current.next` is `None`, meaning `current` is the last node. Using `current.next` as the condition (not `current`) stops one step earlier than a full traversal, leaving `current` at the tail.
- `current.next = new_node` — attach the new node after the tail.
- `return head` — the head has not changed.

**Performance note.** This is O(n) because you walk the entire list to find the tail. Maintaining a separate `tail` pointer in the `LinkedList` class makes it O(1).

**Time:** O(n) without tail pointer, O(1) with one. **Space:** O(1).

### Code Trace — `insert_at_tail(head_of_10_20, 99)`

`head` points to `10 → 20 → None`.

| Iteration | current (before) | current.next | Action | current (after) |
|---|---|---|---|---|
| 1 | node(10) | node(20) — not None | advance | node(20) |
| 2 | node(20) | None | exit loop | — |

After loop: `current = node(20)`. `current.next = None` → attach new node.

`current.next = new_node(99)` → `10 → 20 → 99 → None`.

Let us visualise:

<svg role="img" aria-label="insert_at_tail: current walks from node(10) to node(20). current.next was None, now attach new_node(99)." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#tarrow1)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#tarrow1)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="290" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">None</text>
  <path d="M 165 70 L 165 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="165,90 160,80 170,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="165" y="98">current</text>
  <defs><marker id="tarrow1" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="insert_at_tail: current.next=new_node(99) attaches 99 after 20. Now list is 10→20→99→None." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#tarrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#tarrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="330" y="45">99</text>
  <path d="M 385 40 L 415 40" marker-end="url(#tarrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="465" y="45">None</text>
  <defs><marker id="tarrow2" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

### Insert at Position i

**Example 5 — insert at position 2 (0-indexed) in a 3-node list.**

Insert `99` at index 2 in `10 → 20 → 30 → None`:

```text
Walk to position 1 (one before index 2):
    current starts at 10 (position 0)
    step 1: current → 20 (position 1)

Wire new node between current (20) and current.next (30):
    new_node.next = current.next  →  99 → 30
    current.next = new_node       →  20 → 99

Result:  10 → 20 → 99 → 30 → None
```text

**Example 6 — insert at position 0 (same as insert-at-head).**

Index 0 is the head insertion case. The function delegates to the same logic.

**Example 7 — insert at the last position (position = length).**

Insert `99` at index 3 in `10 → 20 → 30 → None` (length 3):

```text
Walk to position 2 (one before index 3):
    current starts at 10 (position 0)
    step 1: current → 20 (position 1)
    step 2: current → 30 (position 2)

current.next is None (tail). Wire:
    new_node.next = None  →  99 → None (correct for new tail)
    current.next = new_node  →  30 → 99

Result:  10 → 20 → 30 → 99 → None
```text

### Insert at Position — Code

```textpython
def insert_at_position(head: Node, data, position: int) -> Node:
    if position == 0:
        new_node = Node(data)
        new_node.next = head
        return new_node

    current = head
    for _ in range(position - 1):
        if current is None:
            raise IndexError("Position out of bounds")
        current = current.next

    new_node = Node(data)
    new_node.next = current.next
    current.next = new_node
    return head
```text

Line by line:

- `if position == 0:` — insert at head. Same logic as `insert_at_head`.
- `current = head` — start at the first node.
- `for _ in range(position - 1):` — walk to the node just before the target position. `range(position - 1)` gives exactly `position - 1` iterations. For position 2, this walks one step to node at index 1.
- `if current is None:` — the position is beyond the list length. Raise an error rather than silently inserting at the end or crashing.
- `new_node = Node(data)` — create the new node.
- `new_node.next = current.next` — point the new node to whatever `current` was pointing to. This step must happen before the next line — if you set `current.next = new_node` first, you lose the reference to the rest of the list.
- `current.next = new_node` — point `current` to the new node.

**Edge case — position equals length.** The loop walks `current` to the last node (whose `.next` is `None`). `new_node.next = None` is correct — the new node becomes the tail.

**Edge case — position beyond length.** `current` becomes `None` during the loop. Raises `IndexError`.

**Time:** O(n) to reach position i, then O(1) for the pointer swap. **Space:** O(1).

### Code Trace — `insert_at_position(head_of_10_20_30, 99, 2)`

`head` points to `10 → 20 → 30 → None`. Insert `99` at index 2 (between 20 and 30).

| Iteration | current (before) | position covered | Action | current (after) |
|---|---|---|---|---|
| 1 | node(10) at pos 0 | position 0 | start: `current = head` | node(10) |
| 2 | node(10) at pos 0 | position 0→1 | `for _ in range(1)`: advance | node(20) at pos 1 |
| 3 | node(20) at pos 1 | — | loop ends, `current = node(20)` | — |

After loop: `current = node(20)`, `current.next = node(30)`.

Now the pointer swaps:

```text
new_node = Node(99)
new_node.next = current.next   →  new_node.next = node(30)
current.next = new_node        →  node(20).next = new_node
```text

Final: `10 → 20 → 99 → 30 → None`.

Let us visualise the final state after pointer swap:

<svg role="img" aria-label="insert_at_position: new_node(99) inserted at index 2. List is now 10→20→99→30→None." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#iparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#iparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">99</text>
  <path d="M 385 40 L 415 40" marker-end="url(#iparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="425" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="475" y="45">30</text>
  <path d="M 520 40 L 550 40" marker-end="url(#iparrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="560" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="595" y="45">None</text>
  <defs><marker id="iparrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

## Deletion

### Delete at Head

**Example 8 — delete head of a 3-node list.**

Delete the head of `10 → 20 → 30 → None`:

```text
Before:  head → [10 | →] [20 | →] [30 | None]

Step 1:  new_head = head.next
  →  [20 | →]

After:   head → [20 | →] [30 | None]
```text

The old head (10) has no remaining references and is garbage-collected.

**Example 9 — delete head of a single-node list.**

```text
Before:  head → [10 | None]

Step 1:  new_head = head.next   →  None
After:   head → None
```text

Empty list. Correct.

### Delete at Head — Code

```textpython
def delete_at_head(head: Node) -> Node:
    if head is None:
        return None
    return head.next
```text

Line by line:

- `if head is None: return None` — empty list. Nothing to delete.
- `return head.next` — skip the first node. If there is only one node, `head.next` is `None`, and the list becomes empty.

**Time:** O(1). **Space:** O(1).

### Delete at Tail

**Example 10 — delete tail of a 3-node list.**

Delete the tail of `10 → 20 → 30 → None`:

```text
Walk to second-to-last:
    current starts at 10
    check: current.next.next is not None → current.next.next is 30 → advance
    current → 20
    check: current.next.next is None → stop

Set current.next = None:
    Before:  10 → 20 → 30 → None
    After:   10 → 20 → None
```text

**Example 11 — delete tail of a single-node list.**

```text
Before:  head → [10 | None]

Check:   head.next is None → return None
After:   head → None
```text

### Delete at Tail — Code

```textpython
def delete_at_tail(head: Node) -> Node:
    if head is None or head.next is None:
        return None

    current = head
    while current.next.next:
        current = current.next
    current.next = None
    return head
```text

Line by line:

- `if head is None or head.next is None: return None` — empty list or single node. Either way, the result is an empty list.
- `current = head` — start at the first node.
- `while current.next.next:` — check two steps ahead. If `current.next.next` exists, there is a node after the next one, so `current` is not the second-to-last. Advance while this is true.
- `current.next = None` — `current` is now the second-to-last node. Cut off the tail.
- `return head` — head has not changed.

**Time:** O(n). **Space:** O(1).

### Code Trace — `delete_at_tail(head_of_10_20_30_40_50)`

`head` points to `10 → 20 → 30 → 40 → 50 → None`. Delete the tail (node with 50).

| Iteration | current (before) | current.next | current.next.next | Action | current (after) |
|---|---|---|---|---|---|
| 1 | node(10) | node(20) | node(30) — not None | advance | node(20) |
| 2 | node(20) | node(30) | node(40) — not None | advance | node(30) |
| 3 | node(30) | node(40) | node(50) — not None | advance | node(40) |
| 4 | node(40) | node(50) | None — exit loop | — | — |

After loop: `current = node(40)`. `current.next = None` removes node(50).

Final: `10 → 20 → 30 → 40 → None`.

<svg role="img" aria-label="delete_at_tail: current advances through 10→20→30→40, then sets current.next=None, removing 50. Result: 10→20→30→40→None." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/2000/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#dtarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#dtarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">30</text>
  <path d="M 385 40 L 415 40" marker-end="url(#dtarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="425" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="475" y="45">40</text>
  <path d="M 520 40 L 550 40" marker-end="url(#dtarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="560" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="595" y="45">None</text>
  <path d="M 435 70 L 435 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="435,90 430,80 440,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="435" y="98">current</text>
  <defs><marker id="dtarrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

### Delete at Position i

**Example 12 — delete at position 1 (second node).**

Delete at index 1 in `10 → 20 → 30 → None`:

```text
Walk to position 0 (one before index 1):
    current stays at 10

Skip the node at position 1:
    current.next = current.next.next
    Before:  10 → 20 → 30 → None
    After:   10 → 30 → None
```text

Node 20 is skipped. No remaining references to it → garbage-collected.

### Delete at Position — Code

```textpython
def delete_at_position(head: Node, position: int) -> Node:
    if head is None:
        return None

    if position == 0:
        return head.next

    current = head
    for _ in range(position - 1):
        if current is None or current.next is None:
            raise IndexError("Position out of bounds")
        current = current.next

    current.next = current.next.next
    return head
```text

Line by line:

- `if head is None: return None` — nothing to delete.
- `if position == 0: return head.next` — delete the head. Same logic as `delete_at_head`.
- `current = head` — start at the first node.
- `for _ in range(position - 1):` — walk to the node before the target position.
- `if current is None or current.next is None:` — `current` being None means position is past the end. `current.next` being None means the target position does not exist (there is nothing to delete).
- `current.next = current.next.next` — skip the target node. If `current.next` is the last node, `current.next.next` is `None`, which means `current.next` becomes `None` — the new tail is correct.

**Time:** O(n) to reach position i, O(1) for the pointer skip. **Space:** O(1).

### Code Trace — `delete_at_position(head_of_10_20_30_40_50, 3)`

Delete at index 3 in `10 → 20 → 30 → 40 → 50 → None` (node with value 40).

| Iteration | current (before) | position covered | Action | current (after) |
|---|---|---|---|---|
| start | node(10) at pos 0 | — | `current = head` | node(10) |
| step 1 | node(10) | pos 0 | `range(2)`: advance | node(20) at pos 1 |
| step 2 | node(20) | pos 1 | `range(2)`: advance | node(30) at pos 2 |
| loop ends | node(30) at pos 2 | — | `range(2)` gave 2 steps | — |

After loop: `current = node(30)`. `current.next = node(40)`. `current.next.next = node(50)`.

Set `current.next = current.next.next` → `node(30).next = node(50)` → skips node(40).

Final: `10 → 20 → 30 → 50 → None`.

<svg role="img" aria-label="delete_at_position(3): current walks to node(30), then current.next=current.next.next skips node(40). Result: 10→20→30→50→None." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#dparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#dparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">30</text>
  <path d="M 385 40 L 415 40" marker-end="url(#dparrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fee2e2" rx="6" stroke="#dc2626" stroke-width="1.5" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="475" y="45">40</text>
  <path d="M 520 40 L 550 40" marker-end="url(#dparrow)" stroke="#94a3b8" stroke-width="1.5" stroke-dasharray="4 2"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="560" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="600" y="45">50</text>
  <path d="M 475 70 L 475 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="475,90 470,80 480,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="475" y="98">current</text>
  <defs><marker id="dparrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

## When Insert and Delete Beat Arrays

Linked list insertion and deletion are O(1) at the point of operation. Arrays shift everything. The linked list pays for this with slower traversal. Use it when your workload is insert-heavy at known positions — queues, caches, and in-memory manipulation where the cost of shifting elements dominates.

The music player queue from the first post: inserting "play next" at the front is O(1). Array insert at front is O(n). That gap is the entire reason linked lists exist.

Every operation in this post — head, tail, position — requires walking to the target node first. That walk is O(n) and unavoidable when you do not have a direct address. The next post covers searching: what happens when you need to find a node before you can insert or delete it.
Linked List Insertion and Deletion

The Problem

Insertion

Insert at Head

Comments (0)

Leave a comment
