educative.io

Educative

Doubly Linked List Delete Python Data Structures

def delete(lst, value):
deleted = False
if lst.is_empty():
    print("List is Empty")
    return deleted

current_node = lst.get_head()

if current_node.data is value:
    # Point head to the next element of the first element
    lst.head_node = current_node.next_element
    # Point the next element of the first element to Nobe
    current_node.next_element.previous_element = None
    deleted = True  # Both links have been changed.
    print(str(current_node.data) + " Deleted!")
    return deleted

# Traversing/Searching for node to Delete
while current_node:
    if value is current_node.data:
        if current_node.next_element:
            # Link the next node and the previous node to each other
            prev_node = current_node.previous_element
            next_node = current_node.next_element
            prev_node.next_element = next_node
            next_node.previous_element = prev_node
            # previous node pointer was maintained in Singly Linked List

        else:
            current_node.previous_element.next_element = None
        deleted = True
        break
    # previousNode = tempNode was used in Singly Linked List
    current_node = current_node.next_element

if deleted is False:
    print(str(value) + " is not in the List!")
else:
    print(str(value) + " Deleted!")
return deleted

This is what the solution that is provided in the course for deleting the node from a doubly linked list. I think this solution will not work if there is only one node in the list. Before we access the next element, we should always check if the next element is not None. And then only assign the value of previous’ next_element to current. next_element as done in line 17. Same is the case if we happen to delete last element in the list. Below code is shorter and should work for all the cases.

def delete(lst, value):
if lst.is_empty():
    print("List is empty")
    return False
current_node= lst.get_head()
if current_node.data== value:
    lst.head_node= current_node.next_element
    if current_node.next_element:
        current_node.next_element.previous_element= None 
    current_node.next_element= None
    return True
while current_node.next_element:
    current_node= current_node.next_element
    if current_node.data== value:
        current_node.previous_element.next_element= current_node.next_element
        if current_node.next_element:
            current_node.next_element.previous_element= current_node.previous_element
        current_node.previous_element= None
        current_node.next_element= None
        return True
return False