Programme Java : recherche d'éléments dans une liste chaînée circulaire

Que sont les listes et les listes chaînées circulaires ?

Une liste chaînée est une structure de données dans laquelle chaque nœud contient deux parties, des données et un chemin d'adresse. Ces sections pointent vers le nœud suivant, ce qui crée toujours une interconnexion avec le nœud précédent. Sur cette base, une liste chaînée circulaire est une liste dans laquelle le dernier nœud a un lien interne avec le premier nœud, c'est pourquoi ce type de liste chaînée est appelé liste chaînée circulaire.

Dans l'environnement Java, lorsque nous recherchons des éléments dans une liste chaînée circulaire, nous devons créer un nœud temporaire dans la liste chaînée vers lequel pointer. De cette façon, nous devons encore déclarer deux variables. Il s'agit de l'index des pistes et de la recherche des pistes. Si le nœud Temp est vide au point de départ, il est important de parcourir la liste car elle ne contient aucun élément à ce stade.

Comment fonctionne une liste chaînée circulaire et ses applications ?

Comment fonctionne la liste chaînée circulaire

Avec une liste chaînée circulaire, l'utilisateur peut saisir des données n'importe où dans cette liste particulière (dans un tableau, ce qui n'est pas possible en mémoire contiguë). Dans cette liste chaînée, les données en arrière sont stockées en tant que nœud d'adresse suivant. De cette manière, les données pointent les unes vers les autres de manière circulaire, formant des chaînes circulaires de tailles dynamiques. Ici, des moyens dynamiques ; l’allocation de mémoire sera effectuée selon les besoins.

Vous devez vous rappeler les points suivants

• N'importe quel nœud peut être utilisé comme point de départ de la liste chaînée circulaire

• La liste de données peut être parcourue à partir de n'importe quel nœud aléatoire

• Il n'y a pas de pointeur vers le premier nœud ici

Application de la liste chaînée circulaire

• Les listes chaînées circulaires utilisées dans nos ordinateurs personnels sont plusieurs applications qui effectuent leurs tâches simultanément.

• Utilisé pour créer des files d'attente circulaires.

• Parcourez les joueurs dans les jeux multijoueurs.

• Pour la fonctionnalité Annuler dans les applications Word ou Photoshop.

Algorithme de liste chaînée circulaire

La méthode de mise en œuvre et de fonctionnement de la liste chaînée circulaire est très simple. Il y a deux caractéristiques, les données et ensuite. Pour définir une autre liste chaînée circulaire, nous pouvons utiliser : head et tail. Le nouveau nœud est toujours défini par le "nœud actuel", qui pointera vers la tête de la liste chaînée. Le point se déplace vers le nœud suivant après chaque itération.

• Étape 1 - Déclarez un newNode() avec la valeur donnée.

• Étape 2 - Recherchez dans la liste des invalides.

• Étape 3 − Si le résultat est nul, alors head = newNode().

• Étape 4 - Sinon, définissez le pointeur de nœud comme temp et initialisez-le.

Syntaxe de la liste chaînée circulaire

struct Node {int dataset; struct Node * to next;};

Dans cette syntaxe, chaque nœud présent dans la liste possède une partie données et pointeur qui est utilisée pour créer un nouveau nœud lorsqu'une nouvelle entrée est reçue.

Nous pouvons rechercher un élément dans une liste spécifique en utilisant la méthode suivante -

• En ajoutant de nouvelles données à une liste spécifique

• En recherchant des éléments dans une liste chaînée circulaire spécifique

En ajoutant de nouvelles données à une liste chaînée spécifique

L'ajout de nouveaux éléments dans un nouveau nœud permet de découvrir certaines données spécifiques de la liste chaînée circulaire. Tout d'abord, vous devez insérer un nouveau nœud dans la mémoire allouée. Une fois les nouvelles données stockées, les données suivantes peuvent être modifiées vers le nouveau nœud. Vous pouvez également stocker des données supplémentaires à la fin du nœud et appliquer un parcours.

Exemple

public class SearchNodearb {   
   public class Nodefind{  
      int datafall;  
      Nodefind next;  
      public Nodefind(int datafall) {  
         this.datafall = datafall;  
      }  
   }  
   public Nodefind head = null;  
   public Nodefind tail = null;  
   public void add(int datafall){   
      Nodefind newNode1 = new Nodefind(datafall);      
      if(head == null) {        
         head = newNode1;  
         tail = newNode1;  
         newNode1.next = head;  
      }  
      else {     
         tail.next = newNode1;
            
         tail = newNode1;         
         tail.next = head;  
      }  
   }  
   public void search(int element) {  
      Nodefind current = head;  
      int i = 1;  
      boolean flagon = false;  
              
      if(head == null) {  
         System.out.println("List is totally Void! So Sad!");  
      }  
      else {  
         do{  
            if(current.datafall ==  element) {  
               flagon = true;  
               break;  
            }  
            current = current.next;  
            i++;  
         }while(current != head);  
         if(flagon)  
         System.out.println("Element is present in the list with a position tag : " + i);  
         else  
         System.out.println("Element is not present in the list");  
      }  
   }  
   public static void main(String[] args) {  
      SearchNodearb cl1 = new SearchNodearb();            
      cl1.add(1000);  
      cl1.add(5000);  
      cl1.add(3);  
      cl1.add(4);  
      cl1.search(2);  
      cl1.search(5000);  
   }  
} 

Sortie

Element is not present in the list
Element is present in the list with a position tag: 2

En recherchant des éléments dans une liste chaînée circulaire spécifique

Tout d'abord, vous devez initialiser un nœud, puis compteur f=0. Si la position head est vide, la liste entière est vide. Sinon, parcourez la liste complète. Si la sortie est zéro, l'élément n'a pas été trouvé dans la liste.

Exemple

public class search {
   class Nodeval {
      int data;
      Nodeval next;
      public Nodeval(int data) { this.data = data; }
   }
   public Nodeval head = null;
   public Nodeval tempo = null;
   public void addNode2001(int data){
      Nodeval new10 = new Nodeval(data);
      if (head == null) {
         head = new10;
      }
      else {
         tempo.next = new10;
      }
      tempo = new10;
      tempo.next = head;
   }
   public void find(int key){
      Nodeval temp07 = head;     
      int f = 0;
      if (head == null) {
         System.out.println("List is empty, Please Fill It ASAP");
      }
      else {
         do {
            if (temp07.data == key) {
               System.out.println(
               "element is present in the running list");
               f = 1;
               break;
            }
            temp07 = temp07.next;
         } while (temp07 != head);
         if (f == 0) {
            System.out.println(
            "element is not present here, I am sorry!");
         }
      }
   }
   public static void main(String[] args){
      search srdd = new search();
      srdd.addNode2001(5);
      srdd.addNode2001(4);
      srdd.addNode2001(3);
      srdd.addNode2001(2);
      srdd.find(2);
      srdd.find(6);
   }
} 

Sortie

element is present in the running list
element is not present here, I am sorry!

Conclusion

L'utilisation de listes chaînées circulaires présente de nombreux avantages et inconvénients. L'avantage le plus important est que les opérations de parcours peuvent être lancées à partir de n'importe quel nœud de la liste chaînée. Pas besoin d'utiliser NULL, très utile pour la planification du cycle CPU. Mais le plus gros inconvénient est que si la liste n’est pas écrite correctement, elle peut se transformer en une boucle infinie et le serveur peut se bloquer. Grâce à cet article, nous avons appris à rechercher des éléments dans une liste chaînée circulaire à l'aide de Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!