Doppelt verknüpfte Liste: Hinzufügen eines Knotens vorne. Von geeksforgeeks (Java-Code)

Question

Dies ist ein Code, der einen Knoten am Anfang der doppelt verknüpften Liste hinzufügt. Was ich hier nicht verstehe, ist Schritt 4. Genau hier scheint es mir, dass die Adresse des neuen Knotens in der Variablen head.prev gespeichert wird. Die Variable head.prev enthält jetzt den neuen Knoten. Dies ist nicht einmal sinnvoll, da die Variable 'head' auch new_node enthält. Jetzt haben wir zwei Variablen, die auf dieselbe Adresse zeigen.

Selbst wenn dieser Code auf jeden Fall new_node = head.prev sagen sollte, ist dies ebenfalls nicht sinnvoll, da head.prev an dieser Stelle null ist und new_node dann auf null zeigt.

// Klasse für doppelt verknüpfte Liste public class DLL {Node head; // Listenkopf

/* 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

Der Schritt 4 wird benötigt, um prevden alten Kopf mit dem neuen Kopf zu verbinden.

Dies ist die Situation nach Schritt 3:

Dann wird nach Schritt 4 der prevalte Kopf (der null war) so eingestellt, dass er auf den neuen Kopf zeigt:

Und dann bringt Schritt 5 den Kopf auf den neuen Knoten (den neuen Kopf):

Answer 2

Wenn head.prev != nulldann headist nicht das erste Element der Liste. Dies sollte als Vorbedingung überprüft und IllegalStateExceptiongeworfen werden. Die weitere Verarbeitung des Einfügens ist sinnlos, da der Zeiger auf die erste Position wiederhergestellt werden muss.

After step 3, the new_node setup is complete, and the new_node is linked unidirectional by new_node.next to the former first, now second element head. To make the double-link complete, head.prev must be set to the new predecessor head. That is what step 4 does if you omit the 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;
        }
    }
}