How to remove a loop in a linked list
Loop in a linked list
A linked list is a commonly used data structure made up of nodes that are interlinked using pointers.
Note: Read more on a linked list here.
A linked list may contain a loop if a node points to another node that comes earlier in the chain. If this happens, a never-ending loop is created in the linked list.
Note: If you want to learn more about detecting a loop in a linked list, visit this link.
Removing a loop
If we find a loop, we can remove it by pointing the pointer next to where the loop occurs to null. For example, the linked list above will become as follows:
Algorithm
The above method can be implemented by first going through the linked list and finding where the loop is and then removing that loop. We can follow the following steps to do this:
Find the loop using a map in Java/C++ or a dictionary in Python. We can go through the linked list and add the addresses of the nodes in the dictionary. Now, if at any node, the next node's address is already in the dictionary, the loop is at that node.
After we find the loop, we can simply point the next pointer of that node to
nullto remove the loop.
Code
class LinkedList:def __init__(self):self.root = Nonedef removeLoop(self):visited_nodes = dict()curr = self.rootvisited_nodes[curr] = Truewhile curr.after:try:if visited_nodes[curr.after]:curr.after = Nonereturn Trueexcept:visited_nodes[curr.after] = Truecurr = curr.afterreturn FalseLinkedList.detectLoop = detectLoop # add the detect loop functionmy_list = LinkedList()my_list.root = Node(3)my_list.root.after = Node(9)my_list.root.after.after = Node(13)my_list.root.after.after.after = Node(12)my_list.root.after.after.after.after = Node(8)my_list.root.after.after.after.after.after = Node(15)my_list.root.after.after.after.after.after.after = my_list.root.after.afterprint("The list", "has" if my_list.detectLoop() else "does not have", "a loop")print("\nCalling removeLoop() to remove the loop...")my_list.removeLoop()print("\nNow we check if the list still has a loop:")print("The list", "has" if my_list.detectLoop() else "does not have", "a loop")
Explanation
Lines 6–8: We create a dictionary that stores the address of nodes we have already visited and sets the value to
True.Lines 9–17: The
whileloop iterates through the linked list. If a loop is found, it removes it (by pointing it toNone) and returnsTrue.Lines 10–13: The
tryblock checks if a node already exists in thevisited_nodesand removes the loop if it finds one.Lines 14–16: The
catchblock adds a node to the dictionary and updates the value ofcurrto move through the list.Lines 21–34: We create a linked list
my_list. The functiondetectLoop()is used to find if the list has a cycle. The functionremoveLoop()is called to remove the loop from the list.
Free Resources
