Data Structures and Algorithms in Python/

...

/

Delete Node

Delete Node

In this lesson, you will learn how to remove a node from a doubly linked list.

We'll cover the following...

In this lesson, we consider how to delete, or, remove nodes from a doubly linked list. Once we cover the concept of how to perform this action, we follow through with a Python implementation.

We will analyze the entire implementation step by step in four parts. The following are the different cases that we can encounter while deleting a node from a doubly linked list.

Case 1: Deleting the only node present

Case 1 is where we want to delete the only node present in the linked list. As it is the single node in the linked list, then it is the head node as well. The prev and next pointer of such a node point to None which makes it a special case. Let’s look at the implementation for this case below.

Implementation

Press + to interact
def delete(self, key):
        cur = self.head
        while cur:
            if cur.data == key and cur == self.head:
                # Case 1:
                if not cur.next:
                    cur = None 
                    self.head = None
                    return
            cur = cur.next

Explanation

The method takes in key which is the key of the node to be deleted. On line 2, we set cur to self.head and proceed to the while loop on line 3 which will run until cur is None. The execution will jump to line 6 if the conditions on line 4 evaluate to True i.e., cur.data is equal to key and the current node is also the head node. Now at this point, we ...