Deletion From a Simple Linked List Using Python
Tags: beginners, programming, python, algorithms
Published: 2021-09-02 16:37:23

### 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.

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

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

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

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

```python
    # 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 found then point the previous node to the next node of the key. Otherwise print an error message.

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

---
## Step 4: Check sample test cases for the code.

![output](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nu8zbgiir5g591mtrvmt.png)

---

## The complete code is given below:

```python
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() 

```

---

## Thank you for reading the article. Please leave you feedback. :smile:
---

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