Deletion in Singly Linked List in Python
Deletion in Singly Linked List in Python
In the world of programming, data structures play a crucial role in organizing and managing data efficiently. One such data structure is the singly linked list, which is widely used for its simplicity and versatility.
In this page, we will discuss the process of deletion in singly linked list in Python.
Understanding Singly Linked Lists
A singly linked list is a linear data structure composed of nodes. Each node contains data and a reference (or link) to the next node in the sequence. The first node is known as the head, and the last node typically points to null, indicating the end of the list.
Elements of a Singly Linked List
- Node: The fundamental building block of a linked list. Each node contains a data element and a reference to the next node (or None if it’s the last node).
- Head: The first node in the linked list, which serves as the starting point for traversing the list.
- Tail: The last node in the linked list, which has a reference to None, indicating the end of the list.
How to Remove Nodes in a Singly Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def remove_node(self, key):
current = self.head
# Handle the case where the node to remove is the head
if current is not None and current.data == key:
self.head = current.next
current = None
return
prev = None
while current is not None:
if current.data == key:
break
prev = current
current = current.next
# If the key was not found in the list
if current is None:
return
# Unlink the node from the linked list
prev.next = current.next
current = None
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
linked_list = LinkedList()
linked_list.head = Node(1)
second_node = Node(2)
third_node = Node(3)
linked_list.head.next = second_node
second_node.next = third_node
linked_list.print_list() # Output: 1 -> 2 -> 3 -> None
linked_list.remove_node(2)
linked_list.print_list() # Output: 1 -> 3 -> None
Algorithm for Deletion in Singly Linked List:
function deleteNode(list, target):
if list.head is null:
return "List is empty"
// Initialize pointers
current = list.head
prev = null
// Traverse the list to find the target node
while current is not null and current.data is not equal to target:
prev = current
current = current.next
// Check if the target node was found
if current is null:
return "Node not found"
// Update pointers to skip the target node
if prev is null:
// If the target node is the head node
list.head = current.next
else:
// If the target node is an interior or tail node
prev.next = current.next
// Free memory (if applicable)
return "Node deleted successfully"
Implementing Deletion in Singly Linked Lists in Python
Implementing deletion in Singly Linked Lists in Python involves locating the node to be removed and updating the previous node’s pointer to skip over it. This can be done at the beginning, middle, or end of the list, each with its own pointer adjustment logic. Proper handling of edge cases like empty lists or non-existent values is crucial for robust implementation.
Run
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def delete_node(self, key):
current = self.head
# If head node holds the key to be deleted
if current is not None and current.data == key:
self.head = current.next
return
# Search for the key while keeping track of the previous node
prev = None
while current is not None and current.data != key:
prev = current
current = current.next
# Key not found
if current is None:
print(f"{key} not found in the list.")
return
# Remove the node
prev.next = current.next
# Example usage:
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print("Original Linked List:")
linked_list.display()
# Delete node with value 3
linked_list.delete_node(3)
print("Linked List after deleting 3:")
linked_list.display()
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> None Linked List after deleting 3: 1 -> 2 -> 4 -> None
Explanation:
- Each node has data and a next pointer.
- append() adds a new node at the end (O(n)).
- display() prints all nodes (O(n)).
- delete_node(key):
- If key is in head → shift head.
- Else → search and unlink the node.
- If not found → print message.
- Handles deletion from beginning, middle, or not-found cases.
Time & Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| append() | O(n) | O(1) |
| display() | O(n) | O(1) |
| delete_node() | O(n) | O(1) |
| Initialization | O(1) | O(1) |
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Deletion in Singly Linked Lists
- Deletion at Beginning
- Deletion at Middle
- Deletion at End
Deletion at Beginning in Singly Linked List in Python
Deleting the first node in a singly linked list is a relatively straightforward operation. We need to update the head of the list to point to the second node, effectively bypassing the first node, which will eventually be garbage collected by Python’s memory management system.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
def delete_at_beginning(self):
if self.head is None:
print("List is empty. No node to delete.")
else:
print(f"Deleted node: {self.head.data}")
self.head = self.head.next
def display(self):
temp = self.head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")
# Example usage
sll = SinglyLinkedList()
sll.insert_at_end(8)
sll.insert_at_end(23)
sll.insert_at_end(34)
sll.insert_at_end(45)
print("Original List:")
sll.display()
sll.delete_at_beginning()
print("After Deletion at Beginning:")
sll.display()
Output:
Original List: 8 -> 23 -> 34 -> 45 -> None Deleted node: 8 After Deletion at Beginning: 23 -> 34 -> 45 -> None
Explanation:
A Singly Linked List is created and nodes 8, 23, 34, and 45 are inserted at the end.
To delete the first node (8):
We simply move the head pointer to the next node (23).
The original head node (8) becomes inaccessible and is automatically deleted by Python’s garbage collector.
If the list is empty, a message is displayed: “List is empty. No node to delete.”
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Deletion at Beginning | O(1) | O(1) |
Deletion at Middle in Singly Linked List in Python
When it comes to deleting a node from the middle of the list, we need to ensure that we maintain the integrity of the list’s structure. ‘
We update the reference of the previous node to point to the node after the one being deleted.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
def delete_in_middle(self, key):
if self.head is None:
print("List is empty.")
return
if self.head.data == key:
self.head = self.head.next
return
prev = None
current = self.head
while current and current.data != key:
prev = current
current = current.next
if current is None:
print(f"Node with data {key} not found.")
else:
print(f"Deleted node: {current.data}")
prev.next = current.next
def display(self):
temp = self.head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")
# Example usage
sll = SinglyLinkedList()
sll.insert_at_end(8)
sll.insert_at_end(23)
sll.insert_at_end(34)
print("Original List:")
sll.display()
sll.delete_in_middle(23)
print("After Deletion in Middle:")
sll.display()
Explanation:
- We first check if the list is empty.
- If the head node matches the target, it is deleted as a special case.
- Otherwise, we traverse the list and keep track of the previous node.
- Once the target node is found, we skip it by changing prev.next to current.next.
- If the node is not found, we print a message.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Deletion in Middle | O(n) | O(1) |
Deletion at End in Singly Linked List in Python
Deleting the last node is a bit more challenging because we need to traverse the entire list to find the second-to-last node and update its reference to None.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
def delete_at_end(self):
if self.head is None:
print("List is empty.")
return
if self.head.next is None:
print(f"Deleted node: {self.head.data}")
self.head = None
return
prev = None
current = self.head
while current.next:
prev = current
current = current.next
print(f"Deleted node: {current.data}")
prev.next = None
def display(self):
temp = self.head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")
# Example usage
sll = SinglyLinkedList()
sll.insert_at_end(8)
sll.insert_at_end(23)
sll.insert_at_end(34)
print("Original List:")
sll.display()
sll.delete_at_end()
print("After Deletion at End:")
sll.display()
Output:
Original List: 8 -> 23 -> 34 -> None Deleted node: 34 After Deletion at End: 8 -> 23 -> None
Explanation:
- We insert 8, 23, and 34 into the singly linked list.
- On deletion:
- If list is empty → print message.
- If only one node → delete by setting head to None.
- Otherwise → traverse to second-last node and set its next to None.
- So 34 is removed from the list.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Deletion at End | O(n) | O(1) |
Advantages of Using Singly Linked Lists in Python
- Dynamic Size: Singly Linked Lists can dynamically adjust their size, allowing for efficient memory allocation as elements are added or removed. This flexibility makes them suitable for situations where the size of the data structure may change frequently.
- Efficient Insertion and Deletion: Inserting or deleting an element at the beginning of a Singly Linked List is a constant-time operation (O(1)), making it efficient for scenarios that require frequent data updates. Other operations, such as insertion and deletion in the middle, are also relatively efficient when the position of the element is known.
- Low Memory Overhead: Singly Linked Lists have lower memory overhead compared to some other data structures like arrays or doubly linked lists. Each element only needs to store a reference to the next element, which saves memory.
- Dynamic Memory Allocation: Singly Linked Lists allocate memory for each element individually, reducing the risk of memory wastage. This feature is particularly valuable in environments with limited memory resources.
Conclusion
In this page, we explored the topic of deletion in singly linked lists in Python. We covered various scenarios, from deleting the first node to handling edge cases and discussed the time and space complexities associated with these operations. By understanding the fundamentals of linked list operations
FAQs
To delete the first node, simply move the head pointer to the next node. The original head node becomes inaccessible and is cleaned up by Python’s garbage collector.
Traverse the list to find the node with the given value, keep track of the previous node, and update its next pointer to skip the target node. If the node is not found, no deletion occurs.
If the list is empty (i.e., head is None), deletion cannot occur and a message like “List is empty” should be displayed or returned.
Traverse the list until the second-last node and set its next pointer to None. This removes the reference to the last node, which is then automatically deleted.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment