Java >> Tutoriel Java >  >> Java

Programme Java pour détecter une boucle dans une liste chaînée

Java

Dans ce tutoriel, nous allons voir comment détecter une boucle dans une liste chaînée en java. LinkedList est une structure de données linéaire où les éléments ne sont pas stockés dans des emplacements contigus et chaque élément est un objet séparé avec une partie données et une partie adresse. Chaque élément est appelé nœud. En raison de la dynamique et de la facilité des insertions et des suppressions, ils sont préférés aux tableaux. Mais avant d'aller plus loin, si vous n'êtes pas familier avec le concept de liste chaînée en Java, consultez l'article sur la liste chaînée en Java.

Saisie : Saisissez les éléments de la liste chaînée :6 7 8 4 5

Sortie : Boucle trouvée

Cela peut être fait en utilisant les méthodes suivantes :

Approche 1 : utiliser Hash-Set

Approche 2 :sans utiliser Hash-Set

Examinons chacune de ces approches pour une meilleure compréhension.

Programme 1 :Détecter une boucle dans une liste chaînée

Dans ce programme, nous verrons comment détecter une boucle dans une liste chaînée en utilisant l'approche de hachage.

Algorithme :

  1. Commencer
  2. Créer une liste liée.
  3. Ajouter des éléments à la liste.
  4. Utilisez une méthode booléenne pour vérifier si une boucle existe ou non.
  5. Utilisez un HashSet pour la même chose.
  6. Parcourez la liste une par une et continuez à mettre les adresses de nœud dans une table de hachage.
  7. À tout moment, si null est atteint, renvoie false.
  8. Si le nœud actuel suivant pointe vers l'un des nœuds précédemment stockés dans HashSet, renvoie true.
  9. Afficher le résultat.
  10. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

// Java program to detect loop in a linked list
import java.util.*;
public class LinkedList 
{
	static Node head; // head of list
	/* Linked list Node*/
	static class Node {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	static public void add(int newData)
	{
		Node newNode = new Node(newData);
		newNode.next = head;
		head = newNode;
	}
	static boolean checkLoop(Node n)
	{
		HashSet<Node> hset = new HashSet<Node>();
		while (n != null) {
			if (hset.contains(n))
				return true;
			hset.add(n);
			n = n.next;
		}
		return false;
	}
	//Driver program
	public static void main(String[] args)
	{
		LinkedList ll = new LinkedList();
		ll.add(8);
		ll.add(12);
		ll.add(15);
		ll.add(21);
		ll.head.next.next.next.next = ll.head;
		if (checkLoop(head))
			System.out.println("Loop found");
		else
			System.out.println("No Loop found");
	}
}


Boucle trouvée

Programme 2 :Détecter une boucle dans une liste chaînée

Dans ce programme, nous allons voir comment détecter une boucle dans une liste chaînée.

Algorithme :

  1. Commencer
  2. Créer une liste liée.
  3. Créer une liste liée.
  4. Ajouter des éléments à la liste.
  5. Utilisez une méthode booléenne pour vérifier si une boucle existe ou non.
  6. Déclarez une variable temporaire et initialisez-la à 0.
  7. Parcourez la liste liée et continuez à marquer les nœuds visités.
  8. Si un nœud visité est retrouvé, il y a une boucle.
  9. Afficher le résultat.
  10. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

// Java program to detect loop in a linked list
import java.util.*;
public class Main
{
    static class Node
    {
       int data;
       Node next;
       int temp;
    };
    static Node add(Node newHead, int newData)
    {
        Node newNode = new Node();
        newNode.data = newData;
        newNode.temp = 0;
        newNode.next = newHead;
        newHead = newNode;
        return newHead;
    }
    static boolean detect(Node n)
    {
        while (n != null)
        {
            if (n.temp == 1)
               return true;
            n.temp = 1;
            n = n.next;
        }
        return false;
    }
    // Driver code
    public static void main(String[] args)
    {
        Node head = null;
        head = add(head, 20);
        head = add(head, 4);
        head = add(head, 15);
        head = add(head, 10);
        head.next.next.next.next = head;
        if (detect(head))
           System.out.print("Loop found");
        else
           System.out.print("No Loop found");
    }
}


Boucle trouvée


Balise Java