Programmation Java - Circulaire LinkedList

Question

Je tente d'écrire une classe java CircularList qui contient le nœud habituelle classe interne et les variables d'instance:

Answer 1

Conseil ... liste circulaire devrait avoir suivant et précédent au lieu de premier et dernier. La logique compte

Answer 2

OK, je ne vais pas vous donner l'implémentation complète de la classe, mais je vais vous donner quelques conseils.

1. Vous n'avez pas besoin de contenir une référence au dernier élément. Placez une référence précédente et suivante à vos nœuds et votre dernier nœud sera le premier.Prev

2. Outre le fait que les listes circulaires n'ont pas de fin, ils sont tout à fait les mêmes que les listes régulières, mais où vous trouvez le dernier élément comme celui-ci :

   Nœud tmp = premier;

   while (tmp.Next! = Null) tmp = tmp.Next;

Dans une liste circulaire, l'idée est comme ceci:

Node tmp = first; 

while (tmp.Next != first) 
    tmp = tmp.Next; 

Parce que vous ne trouverez jamais un nœud pointant vers nulle, sauf si la liste est vide. Un dernier conseil, si vous avez besoin de mettre en œuvre un indexeur, rappelez-vous que dans une liste circulaire il n'y a pas une telle chose que l'indice hors de portée, car

list[count] = list[0] = list[count * k] 

Gardez cela à l'esprit, donc le calcul de votre index pour ces méthodes peuvent être assez difficile. Pour les index positifs, l'idée principale est:

index = index % count; 

Pour les négatifs, c'est légèrement différent. J'espère pouvoir vous aider avec mes mots. Si vous voulez une mise en œuvre, je crois qu'il devrait y avoir quelques-uns si vous demandez poliment à Google :)

Bonne chance!

Answer 3

Je ne sais pas quel est votre problème, vous semblez avoir tout ce dont vous avez besoin. La seule différence entre cette liste liée et une normale serait d'ajouter à la fin.

Dans une liste liée régulière, vous créez un nouveau noeud et définissez le dernier élément sur ce noeud. Dans ce cas, vous changez le pointeur dans le • Dernier nœud pour pointer vers le nouveau nœud, et faites pointer le nouveau nœud sur • Premier.

La suppression fonctionne de la même manière qu'une liste chaînée normale. Chaque fois que vous voulez supprimer un nœud, vous trouvez quel autre nœud pointe vers celui-ci (soit en précédent, soit en supprimant le premier, vérifiez • Dernier) et faites le pointer vers l'endroit où le nœud en cours de suppression pointait.

Si cela ne résout pas votre problème, faites le moi savoir et je vais essayer de vous aider.

Juste quelqu'un a déjà remarqué demandé exactement la même question: Can I use java.util.LinkedList to construct a circular/cyclic linked list?

Answer 4

class Node { 
    int value; 
    Node next; 
    Node prev; 
    Node(int initialValue) { 
     value = initialValue; 
     next = null; 
     prev = null; 
    } 
    public int getValue() { 
     return this.value; 
    } 
} 

class NodeList { 
    Node pointer; 
    NodeList() { 
     pointer = null; 
    } 
    public void insertNode(int nodeValue) { 
     Node newNode = new Node(nodeValue); 
     if(pointer == null) { 
      newNode.next = newNode; 
      newNode.prev = newNode; 
     }else if(pointer.next == null && pointer.prev == null && pointer != null) { 
      newNode.next = pointer; 
      newNode.prev = pointer; 
      pointer.prev = newNode; 
      pointer.next = newNode; 
     } 
     else if(pointer != null) { 
      newNode.next = pointer.next; 
      newNode.prev = pointer; 
      pointer.next.prev = newNode; 
      pointer.next = newNode; 
     } 
     pointer = newNode; 
     System.out.println(“Successfully inserted : ” + pointer.getValue()); 
    } 
    public void printRing(boolean direction) { 
     Node tempNode = pointer; 
     do { 
      System.out.println(“Value = ” + tempNode.getValue()); 
      tempNode = direction ? tempNode.next : tempNode.prev; 
     } while(tempNode.value != pointer.value);  
    }  
}