Comment mettre en œuvre la circulaire liste liée dans java?

J'ai lu un livre sur les "structures de Données et algorithmes", dans lequel il est d'affectation qui me demande de mettre en œuvre une circulaire de la liste liée. C'est un exercice d'apprentissage et mon code ne peut pas être d'un très haut standard.

L'idée principale derrière mon de la mise en œuvre d'une circulaire de la liste chaînée est d'avoir un pointeur qui pointe sur le dernier élément et chaque fois j'ai ajouter un nouvel élément, le champ suivant du dernier élément sera actualisé pour pointer vers la nouvelle rubrique.

La méthode d'insertion fonctionne très bien, je peux ajouter un élément sans aucun problème, mais pour une raison que je ne peux pas supprimer des éléments de la liste.

Voici le code pour le "Lien" ou "Nœud":

public class Link {
  public long data;
  public Link next;

  public Link(long val) {
    data = val;
    next = null;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }

}  //end class

C'est le code pour la classe qui effectue les travaux, et le bug est évidemment quelque part ici:

public class CircularList {
Link first;
Link last;

public CircularList() {
     first = null;
     last = null;
}

public Link find(long key) {
    Link current = first;
    while(current.data != key) {
        current = current.next;
    }
    return current;
} //end find

public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    return temp;
}  //end delete

public boolean isEmpty() { return (first == null); }

public void insert(long val) {
    Link newLink = new Link(val);

    if(isEmpty())
        last = newLink;

    newLink.next = first;
    first = newLink;
    last.next = first;
} //end insert

public void displayAmount(int n) {
    Link current = first;
    while(n>0) {
        current.displayLink();
        current = current.next;
        n--;
    }
    System.out.println("");
} //end displayAmount

}  //end class

Et de l'application principale code:

public class App {
public static void main(String[] args) {
    CircularList cl = new CircularList();

    cl.insert(10);
    cl.insert(20);
    cl.insert(30);
    cl.insert(40);

    cl.displayAmount(6);

    cl.delete();

    cl.displayAmount(6);
}
}  //end class

L'affichage de la quantité semble un peu idiot, je viens d'essayer d'éviter la boucle infinie et fait quelque chose de simple qui fonctionne, tout simplement.

Et quelle est votre question?
Votre liste liée nœud n'est pas une référence au nœud précédent, la rendant impossible. Vous voulez avoir le dernier élément se référer à la première ainsi que la première à la dernière, qui signifie à la fois besoin d'un suivant et précédent. Avec ces derniers, vous pouvez prendre n'importe quel élément, obtenir la précédente et la suivante sur l'élément courant et connectez précédente et suivante, de manière efficace de la découpe de l'élément à supprimer.
le delete() méthode comme il est toujours (essaie de supprimer le premier élément, qui est OK parce que son prédécesseur est last. Vous auriez besoin d'être doublement lié, si vous vouliez supprimer arbitraire des éléments, mais si vous ne jamais supprimer first, vous n'en avez pas besoin.
Ce lien peut être utile pour vous sanfoundry.com/...

OriginalL'auteur SuperManEver | 2015-01-04

data-structures java

4

Ajouter last.next = first avant return temp dans votre delete() fonction:
```
public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    if(last != null)
        last.next = first
    return temp;
} 
```
Mise à jour:

Je ne peux pas trouver un scénario qui satisfont first.next == null, et nous devons prendre en considération l'appel à delete() sur une liste vide.
```
public Link delete() {
    Link temp = first;
    if(first == null){
        ;  //or you can throw some exception as a warning
    }
    else if(first==last){  //only one element
        first = null; //reset to initial state
        last = null;
    }
    else{
        first = first.next;
        last.next = first;
    }
    return temp;
} 
```
Vous n'avez pas besoin de votre null vérifier: si first n'est pas nulle alors last ne peut pas être null (parce que si vous avez juste un élément puis first == last).
Aussi longtemps que le premier.suivant == null pourrait être vrai, je pense que nous avons besoin de cette null vérifier que nous avons mis la dernière à null. Cependant, j'ai remarqué que ne pourrait jamais arriver, donc j'ai mis à jour ma réponse et a ajouté défensive code pour une autre affaire qui nous delete() sur une liste vide.

OriginalL'auteur Paul Lo
1

Votre delete() méthode ne gère pas la circularité de la liste. Le dernier élément pointe vers le premier élément; que la mise à jour lorsque le premier élément est supprimé.

En d'autres termes, vous devez définir last.next pour pointer vers le nouveau first plutôt que de l'ancien first.

L'autre problème que vous avez est que si vous supprimez l'élément final (alors que c'est maintenant vide), alors vous devez également définir last à null.
```
public Link delete() {
    if (first.next == null) {
        first = null;
        last = null;
    }
    Link temp = first;
    first = first.next;
    last.next = first;
    return temp;
} 
```
vous variante est également à l'œuvre. Et au moins pour moi, il est beaucoup claire transmettre l'idée.

OriginalL'auteur chiastic-security

Vous devez vous connecter pour publier un commentaire.