https://learnprogramming.in.net/detect-loop-in-linked-list-bash-program/
Detecting a Loop in a Linked List using Bash
In this guide, we will create a Bash script to detect if a singly linked list contains a loop. A loop in a linked list occurs when a node’s next pointer points back to a previous node, creating a cycle.
Program Explanation
We will use Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm) to detect the loop. The idea behind this algorithm is that if there is a loop in the linked list, the faster pointer (hare) will eventually meet the slower pointer (tortoise).
Steps:
- We will define two pointers,
slowandfast. - Initially, both pointers will start at the head of the linked list.
- The
slowpointer will move one step at a time, while thefastpointer will move two steps at a time. - If there is a loop, the
fastpointer will eventually meet theslowpointer within the loop. - If the
fastpointer reaches the end of the linked list (NULL), then there is no loop.
Bash Script
Here is the Bash script that implements this logic:
#!/bin/bash
# Node structure
declare -A node1=( ["data"]=1 ["next"]="node2" )
declare -A node2=( ["data"]=2 ["next"]="node3" )
declare -A node3=( ["data"]=3 ["next"]="node4" )
declare -A node4=( ["data"]=4 ["next"]="node5" )
declare -A node5=( ["data"]=5 ["next"]="node3" ) # Creates a loop
# Detect Loop function using Floyd's Cycle-Finding Algorithm
detect_loop() {
local slow=$1
local fast=$1
while true; do
# Move slow pointer by one step
slow=${!slow[next]}
# Move fast pointer by two steps
fast=${!fast[next]}
[ -n "${!fast[next]}" ] && fast=${!fast[next]} || break
# If slow and fast meet, there is a loop
if [ "$slow" == "$fast" ]; then
echo "Loop detected in the linked list."
return
fi
# If fast reaches the end, no loop exists
[ -z "$fast" ] && break
done
echo "No loop detected in the linked list."
}
# Start the detection
detect_loop "node1"
Documentation
This Bash script is structured to simulate a linked list using associative arrays, where each array represents a node.
Node Representation
Each node is defined as an associative array with two keys:
data: Holds the value of the node.next: Holds the reference to the next node in the list.
detect_loop Function
The detect_loop function is responsible for checking if there is a loop in the linked list:
- The function accepts the name of the first node as an argument.
- It initializes two pointers,
slowandfast, both starting at the head of the linked list. - The
whileloop runs until the end of the list is reached or a loop is detected. - In each iteration, the
slowpointer advances by one node, and thefastpointer advances by two nodes. - If the
slowpointer andfastpointer meet, a loop is detected. - If the
fastpointer reaches the end of the list, it breaks out of the loop, indicating no loop is present.
Conclusion
Floyd’s Cycle-Finding Algorithm is an efficient way to detect a loop in a linked list with a time complexity of O(n) and no additional space requirement. This Bash script provides a simple implementation that can be easily adapted for different use cases.
