DEV Community

Cover image for Deletion From a Simple Linked List Using Python
Abu Hurayra
Abu Hurayra

Posted on

Deletion From a Simple Linked List Using Python

Deleting a node from a linked list is straightforward but there are a few cases we need to account for:

  • 1. The list is empty
  • 2. The node to remove is the only node in the linked list
  • 3. We are removing the head node
  • 4. We are removing the tail node
  • 5. The node to remove is somewhere in between the head and tail node
  • 6. The item to remove does not exist in the linked list.

Step 1: If the list is empty then print a message and return.

def delete(self, key):
    # If the list is empty
    if self.head is None:
        print('Deletion Error: The list is empty.')
        return 
Enter fullscreen mode Exit fullscreen mode

Step 2: If the head holds the key, delete the head by assigning head to the next node of head.

    # If the key is in head
    if self.head.data == key:
        self.head = self.head.next
        return
Enter fullscreen mode Exit fullscreen mode

Step 3: Find the first occurrence of the key in the linked list.

    # Find position of first occurrence of the key
    current = self.head
    while current:
        if current.data == key:
            break
        previous = current
        current = current.next
Enter fullscreen mode Exit fullscreen mode

If the key was found then point the previous node to the next node of the key. Otherwise print an error message.

    # If the key was not found
    if current is None:
        print('Deletion Error: Key not found.') 
    else:
        previous.next = current.next
Enter fullscreen mode Exit fullscreen mode

Step 4: Check sample test cases for the code.

output


The complete code is given below:

class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        if not temp:
            print('List is empty.')
            return
        else:
            print('Start:', end=' ')
        while temp:
            print(temp.data, end=' -> ')
            temp = temp.next
        print('end.')

    def insert(self, data):
        new_node = Node(data)

        # If the linked list is empty
        if self.head is None:
            self.head = new_node

        # If the data is smaller than the head
        elif self.head.data >= new_node.data:
            new_node.next = self.head
            self.head = new_node

        else:
            # Locate the node before the insertion point
            current = self.head
            while current.next and new_node.data > current.next.data:
                current = current.next

            # Insertion
            new_node.next = current.next
            current.next = new_node

    def delete(self, key):
        # If the list is empty
        if self.head is None:
            print('Deletion Error: The list is empty.')
            return 

        # If the key is in head
        if self.head.data == key:
            self.head = self.head.next
            return

        # Find position of first occurrence of the key
        current = self.head
        while current:
            if current.data == key:
                break
            previous = current
            current = current.next

        # If the key was not found
        if current is None:
            print('Deletion Error: Key not found.') 
        else:
            previous.next = current.next



if __name__=='__main__':
    # Create an object
    LL = LinkedList()
    print('')

    # Insert some nodes
    LL.insert(10)
    LL.insert(12)
    LL.insert(8)
    LL.insert(11)
    LL.insert(10)


    LL.printList()
    LL.delete(7)
    LL.delete(8)
    LL.delete(13)
    LL.printList() 

Enter fullscreen mode Exit fullscreen mode

Thank you for reading the article. Please leave you feedback. 😄


References:

  1. https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
  2. CLRS: Introduction to Algorithms [book]

Discussion (0)