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"
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.
# Python code for deleting the first node in a singly linked list
def delete_first_node(self):
if self.head is None:
return
self.head = self.head.next
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.
# Python code for deleting a node in the middle of a singly linked list
def delete_middle_node(self, key):
if self.head is None:
return
temp = self.head
if temp.data == key:
self.head = temp.next
return
while temp:
if temp.data == key:
break
prev = temp
temp = temp.next
prev.next = temp.next
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.
# Python code for deleting the last node in a singly linked list
def delete_last_node(self):
if self.head is None:
return
temp = self.head
if temp.next is None:
self.head = None
return
while temp.next:
prev = temp
temp = temp.next
prev.next = None
Implementing Deletion in Singly Linked Lists in Python
")
current = current.next
print("None")
def delete_node(self, key):
current = self.head
# If the head node itself holds the key to be deleted
if current is not None and current.data == key:
self.head = current.next
return
# Search for the key to be deleted, keeping track of the previous node
prev = None
while current is not None and current.data != key:
prev = current
current = current.next
# If the key was not found in the list
if current is None:
print(f"{key} not found in the list.")
return
# Unlink the node with the key
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()
# Deleting a node with value 3
linked_list.delete_node(3)
print("Linked List after deleting 3:")
linked_list.display()
Analyzing Time Complexity in Deletion Operations
- When performing deletions in a singly linked list, the time complexity depends on the position and number of nodes to be deleted.
- Deleting a node takes O(1) time if we have a reference to the node to be deleted. However, searching for a node with a specific value takes O(n) time, where n is the number of nodes in the list.
The space complexity for deletion operations is O(1) as we do not use any additional data structures.
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
Can a singly linked list contain duplicate values?
Yes, a singly linked list can contain duplicate values. Each node in the list contains a data element, and multiple nodes can have the same data value.
Question 2.
What is the difference between a singly linked list and a doubly linked list?
In a singly linked list, each node has a reference to the next node, while in a doubly linked list, each node has references to both the next and previous nodes.
Question 3.
How do I insert an element at a specific position in a singly linked list?
To insert an element at a specific position, create a new node, traverse the list to the desired position, and update the references accordingly.
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