To learn about singly linked lists, you should know:<\/p>\n
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\u2019t as we will be building off of those concepts.<\/p>\n
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\u00a0LinkedList\u00a0<\/i>class. Let us see these one by one.<\/p>\nHow to find an element?<\/h3>\n
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\u00a0True\u00a0<\/i>if we find the element else we return\u00a0False<\/i>. You can also use a counter and return the index of the element if it exists.<\/p>\n Code<\/p>\n 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\u00a0tail\u00a0<\/i>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\u00a0True\u00a0<\/i>for success and\u00a0False\u00a0<\/i>otherwise. Remember to decrement the\u00a0size\u00a0<\/i>attribute by 1.<\/p>\n Let us call the node to be deleted as the current node. The idea is to link the previous node\u2019s next to point to the current node\u2019s next node. For example, let us say we want to delete 4 from the given linked list:<\/p>\n We made the 3\u2019s next node point to 4\u2019s next node which is 5.<\/p>\n Let us say we want to delete 3<\/p>\n We made the head pointer to point to 3\u2019s next which is 5.<\/p>\n Note:<\/strong>\u00a0To do make a connection between the previous node and the current node\u2019s next node, it is important to keep track of the previous node.<\/p>\nAlgorithm<\/h3>\n
\n
\n
def findNode(self,value):\r\n\r\n curr = self.head\r\n while curr:\r\n if curr.getData() == value:\r\n return True\r\n curr = curr.getNextNode()\r\n return False<\/pre>\n
How to remove nodes from singly linked lists?<\/h3>\n
Linked list: H-->3-->4-->5 \r\n\r\nRemove 4: H-->3-->5<\/pre>\n
Remove 3: H-->5<\/pre>\n
Algorithm<\/h3>\n
\n
\n
\n
\n
\n