AI Hints
Home›DSA in Python Tutorial›Linked Lists
DSA in Python · Lesson 36 of 132

Deleting Nodes

Re-pointing around a node.

⏱ 2 min read▶ Video at 41:46🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

To remove a node from a linked list, you don't move anything. You simply point the node before it at the node after it. The removed node is skipped, as if it was never there.

Deleting Nodes
From the video: Deleting Nodes
  • Nothing moves
  • Point around the node
  • It's skipped

Delete a value

If the head holds the value, the new head is simply the next node. Otherwise, we walk along, always looking one node ahead. When the next node holds the value, we point past it. Run it. Two has gone from the middle, and one from the front.

delete.pypython
from node import Node, show

def delete(head, value):
    if head and head.value == value:
        return head.next
    node = head
    while node and node.next:
        if node.next.value == value:
            node.next = node.next.next
            return head
        node = node.next
    return head

head = Node(1, Node(2, Node(3, Node(4))))
head = delete(head, 2); show(head)
head = delete(head, 1); show(head)
Output
1 -> 3 -> 4
3 -> 4
Also uses node.py
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def show(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals))

Pointer tips

Linked list bugs almost always come from losing a pointer. Draw boxes and arrows on paper first. Always check for none, before reading dot next. Handle the head as a special case. And test with an empty list, one node, and the last node.

keyvalue
Draw itboxes and arrows
Check Nonebefore .next
The heada special case
Test edgesempty, one, last

Summary

Deleting a node means pointing the previous node past it. Watch the head, and check for none. Next, the most famous linked list question. Reversing one.

Key takeaways
  • prev.next = node.next
  • Head is special
  • Check for None
Next up: Reversing a Linked List — flip every pointer