# 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