🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
A common challenge when working with linked lists is cycle detection. A cycle in a linked list means that if you traverse the list indefinitely, you'll find yourself looping through the same set of nodes over and over again. Detecting such cycles is crucial for many algorithms to avoid infinite loops and potential system crashes.
2. Program Overview
Our program aims to detect a cycle in a given linked list. We will:
1. Define a Node class that represents each element in the linked list.
2. Create a LinkedList class with methods to:
- append data to the list.
- create_cycle for intentionally introducing a cycle for testing.
- detect_cycle which will identify if the list contains a cycle.
We'll employ Floyd’s cycle-finding algorithm, often termed as the "Tortoise and the Hare" approach. This technique uses two pointers that move through the list at different speeds.
3. Code Program
class Node:
def __init__(self, data):
"""Initialize node with data and next as None."""
self.data = data
self.next = None
class LinkedList:
def __init__(self):
"""Initialize linked list with head as None."""
self.head = None
def append(self, data):
"""Add data to the end of the linked list."""
new_node = Node(data)
if not self.head:
self.head = new_node
return
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
def create_cycle(self, n):
"""Introduce a cycle in the linked list for testing purposes."""
if self.head is None:
return
tail = self.head
while tail.next:
tail = tail.next
node = self.head
for i in range(n):
if node is None:
return
node = node.next
tail.next = node
def detect_cycle(self):
"""Use Floyd's cycle detection algorithm to identify a cycle."""
tortoise = self.head
hare = self.head
while hare and hare.next:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False
# Demonstration
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(5)
print(llist.detect_cycle()) # False
llist.create_cycle(2)
print(llist.detect_cycle()) # True
Output:
False True
4. Step By Step Explanation
1. The Node class represents individual items in our linked list. Each node has data and a reference to the next node.
2. In the LinkedList class, the append method is for adding data to the list. We traverse the list until we find a node with no next node and then add the new data there.
3. The create_cycle method introduces a cycle in our list intentionally by making the next of the tail nodes point back to some node in the list.
4. Our cycle detection relies on the detect_cycle method using the "Tortoise and the Hare" approach. If there's a cycle, the fast-moving hare will eventually catch up to the slower-moving tortoise, and they will both point to the same node. If they do, it confirms a cycle.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment