Linked lists are a type of data structure in computer science, where each item is connected through pointers or references instead of their physical memory placement. These lists are composed of nodes, which hold data fields and links to the subsequent nodes. This article delves into loop identification and correction within linked lists, offering a useful reference point for data scientists seeking to gain insight into how loops and linked lists work.
The Linked List and the Loop Theorem
A linked list containing a loop will have its last node pointing not to NULL, but to another node within the same list.
By transforming the last node of a linked list into a NULL pointer, the loop present in the list can be eliminated.
The linked list is comprised of four nodes, starting at node 3 and ending at nodes 3, 7, and 9. It is clear that the last node functions as a redirect, taking us back to the beginning of the list.
Having spotted the loop within the linked list, we must now identify the most effective way to remove it. By doing so, the structure of the list will be transformed to the following: 1 → 3 → 5 → 7 → 9 → NULL.
There are several different methods for breaking a loop within a linked list. Can you please elaborate on these techniques for me?
Pinpointing and resolving a loop within a linked list
One possible technique is the employment of Floyd’s cycle-finding method.
To ensure prompt and effective troubleshooting, it’s crucial to establish the absence of loops within a linked list. One of the most expedient techniques for that is Floyd’s cycle-finding approach, which utilizes two pointers. The first pointer proceeds through the list at a gradual pace, while the other moves much faster. This method is commonly referred to as the ‘hare-tortoise algorithm’, named after the famous fable of The Tortoise and the Hare.
The following is a practical demonstration of how Floyd’s cycle-finding technique operates:
Step 1: At the start, both pointers (ptr1 and ptr2) are positioned at the root node.
Step 2: The pointers start traversing through the list, with ptr1 and ptr2 visiting the first and second nodes, respectively.
Step 3: As it travels at a faster pace, ptr2 will reach the end of the linked list before ptr1 does.
When the list is fully traversed, there are two possible scenarios that may arise.
In the case where the linked list is loop-free, ptr2, which moves forward by two nodes at a time, will end up pointing at null. This means that no matter how many nodes are included in the list, ptr2 will ultimately reach its conclusion. It is noteworthy that ptr2 will consistently be null, regardless of whether the number of nodes in the list is an odd or even integer.
In such situations, the function terminates execution and returns ‘no loop’ as the output when the null value is encountered.
The presence of loops is the second kind of scenario that might arise in linked lists. It is critical to bear in mind that pointers cannot point to an empty address; instead, they will travel the loop and reverse direction. Eventually, both pointers will converge upon a single node somewhere along the list’s course.
Observations indicate that when pointers encounter loops in the code, they begin to travel at varying speeds, which ultimately results in them colliding with each other. As a result of this collision, instead of pointing to null, ptr1 and ptr2 come to be equal. Consequently, the code comes to a halt, and a message is exhibited on the screen showing that a loop has been found.
It is evident that the two pointers will eventually intersect at a single node within the cyclical structure.
After confirming that the linked list is non-cyclic, it can be concluded that the first case has concluded. However, in the second case, we must now shift our focus to the problem’s second aspect, which calls for us to disrupt the cycle.
Resolving a circular link in a list of elements.
To eliminate the detected loop and ensure that the final element of the linked list points to NULL, a series of steps need to be taken. To aid in this process, here is a detailed procedure that you can employ.
Step 1: As established earlier, ptr1 and ptr2 converge at a single node within the loop. Therefore, it is imperative to identify the last element of the loop and ensure that it points to NULL, as demonstrated below.
Step 2: Retain ptr2 in its current state and modify ptr1’s direction to point back to the beginning of the loop, as shown in the highlighted section of the code below.
Step 3: Our subsequent move is to traverse the linked list by using two pointers – ptr1 and ptr2 – at the same time. Both pointers will advance from one node to the next, one after the other, until they eventually converge on a single node. At this point, the process is restarted.
Step 4: To put an end to the infinite loop, it is critical to set the value of pointer2 to null. It is significant to note that the point at which the two pointers’ subsequent values coincide is the starting point of the loop.
You may be perplexed as to why the “next” of ptr1 and ptr2 intersects at the initial node of the loop. But what is the reason for that?
To help clarify, take a look at the example below:
Let L be the number of nodes in the loop and N be the total number of elements in the list.
Therefore, in this instance, L = 5 and N = 12.
At the outset, both pointers are oriented towards the root node. Pointer 1 (ptr1) progresses by N-L units, which is 7 in this example. Since pointer 2 (ptr2) moves at twice the velocity of ptr1, the total number of steps taken by ptr2 should be increased by 2(N-L) steps.
As a result, the distance between the two pointers will be equivalent to (2N)(12-5L)/(N-L) = 2 nodes. This signifies that during a full cycle of the linked list, ptr2 will travel across (N-L) nodes.
To calculate the distance between two positions, follow these steps: Initially, separate the arrows by a distance of (N-L)%L+1. Then, increase the distance in a sequential manner by (N-L)%L + 2, (N-L)%L + 3, and so on. This sequence allows the distance between two locations to be calculated by travelling X nodes from the loop’s seed node, where X is determined with the formula (N-L)%L + X.
As soon as ptr1 and ptr2 converge on a single node, execution must be instantly halted. Since ptr2 travels around the loop once before rejoining ptr1, the two pointers will eventually cross paths when their distance apart is equal to L.
When X = L – ((N-L)%l), the distance between them is L. As per the above calculation, X is equivalent to 3.
Next, we shift pointer 1 (ptr1) back to the root node, while maintaining pointer 2 (ptr2) at its current location. Each pointer moves sequentially, traversing one node at a time. To reach the node in the first loop, ptr1 must traverse N-L nodes. Similarly, since ptr2 was two nodes away from the starting point (i.e., (N-L)%L), it must move through N-L nodes to get to the node of the original loop.
Fundamentally speaking, it is certain that ptr1 and ptr2 will intersect at the loop’s initial node in the linked list. To eliminate the loop, we can retrace our steps until ptr2 points to the entry node of the loop and then designate the node pointed to by ptr2 as NULL.
Below is a solution in the C programming language.
Output:
The code above initiates the linked list loop. Floyd’s method is employed to eliminate the loop, and the outcomes are printed accordingly.
Approach 2: Hashing
If the prior method appears too challenging, this one should be easy to follow. While traversing the list, additional nodes will be inserted into the unordered map.
If we encounter a node that is already present on the map, it indicates that we have reached the beginning of the loop.
Throughout the list’s traversal, we verify that the head and tail pointers are situated as intended. The node located at the list’s head is deemed active, while the node located at the end of the list is the node immediately preceding the active node.
At present, the head pointer of the loop refers to the starting point, while the last pointer indicates the node that precedes the one indicated by the head pointer. To break free from the loop, designate the value of the next pointer of the last node to NULL.
With this method, the last node in the loop no longer refers back to the first node but to NULL. Those interested in investigating the solution further may download implementations in C++, Java, and Python.
To remove loops from a linked list, we explored the use of extra pointers. We figured out how to recognize a loop in the list and discussed Floyd’s cycle-finding algorithm. To restructure the linked list, we employed two pointers moving at different speeds to identify the node where the loop starts. We then made the linked list linear by directing the last node to NULL. Additionally, we explored hashing as an alternative means of detecting the loop’s origin and removing cycles from the list.
Linked lists are among the most crucial data structures employed in programming, delivering a dataset that can be accessed by traversing nodes interlinked by pointers. To address any concerns regarding potential loops in the linked list, relevant code can be utilized to recognize and solve the issue.
