Liste doublement chaînée: ajout d'un nœud au début. De geeksforgeeks (code java)

Question

Il s'agit d'un code qui ajoute un nœud au début de la liste doublement liée. Ce que je ne comprends pas ici, c'est l'étape 4. Ici, il me semble qu'il stocke l'adresse du new_Node dans la variable head.prev. La variable head.prev contiendra désormais new-node. Cela n'a même pas de sens car la variable 'head' contiendra également new_node. Nous avons donc maintenant deux variables pointant vers la même adresse.

Même si, dans tous les cas, ce code était censé dire, new_node = head.prev, cela n'a pas non plus de sens, car head.prev sera nul à ce stade, et new_node pointera alors vers un null.

// Classe pour la DLL de classe publique Double Linked List {Node head; // tête de liste

/* Doubly Linked list Node*/
class Node { 
    int data; 
    Node prev; 
    Node next; 

    // Constructor to create a new node 
    // next and prev is by default initialized as null 
    Node(int d) { data = d; } 
} 
// Adding a node at the front of the list 
public void push(int new_data) 
{ 
/* 1. allocate node  
* 2. put in the data */
    Node new_Node = new Node(new_data); 

/* 3. Make next of new node as head and previous as NULL */
new_Node.next = head; 
new_Node.prev = null; 

/* 4. change prev of head node to new node */
    if (head != null) 
        head.prev = new_Node; 

/* 5. move the head to point to the new node */
    head = new_Node; 
} 

}

Answer 1

L'étape 4 est nécessaire pour connecter prevl'ancienne tête à la nouvelle tête.

Voici la situation après l'étape 3:

Ensuite, après l'étape 4, l' prevancienne tête (qui était nulle) est définie pour pointer vers la nouvelle tête:

Et puis l'étape 5 fait pointer la tête vers le nouveau nœud (la nouvelle tête):

Answer 2

Si head.prev != nullalors headn'est pas le premier élément de la liste. Ceci doit être vérifié comme condition préalable et un IllegalStateExceptiondoit être jeté. Un traitement ultérieur de l'insertion est insensé car le pointeur vers la première position doit être restauré.

Après l'étape 3, la new_nodeconfiguration est terminée et le new_nodeest lié unidirectionnel par new_node.nextà l'ancien premier, maintenant deuxième élément head. Pour terminer le double lien, head.prevdoit être défini sur le nouveau prédécesseur head. C'est ce que fait l'étape 4 si vous omettez le if.

Answer 3

public class DLL {

    private Node head;
    private Node tail;

    public void addFirst(int val) {
        Node node = new Node(val);

        if (head == null)
            tail = node;
        else {
            node.next = head;
            head.prev = node;
        }

        head = node;
    }

    public void addLast(int val) {
        Node node = new Node(val);

        if (tail == null)
            head = node;
        else {
            tail.next = node;
            node.prev = tail;
        }

        tail = node;
    }

    private static final class Node {

        private final int val;
        private Node prev;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}