Python Program To Detect A Loop In A Linked List
Linked lists are commonly used data structures. Sometimes, a linked list can have a cycle or a loop in it. A cycle is defined as a set of nodes, where the last node points to one of the previous nodes. This can cause problems while traversing the linked list, as an infinite loop will be formed. In this article, we will discuss a Python program to detect a loop in a linked list.
What is a Linked List?
A linked list is a data structure consisting of a group of nodes which together represent a sequence. Each node contains data and a link to the next node in the sequence. Linked lists are a popular choice for many applications because of their flexibility, and because they can effectively handle data of varying sizes.
How to implement a Linked List in Python?
To implement a linked list in Python, we will need to create a class for the node, and another class for the linked list. In the node class, we will define the data, and a reference to the next node. In the linked list class, we will define the head, which will refer to the first node in the linked list.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
How to detect a loop in a Linked List?
To detect a loop in a linked list, we need to use the Floyd’s cycle-finding algorithm, also known as the Tortoise and the Hare algorithm. This algorithm uses two pointers, one tortoise and one hare. The hare pointer moves twice as fast as the tortoise pointer. If there is a loop in the linked list, eventually the hare pointer will catch up to the tortoise pointer.
def has_cycle(self):
tortoise = self.head
hare = self.head
while hare != None and hare.next != None:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False
In the above code, we have initialized two pointers, tortoise and hare, to the head of the linked list. We then move the pointers, with the hare pointer moving twice as fast as the tortoise pointer. If there is a loop in the linked list, eventually the hare pointer will catch up to the tortoise pointer, and they will be equal. If there is no loop, then the hare pointer will reach the end of the linked list, and the function will return False.
How to test the Linked List program?
To test the linked list program, we need to create a linked list, and add some nodes to it. We can then link two nodes to create a loop, and then use the has_cycle function to check if there is a loop in the linked list.
# create a linked list with a loop
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
llist.head.next = second
second.next = third
third.next = fourth
# create a loop
fourth.next = second
# check for cycle
print(llist.has_cycle()) # output: True
In the above code, we have created a linked list with four nodes. We then create a loop by linking the fourth and second nodes. We then use the has_cycle function to check for a loop in the linked list, which returns True.
Conclusion
In this article, we have discussed how to detect a loop in a linked list using the Floyd’s cycle-finding algorithm. We have also discussed how to implement a linked list in Python. By using the code provided, you can easily detect a loop in a linked list in Python. Linked lists are an essential data structure in computer science, and this program can be useful in many applications.