Deleting a node from a linked list involves removing an element from various positions within the list. This process modifies the list structure by adjusting node references to maintain the integrity of the linked list.
For all the scenarios discussed in this article, linked list node is represented with the below structure:
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
And this is how the linked list is created before the deletion operation:
# Create the nodes first before linking them
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4
# Store references to Head node and Tail node
head = node1
tail = node4
Note: If the language you are using does not have garbage collection (C/C++ for example), the memory used by node which is removed from the linked list has to be deallocated manually. In order to keep this article simple, the memory deallocation part is skipped.
Deletion at the Beginning
Deleting a node from the beginning of a linked list involves updating the head to point to it’s next node. Here’s the code snippet:
if head is not None:
head = head.next # Update head to the next node
# If the list had only one node, update tail to None
if head is None:
tail = None
If there’s only one node in the list, we reset the tail to indicate that there is no tail node after deletion.
Deletion at the End
Unlike the scenario with insertion of a new node at the end of linked list, deletion of the last element requires traversing till last but one element and then deleting the node after it. Here’s the code snipped for deleting last node in a linked list:
current = head
prev = None
# Traverse linked list until node before the last/tail node
while current and current.next:
prev = current
current = current.next
if prev is not None:
# Remove the last node
prev.next = None
# Update tail to the new last node
tail = prev
else:
# If there was only one node,
# update both head and tail to None
head = None
tail = None
The first while loop traverses the linked list until current pointer reaches the end of linked list. prev will point to the node before the tail node. If prev is None, it means that there is only one node in the linked list and the else condition handles it by setting both head and tail of the linked list to None.
Deletion after a Specific Node
Let’s say there are three nodes A->B->C in a linked list in that sequence. And we need to delete the next node after node A. In order to achieve this, we need to retrive the node pointed by node to be deleted (B), which is C, and then updateA node’s to point to C. Here’s a code snippet which does that:
# For example, let's try deleting node after node2
prev_node = node2
if prev_node is not None and prev_node.next is not None:
node_to_delete = prev_node.next # Node to be deleted
prev_node.next = node_to_delete.next # Update pointers to skip the node to delete
if node_to_delete == tail:
# Update tail if the deleted node was the last
tail = prev_node
For the example discussed, prev_node variable will point to node A, node_to_delete will point to node B. Before deletion, prev_node.next will point to node B. But after the statement prev_node.next = node_to_delete.next, node C is set as the next node to node A and so the linked list finally becomes A->C.
Deletion at a Specific Position
Deleting a node at a specific position involves traversing the list to the (position-1)th node and then performing deletion similar to what we did for deleting a specific node in the linked list. Here’s the code snippet:
# Deletion position (position starts from 0)
position = 1
if position == 0:
# Same case as deleting node at the beginning
if head is not None:
# Update head to the next node
head = head.next
# If the list had only one node, update tail to None
if head is None:
tail = None
elif position > 0:
count = 0
current = head
prev = None
# Traverse through linked list until at position-1
while current and count < position:
prev = current
current = current.next
count += 1
# current node is the node to delete
if current is not None:
prev.next = current.next # Skip over the node to be deleted
if current == tail:
tail = prev # Update tail if the node to delete is the last