DSA Inserting and Deleting in a Linked List
Inserting and deleting in a linked list means rewiring next links around one node. A dummy head is a spare node placed before the head so every edit follows the same steps.
Insert at the head
The new node's next takes the old head. The new node then becomes the head.
class Node:
def __init__(self, value):
self.value = value
self.next = None
def build(values):
head = None
tail = None
for value in values:
node = Node(value)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def render(head):
parts = []
node = head
while node is not None:
parts.append(str(node.value))
node = node.next
parts.append("None")
return " -> ".join(parts)
head = build([2, 3])
fresh = Node(1)
fresh.next = head
head = fresh
print(render(head))Insert in the middle
The fresh node first takes the old next link. Then the node before it points at the fresh node.
class Node:
def __init__(self, value):
self.value = value
self.next = None
def build(values):
head = None
tail = None
for value in values:
node = Node(value)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def render(head):
parts = []
node = head
while node is not None:
parts.append(str(node.value))
node = node.next
parts.append("None")
return " -> ".join(parts)
head = build([1, 3])
node = head
fresh = Node(2)
fresh.next = node.next
node.next = fresh
print(render(head))Delete with a dummy head
The dummy stands before the head. Deleting the head then rewires the dummy, like any other deletion.
class Node:
def __init__(self, value):
self.value = value
self.next = None
def build(values):
head = None
tail = None
for value in values:
node = Node(value)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def render(head):
parts = []
node = head
while node is not None:
parts.append(str(node.value))
node = node.next
parts.append("None")
return " -> ".join(parts)
def delete_value(head, value):
dummy = Node(0)
dummy.next = head
node = dummy
while node.next is not None:
if node.next.value == value:
node.next = node.next.next
break
node = node.next
return dummy.next
head = build([1, 2, 3])
head = delete_value(head, 1)
print(render(head))Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
def build(values):
head = None
tail = None
for value in values:
node = Node(value)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def render(head):
parts = []
node = head
while node is not None:
parts.append(str(node.value))
node = node.next
parts.append("None")
return " -> ".join(parts)
def insert_head(head, value):
node = Node(value)
node.next = head
return node
def append(head, value):
node = Node(value)
if head is None:
return node
tail = head
while tail.next is not None:
tail = tail.next
tail.next = node
return head
def insert_after(head, target, value):
node = head
while node is not None and node.value != target:
node = node.next
if node is not None:
fresh = Node(value)
fresh.next = node.next
node.next = fresh
return head
def delete_value(head, value):
dummy = Node(0)
dummy.next = head
node = dummy
while node.next is not None:
if node.next.value == value:
node.next = node.next.next
break
node = node.next
return dummy.next
head = build([10, 20, 30])
print("start:", render(head))
head = insert_head(head, 5)
print("insert 5 at head:", render(head))
head = append(head, 40)
print("append 40:", render(head))
head = insert_after(head, 20, 25)
print("insert 25 after 20:", render(head))
head = delete_value(head, 5)
print("delete 5:", render(head))
head = delete_value(head, 25)
print("delete 25:", render(head))
head = delete_value(head, 40)
print("delete 40:", render(head))Key points
- Inserting rewires two links, the new node's next and its predecessor's next
- Deleting skips a node by pointing its predecessor past it
- Dummy head: a spare node before the head that is removed before returning
- The dummy head removes the special case of editing the first node
- Edits rewire links around a node instead of moving the other values
In this example, six edits run on one small list and the list prints after each edit. The first insert puts 5 before the old head. The append walks to the tail and links 40 after it. The middle insert places 25 after 20 by rewiring two links. The three deletions then remove the head, a middle node and the tail. The dummy head lets all three use the same code.
Note
The skipped node is not erased by hand, since Python reclaims memory that nothing points to.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Why does delete_value place a dummy head before the real head?