English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية

Tutoriais Básicos de Java

Java Controle de Fluxo

Java Array

Java Orientação a Objetos (I)

Java Orientação a Objetos (II)

Java Orientação a Objetos (III)

Tratamento de Exceção Java

Java Lista (List)

Java Fila (Queue)

Java Conjunto Map

Java Conjunto Set

Java Entrada e Saída (I/O)

Java Reader/Writer

Outros tópicos Java

Java programa para detectar se existe loop no LinkedList

Java Examples Comprehensive

Neste exemplo, vamos aprender a detectar se existe loop no LinkedList do Java.

Para entender este exemplo, você deve conhecer o seguinteProgramação JavaTema:

Exemplo: Detecção de loop no LinkedList

class LinkedList {
  //Criar objeto da classe Node
  //Representa a cabeça da lista
  Node head;
  //Classe interna estática
  static class Node {
    int value;
    //Conectar cada nó ao nó seguinte
    Node next;
    Node(int d) {
      value = d;
      next = null;
    }
  }
  //Verificar se há loop
  public boolean checkLoop() {
    //Criar duas referências no início de LinkedList
    Node first = head;
    Node second = head;
    while(first != null && first.next != null) {
      //Mover a primeira referência2nó
      first = first.next.next;
      //Mover a segunda referência1nó
      second = second.next;
      //Se os dois referenciadores forem iguais (encontrado)
      if(first == second) {
        return true;
      }
    }
    return false;
  }
  public static void main(String[] args) {
    //Criar objeto LinkedList
    LinkedList linkedList = new LinkedList();
    //Atribuir valor a cada nó da lista encadeada
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);
    //Conectar cada nó da lista encadeada ao nó seguinte
    linkedList.head.next = second;
    second.next = third;
    third.next = fourth;
    //Realizar loop em LinkedList
    fourth.next = second;
    //Imprimir valor do nó
    System.out.print("LinkedList: ");
    int i = 1;
    while (i <= 4) {
      System.out.print(linkedList.head.value + "");
      linkedList.head = linkedList.head.next;
      i++;
    }
    //Chama método para verificar loop
    boolean loop = linkedList.checkLoop();
    if(loop) {
      System.out.println("\nThere is a loop in LinkedList.");
    }
    else {
      System.out.println("\nThere is no loop in LinkedList.");
    }
  }
}

Output Result

LinkedList: 1 2 3 4 
There is a loop in LinkedList.

. In the above example, we have used Java implemented LinkedList. We usedFloyd's Cycle Detection Algorithmto check if there is a loop in LinkedList.

Note the code in the checkLoop() method. Here, we have two variables named first, second, which traverse the nodes in LinkedList.

  • first - in a single iteration2nodes for traversal

  • second - in a single iteration1nodes for traversal.

Two nodes traverse at different speeds. Therefore, if there is a loop in LinkedList, they will meet.

Java Examples Comprehensive