0
votes

Doublement insertion LL à l'extrémité collée sur la boucle

Je n'arrive pas à comprendre pourquoi l'insertion d'un nœud à la fin d'une liste doublement liée reste bloquée dans une boucle. Soit il est coincé dans une boucle, soit un pointeur nul. J'aimerais également savoir si le nœud public est meilleur ou si le nœud public est vide lorsqu'il s'agit de listes liées ou de structures de données.

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode;
    }
    newNode.previous = last;
    return newNode;
}

java data-structures

0 commentaires

4 Réponses :

1
votes

Dans votre boucle while :

while(last.next != null) {
   last = last.next;
}
last.next = newNode;

La deuxième ligne définit last.next sur newNode afin à la prochaine itération, last sera défini sur newNode , qui est le champ next est nul. Vous ne voulez définir last.next sur newNode qu'une seule fois last.next == null (lorsque vous avez atteint la fin de la liste):

while(last!=null) {
    last = last.next;
    last.next = newNode;
}

2 commentaires

Oui, j'ai essayé cela et défini le newNode.previous pour durer, mais cela me donne une exécution de pointeur nul.

@ madil26 Je ne peux pas reproduire cela. Pourriez-vous publier un exemple reproductible minimal s'il vous plaît?

2
votes

Eh bien, c'est à cause de cette partie de la logique

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last.next != null) {
        last = last.next;
    }
    last.next = newNode;
    newNode.previous = last;
    return newNode;
}

Une fois la liste chaînée déjà créée, vous essayez d'aller au dernier élément. Cependant, au cours de cette traversée, vous avez également changé le pointeur suivant vers lequel le nœud pointait.

Essayez de changer votre logique en:

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode; //// This shouldn't happen.
    }

p >

1 commentaires

C'est ce que j'ai fait au début et cela ne fonctionnera pas, cela me donne une exception de pointeur nul.

1
votes

Quant à la deuxième partie de la question, elle dépend de la façon dont un client / appelant de cette API s'attendrait à ce que la sortie soit.

Ecrivez-vous cette API pour être utilisée dans un autre programme que vous écrivez? Dans ce cas, demandez-vous s'il vous sera utile d'obtenir le Node nouvellement créé comme valeur de retour de cette API, ou s'il est acceptable de le laisser comme nul.

Pour référence, l'implémentation Java de l'API a void comme type de retour. ( https: // docs. oracle.com/javase/7/docs/api/java/util/LinkedList.html#addLast(E) )

3 commentaires

J'utilise juste un nœud, cela me permet de comprendre plus facilement l'idée de liste liée. Mais de mon manque de confiance, peu importe si c'est vide ou Node tant qu'il fonctionne, mais je sais que ce n'est pas une convention en ce qui concerne les API

Votre compréhension est correcte, dans ce cas, cela n'a pas d'importance tant que cela fonctionne. De plus, comme votre question initiale n'est pas résolue, pourriez-vous mettre à jour la question avec la trace de pile du NPE? Lance-t-il un NPE lorsque vous insérez pour la première fois ou les fois suivantes?

public Node insertEnd (int data) {Node newNode = new Node (data); newNode.next = null; if (head == null) {head = newNode; return newNode; } Dernier nœud = tête; while (last.next! = null) {last = last.next; } last.next = newNode; newNode.previous = dernier; return newNode; }

1
votes

Pour répondre à la 1ère partie, vous devez apporter les modifications suivantes à votre code -

 Node last = head;
    while(last.next!=null) { // be careful- it should be last.next!=null instead of last!=null , as it will give null pointer exception.
        last = last.next;    
    }
    last.next = newNode;
    newNode.previous = last;
    return newNode;

comme l'instruction "last.next = newNode;" dans while loop définissait le dernier sur newNode dans la première itération elle-même.

pour la 2ème partie de votre question, cela dépend de la nécessité d'appeler la fonction.

0 commentaires