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"
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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 :
Deleting a node from a specific position in a Singly Linked List requires traversing the list to locate the node just before the target position and updating its next pointer to skip the target node. If the position is 0, the head is moved to the next node.
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
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def delete_at_position(self, position):
if not self.head:
print("List is empty")
return
if position == 0:
self.head = self.head.next
return
curr = self.head
for _ in range(position - 1):
if not curr.next:
print("Position out of range")
return
curr = curr.next
if not curr.next:
print("Position out of range")
return
curr.next = curr.next.next
def display(self):
curr = self.head
while curr:
print(curr.data, end=" -> ")
curr = curr.next
print("None")
# Example usage
sll = SinglyLinkedList()
for val in [10, 20, 30, 40, 50]:
sll.insert_at_end(val)
print("Before Deletion:")
sll.display()
sll.delete_at_position(2)
print("After Deletion at position 2:")
sll.display()
Output:
Before Deletion: 10 -> 20 -> 30 -> 40 -> 50 -> None After Deletion at position 2: 10 -> 20 -> 40 -> 50 -> None
Explanation:
- A SinglyLinkedList is created and populated with values [10, 20, 30, 40, 50].
- The method delete_at_position(2) is called to remove the node at index 2 (which holds value 30).
- The list is traversed to the node just before the target (index 1 with value 20).
- The next pointer of this node is updated to skip the node at index 2, effectively deleting it.
- If the position is invalid (out of range), a message is printed.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion at End | O(n) | O(1) |
| Deletion at Position | O(n) | O(1) |
| Display | O(n) | O(1) |
Advantages of Using Singly Linked Lists in Python
To wrap it up:
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
FAQs
To delete a node at a given position, traverse the list to the node just before that position and adjust the next pointer to skip the target node. Edge cases like deleting at position 0 (head) should be handled separately.
If the position exceeds the list length, the function should return an error or do nothing to prevent null pointer access. It’s important to validate the position before deletion.
Yes, by checking if the position is 0, you can update the head to point to the next node, effectively removing the original head. This is a common edge case in position-based deletion.
The time complexity is O(n) because we need to traverse up to the specified position. Space complexity remains O(1) since we’re not using extra space.
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