data_structures.linked_list.floyds_cycle_detection

Floyd’s cycle detection algorithm is a popular algorithm used to detect cycles in a linked list. It uses two pointers, a slow pointer and a fast pointer, to traverse the linked list. The slow pointer moves one node at a time while the fast pointer moves two nodes at a time. If there is a cycle in the linked list, the fast pointer will eventually catch up to the slow pointer and they will meet at the same node. If there is no cycle, the fast pointer will reach the end of the linked list and the algorithm will terminate.

For more information: https://en.wikipedia.org/wiki/Cycle_detection#Floyd’s_tortoise_and_hare

Attributes

linked_list

Classes

LinkedList	A class representing a singly linked list.
Node	A class representing a node in a singly linked list.

Module Contents

class data_structures.linked_list.floyds_cycle_detection.LinkedList

A class representing a singly linked list.

__iter__() → collections.abc.Iterator

Iterates through the linked list.

Returns:

Iterator: An iterator over the linked list.

Examples: >>> linked_list = LinkedList() >>> list(linked_list) [] >>> linked_list.add_node(1) >>> tuple(linked_list) (1,)

add_node(data: Any) → None

Adds a new node to the end of the linked list.

Args:

data (Any): The data to be stored in the new node.

Examples: >>> linked_list = LinkedList() >>> linked_list.add_node(1) >>> linked_list.add_node(2) >>> linked_list.add_node(3) >>> linked_list.add_node(4) >>> tuple(linked_list) (1, 2, 3, 4)

detect_cycle() → bool

Detects if there is a cycle in the linked list using Floyd’s cycle detection algorithm.

Returns:

bool: True if there is a cycle, False otherwise.

Examples: >>> linked_list = LinkedList() >>> linked_list.add_node(1) >>> linked_list.add_node(2) >>> linked_list.add_node(3) >>> linked_list.add_node(4)

>>> linked_list.detect_cycle()
False

# Create a cycle in the linked list >>> linked_list.head.next_node.next_node.next_node = linked_list.head.next_node

>>> linked_list.detect_cycle()
True

head: Node | None = None

class data_structures.linked_list.floyds_cycle_detection.Node

A class representing a node in a singly linked list.

data: Any

next_node: Self | None = None

data_structures.linked_list.floyds_cycle_detection.linked_list