TheLazy.Dev
Portfolio GitHub

Blog

beginners |programming |python |algorithms

Deletion From a Simple Linked List Using Python

hurayraiit

Abu Hurayra

Posted on September 2, 2021

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]
💖 💪 🙅 🚩
hurayraiit
Abu Hurayra

Posted on September 2, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Billboard Artist Recommendation Software
beginners Billboard Artist Recommendation Software

June 20, 2022

Deletion From a Simple Linked List Using Python
beginners Deletion From a Simple Linked List Using Python

September 2, 2021