Deletion in a Singly Linked List for a Position in Python
Deletion in Singly Linked List for a Position in Python
In the world of data structures and algorithms, linked lists are fundamental structures that are widely used for various operations. A singly linked list is one of the simplest types of linked lists, where each element in the list points to the next element.
In this page, we will discuss about deletion in singly linked list at a specific position in python. This operation is essential for maintaining the integrity and functionality of linked lists in various programming scenarios.
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.
Why Use Singly Linked Lists?
Singly linked lists are preferred in many situations due to their simplicity and efficiency in memory usage. They are especially useful when the size of the list is unknown or when elements need to be inserted or removed frequently.
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"
Deleting Nodes at a Specific Position in Python
Identifying the Node to Delete :
- To delete a node in a singly linked list at a specific position, you must first identify the node to be removed. This position is usually represented by an index or position number, starting from 1 for the head node.
The Deletion Process
Step 1: Traverse the List :
- Start at the head of the linked list and traverse it while keeping track of the current node and the previous node. Move through the list until you reach the desired position.
Step 2: Update Pointers :
- Once you reach the target position, update the next pointer of the previous node to skip the node you want to delete. This effectively removes the node from the list.
Pseudocode for Deletion in Singly List for a Position in Python :
function deleteNodeAtPosition(head, position):
if position == 1:
head = head.next
else:
current = head
for i in range(position - 2):
current = current.next
current.next = current.next.next
return head
Implementing Deletion in Singly Linked Lists for a Position in Python :
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 delete_at_position(self, position):
if position < 1:
print("Position should be a positive integer.")
return
if position == 1:
if self.head:
self.head = self.head.next
else:
print("List is empty.")
return
current = self.head
prev = None
count = 1
while current and count < position: prev = current current = current.next count += 1 if not current: print("Position exceeds the length of the list.") return prev.next = current.next def display(self): current = self.head while current: print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
if __name__ == "__main__":
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()
position_to_delete = 2
linked_list.delete_at_position(position_to_delete)
print(f"Linked List after deleting node at position {position_to_delete}:")
linked_list.display()
Output
Original Linked List: 1 -> 2 -> 3 -> 4 -> None Linked List after deleting node at position 2: 1 -> 3 -> 4 -> None
Analyzing Time Complexity in Deletion Operations
The time complexity of the provided code for deleting a node in a singly linked list at a specific position is O(n), where “n” is the position of the node to be deleted.
In the worst case, when the position to delete is the last node (position “n”), the code will traverse the entire linked list until it reaches the target position. This involves visiting “n-1” nodes.
When the position is not the last node (position “k” where k < n), the code still traverses “k-1” nodes to reach the target position.
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 for a Position 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 we delete the head node of a singly linked list?
Yes, you can delete the head node by updating the head pointer to point to the next node in the list. Remember to handle memory deallocation if necessary.
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.
What is the time complexity of deleting a node in a singly linked list at a specific position?
The time complexity is O(n), where n is the position of the node to be deleted. In the worst case, you may need to traverse the entire list.
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