Java >> Java tutorial >  >> Java

Java-program til at detektere en sløjfe i en sammenkædet liste

Java

I denne tutorial vil vi se, hvordan man opdager en løkke i en sammenkædet liste i java. LinkedList er en lineær datastruktur, hvor elementerne ikke er gemt på sammenhængende steder, og hvert element er et separat objekt med en datadel og adressedel. Hvert element er kendt som en node. På grund af dynamikken og lette indsættelser og sletninger foretrækkes de frem for arrays. Men før du går videre, hvis du ikke er bekendt med konceptet med den linkede liste i java, så tjek artiklen om Linked List i Java.

Input: Indtast Linked List-elementerne:6 7 8 4 5

Output: Løkke fundet

Dette kan gøres ved at bruge følgende metoder:

Fremgangsmåde 1:Brug af Hash-Set

Fremgangsmåde 2:Uden at bruge Hash-Set

Lad os se på hver af disse tilgange for en bedre forståelse.

Program 1:Find en sløjfe i en sammenkædet liste

I dette program vil vi se, hvordan man detekterer en løkke i en sammenkædet liste ved hjælp af hashing-tilgang.

Algorithme:

  1. Start
  2. Opret en linket liste.
  3. Tilføj elementer til listen.
  4. Brug en boolesk metode til at kontrollere, om der findes en løkke eller ej.
  5. Brug et HashSet til det samme.
  6. Gennemgå listen én efter én, og bliv ved med at indsætte nodeadresserne i en Hash-tabel.
  7. Hvis null er nået på et hvilket som helst tidspunkt, så returner false.
  8. Hvis den næste aktuelle node peger på en af ​​de tidligere gemte noder i HashSet, skal du returnere sand.
  9. Vis resultatet.
  10. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

// 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");
	}
}


Loop fundet

Program 2:Find en sløjfe i en sammenkædet liste

I dette program vil vi se, hvordan man finder en løkke i en sammenkædet liste.

Algorithme:

  1. Start
  2. Opret en linket liste.
  3. Opret en linket liste.
  4. Tilføj elementer til listen.
  5. Brug en boolesk metode til at kontrollere, om der findes en løkke eller ej.
  6. Deklarer en temp-variabel og initialiser den til 0.
  7. Gennemgå den linkede liste, og bliv ved med at markere besøgte noder.
  8. Hvis en besøgt node findes igen, er der en løkke.
  9. Vis resultatet.
  10. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

// 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");
    }
}


Loop fundet


Java tag