Linked List Operations
DSA · Linked Lists
Theory
The core operations are inserting at the head, tail or after a node, deleting a node by value, searching, and reversing. Reversal walks the list once while redirecting each node's next pointer to the previous node, using three variables: prev, cur and next. Careful pointer updates in the right order are the whole skill: updating a pointer too early loses the rest of the list.
Why we use it
These operations appear in almost every linked-list interview question and teach careful pointer manipulation.
When to use it
Use them when implementing stacks, queues, playlists, or when solving reversal, merge and removal problems.
How it works
- Choose operation
- Insert at head? Yes: new.next = head; head = new. No: Find the node before the position.
- Delete? Yes: prev.next = prev.next.next. No: new.next = prev.next; prev.next = new.
- Done: only pointers change, no shifting
Syntax
Reverse:
prev = None; cur = head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
head = prev # O(n) time, O(1) spaceExample
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
out = []
while head:
out.append(str(head.val)); head = head.next
return " -> ".join(out)
def delete_value(head, target):
dummy = Node(0, head)
cur = dummy
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev, head = head, nxt
return prev
h = build([1, 2, 3, 4, 5])
h = delete_value(h, 3)
print("After deleting 3:", show(h))
print("Reversed:", show(reverse(h)))Key points
- A dummy node simplifies deleting the head
- Save next before changing pointers
- Reversal is O(n) time, O(1) space
- Draw the nodes before coding