- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- Prime Video
- OffCampus Updates
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# Deletion in Doubly Linked List in Python

## Deletion in Doubly Linked List in Python

Doubly linked lists are a fundamental data structure in computer science and are often used in various applications to efficiently manage and manipulate data.

In this page, we will explore how to perform deletion in doubly linked list using Python. We will cover different scenarios and techniques for deleting elements at various positions within the list

## Understanding Deletion in Doubly Linked Lists in Python

A Doubly Linked List is a data structure that consists of a set of nodes, where each node contains both data and two pointers: one pointing to the next node and another pointing to the previous node. This bidirectional linking enables efficient traversal in both directions.

Deletion in Doubly linked list in Python involves removing a specific node from the list. Doubly linked lists consist of nodes, where each node contains two parts: data and a reference (or a pointer) to the next node in the list. To delete a node from a linked list, you typically need to update the references to ensure that the deleted node is no longer part of the list.

### Elements of Doubly Linked List

**Data :**This is the actual information or value that the node holds. It can be of any data type, depending on the application’s requirements. For example, in a list of student records, the data may include the student’s name, ID, and grade.**Next Pointer :**The “next” pointer, also known as the “forward” or “next node” pointer, points to the next node in the list. It helps in navigating from the current node to the next node when traversing the list in the forward direction.**Previous Pointer :**The “previous” pointer, also known as the “backward” or “previous node” pointer, points to the previous node in the list. It facilitates traversal in the reverse direction, allowing you to move from the current node to the previous node.

### Deleting Nodes in Python Doubly Linked Lists

Deleting a node from a doubly linked list involves a few essential steps.

**Step 1: Locate the Node to Delete**

- Before deleting a node, we must find the node we want to remove. This typically involves traversing the list using a loop until we find the node with the desired data value.

**Step 2: Update Pointers**

- Once we’ve located the node to delete, we need to update the pointers of the adjacent nodes to bypass the node we’re deleting. This includes changing the ‘next’ pointer of the previous node to point to the next node and the ‘previous’ pointer of the next node to point to the previous node.

**Step 3: Delete the Node**

- After updating the pointers, we can safely delete the node from memory. In Python, memory management is typically automatic through garbage collection.

### Deletion in Doubly Linked-list in Python

For each deletion operation, we need to consider the three cases.

- Deletion at the beginning
- Deletion at Middle
- Deletion at End

### Deletion at Beginning in Doubly Linked List in Python

#### Algorithm

- Check if there is only 1 node or not
- If there is one node
- Assign head to NULL
- Free memory

- Else
- Assign head to next node in the list
- Assign head->prev to NULL
- Free memory

### Function for deletion at beginning in doubly linked list

def delete_front(head): # Check if the linked list is empty if head is None: print("Linked List Empty, nothing to delete") return # Check if Linked List has only 1 node if head.next is None: print(f"{head.data} deleted") head = None return # Move head to the next node head = head.next # Assign the new head node's previous to None head.prev = None print(f"{tempNode.data} deleted") del tempNode

### Deletion at Middle in Doubly Linked List in Python

#### Algorithm

- Traverse till the target node
- create a node called the previous storing previous node of the target node
- Assign previous node’s next pointer to the next node of the target node
- For the next node of the target node, its previous pointer is assigned to the targets node’s previous node’s address
- Free memory of target node

### Function for deletion at Middle in doubly linked list

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None def delete_nth_node(self, n): if self.head is None: print("Linked List Empty, nothing to delete") return len = self.get_length() if n < 1 or n > len: print("Enter valid position") return if n == 1: self.delete_front() return if n == len: self.delete_end() return temp_node = self.head # Traverse to the nth node for i in range(n - 1): temp_node = temp_node.next previous_node = temp_node.prev # (n-1)th node next_node = temp_node.next # (n+1)th node # Assigning (n-1)th node's next pointer to (n+1)th node previous_node.next = next_node # Assigning (n+1)th node's previous pointer to (n-1)th node next_node.prev = previous_node # Deleting nth node print(f"{temp_node.data} deleted") del temp_node def get_length(self): length = 0 temp_node = self.head while temp_node: length += 1 temp_node = temp_node.next return length def delete_front(self): if self.head is None: print("Linked List Empty, nothing to delete") return if self.head.next is None: print(f"{self.head.data} deleted") self.head = None return self.head = self.head.next self.head.prev = None def delete_end(self): if self.head is None: print("Linked List Empty, nothing to delete") return if self.head.next is None: print(f"{self.head.data} deleted") self.head = None return temp_node = self.head while temp_node.next: temp_node = temp_node.next prev_node = temp_node.prev prev_node.next = None print(f"{temp_node.data} deleted") del temp_node

