In computer science, a linked list is a data structure wherein items are linked together by means of references or pointers rather than their physical positioning in memory. Each node in a linked list is composed of a data field and a link to the next node in the list. This article discusses the process of identifying and rectifying loops in linked lists, providing a valuable resource to data scientists who require an understanding of linked list and loop functionality.
The Loop Theorem and the Linked List
In a linked list with a loop, the final node will not refer to NULL, but rather to another node in the same list.
Turning the final node of a linked list into a NULL pointer eliminates the loop.
It is evident that the linked list comprises of four nodes, beginning at node 3 and concluding at nodes 3, 7, and 9. Furthermore, it is apparent that the final node acts as a redirector, leading us back to the root.
Now that we have identified the presence of a loop in the linked list, we must determine the best method for eliminating it. If the loop is removed, the structure of the list will be as follows: 1 → 3 → 5 → 7 → 9 → NULL.
A loop in a linked list may be broken up in numerous different ways. Please explain this to me in further depth.
Identifying a loop in a linked list and fixing it
Firstly, we may use Floyd’s cycle-finding technique
In order to efficiently troubleshoot, it is essential to verify that there are no loops in a linked list. One of the fastest methods for doing so is Floyd’s cycle-finding technique, which makes use of two pointers. The first pointer moves slowly through the list, while the other moves at a faster rate. This method has been nicknamed the ‘hare-tortoise algorithm’ due to its reference to the popular children’s fable The Tortoise and the Hare.
This is how Floyd’s cycle-finding method really works in practice:
Step 1: The initial position of both pointers (ptr1 and ptr2) is the root node.
Step 2: Both ptr1 and ptr2 begin their journey through the list by visiting the first node in turn, while ptr2 visits the second node in turn.
Step 3: Ptr2 will get to the end of the linked list before ptr1 does since it travels quicker.
There are two outcomes that might occur when the list is exhausted.
Since pointer2 (ptr2) advances two nodes at a time, it will point to null in the scenario where there is no loop in the linked list. This implies that, no matter how many nodes are present in the list, ptr2 will eventually reach the end of the list. It is important to note that ptr2 will always become null, regardless of whether the number of nodes in the list is even or odd.
In this scenario, we show the output of the function as ‘no loop’ and terminate execution when a null value is reached.
Loops in linked lists are the second type of occurrence that can be encountered. It is important to understand that pointers are not able to point to an empty address. Instead, they will traverse the loop and switch directions. Eventually, both pointers will meet at a single node along the list’s trajectory.
It has been observed that when the pointers detect a loop in the code, they start travelling at different speeds, which eventually leads to them colliding with one another. The consequence of this collision is that instead of a null value, ptr1 and ptr2 become equal. Due to this, the code ceases execution, and a message is displayed on the screen indicating that a loop is present.
It is clear that the two points will converge on a single node in the cyclic structure.
Having established that there is no cycle present in the linked list, it follows that the initial instance has come to an end. However, in the second example, we must now concentrate our attention on the second element of the problem, which will require us to break the cycle.
Fixing a circular connection in a list of items.
Let us ascertain the steps required to rectify the linked list, such that its final element points to NULL, thereby eliminating the loop that was detected. To assist, here is a comprehensive procedure that you can follow.
Step 1: Previously, it was elucidated that ptr1 and ptr2 would resolve to the same node within the loop. Consequently, as shown below, it is essential to pinpoint the last element of the loop and set it to point to NULL.
Step 2: Keep ptr2 as it is and change ptr1’s direction so it points to the beginning of the loop as seen in the highlighted portion of the code below.
Step 3: Our next step is to traverse the linked list by employing two pointers – ptr1 and ptr2 – simultaneously. Both pointers will move from node to node, one after the other, until they are pointing to the same node. Once this occurs, we will start the process again.
Step 4: It is essential that we terminate the never-ending cycle now by setting the value of pointer2 to null. It is important to take into consideration that the beginning of the loop is where the subsequent values of the two points will be equal.
It’s possible that you’re confused about why ptr1 and ptr2’s “next” converges on the loop’s first node. So why is that?
For illustration purposes, consider the following:
L = the total number of loop nodes N is the total amount of items in the list.
Therefor L = 5, and N = 12.
Initially, both pointers are set to the root node. Pointer 1 (ptr1) will advance N-L levels, which in this instance is 7 levels. To account for the fact that pointer 2 (ptr2) moves at twice the speed of ptr1, 2(N-L) steps should be added to the total number of steps taken by ptr2.
Consequently, the gap between the two pointers will be equal to (2N)(12-5L)/(N-L) = 2 nodes. This implies that ptr2 will traverse (N-L) nodes in the linked list’s full cycle.
The following steps should be taken to calculate the distance between two locations: Firstly, the arrows should be spread out by a distance of (N-L)%L+1. Then, distances should increase sequentially by (N-L)%L plus 2, (N-L)%L plus 3, and so forth. This will enable the distance between the two locations to be calculated using the formula (N-L)%L + X, in which ptr1 travels X nodes from the loop’s seed node.
It is absolutely necessary to immediately cease execution as soon as ptr1 and ptr2 reach the same node. Taking into account the fact that ptr2 goes around the loop once before meeting ptr1, the two pointers will eventually collide when their distance is equal to L.
When X = L – ((N-L)%l), the gap between them is L. According to the above, X equals 3.
Now, we move pointer 1 (ptr1) to the root node while keeping pointer 2 (ptr2) in its current position. Both pointers will advance sequentially, with each pointer traversing one node at a time. To get to the node in the first loop, ptr1 will traverse N-L nodes. Similarly, ptr2 will have to travel N-L nodes to get to the node of the original loop since it was two nodes away from the beginning point (i.e., (N-L)%L).
In essence, it is guaranteed that the two pointers, ptr1 and ptr2, will encounter each other at the initial node of the loop in the linked list. To eliminate the loop, we can backtrack until ptr2 points to the entry node of the loop and then set the node that ptr2 points to, to NULL.
A solution, written in the computer language C, is provided below.
First, the linked list loop is initialised in the code above. Floyd’s approach was used to break the loop and the results were printed.
Solution 2: Hashing
If the previous approach seems too difficult, this one should be a breeze. As we go through the list, more nodes will be added to the unordered map.
If we encounter a node that is already on the map, it means that we have arrived at the loop’s origin.
At every stage of the list’s traversal, we ensure that the head and tail pointers are in their designated positions. The node located at the head of the list is the active node, and the node located at the end of the list is the node immediately preceding the active node.
The head pointer of the loop is now pointing to the starting point, while the last pointer is indicating the node that preceded the node that the head pointer was indicating. To exit the loop, set the value of the next pointer of the last node to NULL.
By following this approach, instead of having the last node in the loop refer back to the first node, it will now refer to NULL. For those who wish to explore the solution further, downloadable implementations in C++, Java, and Python are available for download.
In order to eliminate loops from a linked list, we studied the use of additional pointers. We learnt how to identify a loop in a list, and discussed Floyd’s cycle-finding technique. Re-structuring the linked list involved the use of two pointers which moved at different rates to determine the node at which the loop began. Subsequently, we made the linked list linear by pointing the final node to NULL. Moreover, we examined hashing as an alternative approach to identifying the seed node of the loop and removing iterations from the list.
Linked lists are one of the most significant data structures employed in programming, providing a set of data that can be accessed by progressing through the nodes connected by pointers. Should any issues arise concerning the possibility of a loop existing within the linked list, the appropriate code can be used to detect and resolve the problem.