Visualizer › Linked List
Linked List Deletion
Deletes a value: find the node and the one before it, then point the previous node past it.
How it works
- Deleting the head just moves the head.
- Keep a prev pointer while walking.
- A dummy node before the head removes the special case.
Complexity
- Best time: O(1)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(1)
Code (Python)
def delete(head, value):
dummy = Node(0, head)
prev, curr = dummy, head
while curr:
if curr.val == value:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.nextPractise: Linked List problems