### Deletion at End in Doubly Linked List in Python

- Traverse till the target node
- Check if this is the last node i.e. if node->next = NULL, then its last node
- Assign last node’s previous node’s next pointer to the last node’s next node’s address, which basically is NULL in this case
- Free the memory

### Function for deletion at End in doubly linked list

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None def delete_end(self): if self.head is None: print("Linked List Empty, nothing to delete") return temp_node = self.head if temp_node.next is None: print(f"{temp_node.data} deleted") self.head = None return # Traverse to the last node while temp_node.next is not None: temp_node = temp_node.next second_last = temp_node.prev # Assign 2nd last node's next to None second_last.next = None print(f"{temp_node.data} deleted") del temp_node # Usage example: # Create a doubly linked list dll = DoublyLinkedList() # Insert some nodes (you can add more if needed) node1 = Node(1) node2 = Node(2) node3 = Node(3) dll.head = node1 node1.next = node2 node2.prev = node1 node2.next = node3 node3.prev = node2 # Delete the last node dll.delete_end()

### Python Code for Deletion in a Doubly Linked List

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None def get_length(node): length = 0 while node: node = node.next length += 1 return length def insert(head, data): fresh_node = Node(data) fresh_node.next = head if head: head.prev = fresh_node head = fresh_node return head def delete_front(head): if not head: print("Linked List Empty, nothing to delete") return None if not head.next: print(f"{head.data} deleted") head = None return None head = head.next head.prev = None print(f"{head.data} deleted") return head def delete_end(head): if not head: print("Linked List Empty, nothing to delete") return None if not head.next: print(f"{head.data} deleted") head = None return None temp_node = head while temp_node.next: temp_node = temp_node.next second_last = temp_node.prev second_last.next = None print(f"{temp_node.data} deleted") return head def delete_nth_node(head, n): length = get_length(head) if n < 1 or n > length: print("Enter valid position") return head if n == 1: return delete_front(head) if n == length: return delete_end(head) temp_node = head while n > 1: temp_node = temp_node.next n -= 1 previous_node = temp_node.prev next_node = temp_node.next previous_node.next = next_node next_node.prev = previous_node print(f"{temp_node.data} deleted") return head def display(head): end = None print("List in Forward direction:", end=" ") while head: print(head.data, end=" ") end = head head = head.next print("\nList in backward direction:", end=" ") while end: print(end.data, end=" ") end = end.prev print("\n") if __name__ == "__main__": head = None head = insert(head, 7) head = insert(head, 8) head = insert(head, 9) head = insert(head, 10) head = insert(head, 11) head = insert(head, 12) display(head) head = delete_front(head) display(head) head = delete_end(head) display(head) head = delete_nth_node(head, 3) display(head) head = delete_nth_node(head, 1) display(head) head = delete_end(head) display(head)

#### Output

List in Forward direction: 12 11 10 9 8 7 List in backward direction: 7 8 9 10 11 12 12 deleted List in Forward direction: 11 10 9 8 7 List in backward direction: 7 8 9 10 11 7 deleted List in Forward direction: 11 10 9 8 List in backward direction: 8 9 10 11 9 deleted List in Forward direction: 11 10 8 List in backward direction: 8 10 11 11 deleted List in Forward direction: 10 8 List in backward direction: 8 10 8 deleted List in Forward direction: 10 List in backward direction: 10

**Time and Space Complexity**

The time complexity of deletion in a Doubly Linked List is O(N), where N is the number of nodes. This is because, in the worst case, you may need to traverse the entire list to find the node to be deleted.

The space complexity is O(1), as no additional data structures are used for the deletion itself.

**Conclusion**

In this page, Deletion in Doubly Linked List in Python, we have discussed about the understanding the different scenarios for deletion and implementing them correctly is crucial for efficient data manipulation. Doubly linked lists provide an excellent foundation for various data-related tasks.

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

**Question 1**.

**What’s the process for deleting the tail node in a doubly linked list?**

To delete the tail node, you update the previous pointer of the current tail and make the previous node the new tail.

**Question 2**.

**Can you delete a node in the middle of a doubly linked list?**

Yes, you can delete a node in the middle by updating the next and previous pointers of the adjacent nodes to bridge the gap.

**Question 3**.

**How do I delete a node from a doubly linked list?**

To delete a node, you can update the previous node’s **‘****next’** pointer to skip the node you want to delete and update the next node’s **‘****prev’** pointer 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