Prerequisites

To learn about singly linked lists, you should know:

1. Python 3
2. OOP concepts
3. Singly linked list - inserting a node and printing the nodes

What will we learn?

In the last tutorial, we discussed what singly linked lists are, how to add a node and how to print all the nodes. We strongly recommend you to read that first if you haven’t as we will be building off of those concepts.

This tutorial is about how to remove a node and how to know if a particular element exists in the linked list or not. Both these methods belong to the LinkedList class. Let us see these one by one.

How to find an element?

Like in most data structures, the only way to find if an element exists is by traversing the entire linked list. Note that if the linked list is sorted, we can use binary search. But here we are going to consider an unsorted linked list. The way this works is that the user will give us an element and we return True if we find the element else we return False. You can also use a counter and return the index of the element if it exists.

Algorithm

1. Set a pointer curr to the head
2. Compare curr.data to the input value:
   1. If equal, return True
   2. Else, move to the next pointer
3. Repeat steps 1-2 until the element is found or the end of the linked list is met

Code

def findNode(self,value):

       curr = self.head
       while curr:
           if curr.getData() == value:
               return True
           curr = curr.getNextNode()
       return False

How to remove nodes from singly linked lists?

Now that you know how to find a node, we can use this to remove a node. Again, there are several approaches to do this. You can remove the first node or you can remove the last node by maintaining a tail pointer that points to the last node of the linked list. The approach we are discussing here is that we get a value from the user, find the element in the linked list and remove it if it exists. It is very important to let the user know if the element was successfully removed. For this purpose, we return True for success and False otherwise. Remember to decrement the size attribute by 1.

Let us call the node to be deleted as the current node. The idea is to link the previous node’s next to point to the current node’s next node. For example, let us say we want to delete 4 from the given linked list:

Linked list: H-->3-->4-->5 

Remove 4: H-->3-->5 

We made the 3’s next node point to 4’s next node which is 5.

Let us say we want to delete 3

Remove 3: H-->5

We made the head pointer to point to 3’s next which is 5.

Note: To do make a connection between the previous node and the current node’s next node, it is important to keep track of the previous node.

Algorithm

1. Have two pointers:
   1. curr - Initially points to head
   2. prev - initially points to None

2. If inputted value matches the data of curr:
   1. Check prev exists:
      1. If yes, set next node of prev to next node of curr
      2. If no, simply point the head to next node of curr (this happens when you want to delete the first node)
      3. Decrement size by 1
      4. Return True
3. If inputted value doesn’t match the data of curr:
   1. Proceed to next node by:
      1. Pointing prev to curr
      2. Pointing curr to next node of curr
4. Repeat steps 1-3 till the end of the linked list
5. If the end of the linked list is reached, return False indicating no element in the linked list matches the inputted value

Code

def removeNode(self,value):

        prev = None
        curr = self.head
        while curr:
            if curr.getData() == value:
                if prev:
                    prev.setNextNode(curr.getNextNode())
                else:
                    self.head = curr.getNextNode()
                return True
                    
            prev = curr
            curr = curr.getNextNode()
            
        return False

Conclusion

That’s it for this tutorial. In the future tutorials, we will see how to reverse a singly linked list. Happy Pythoning!