Блог

Это код, который добавляет узел в начало двусвязного списка. Чего я здесь не понимаю, так это шага 4. Прямо здесь мне кажется, что он сохраняет адрес new_Node в переменной head.prev. Переменная head .теперь в prev будет содержаться новый узел. Это даже не имеет смысла, потому что переменная ‘head’ также будет содержать new_node . Итак, теперь у нас есть две переменные, указывающие на один и тот же адрес.

Даже если, в любом случае, этот код должен был сказать, new_node = head.prev , это также не имеет смысла, потому что head.на этом этапе значение prev будет равно null , а new_node будет указывать на null .

// Class для двусвязного списка общедоступный класс DLL { Node head; // глава списка

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

}

Шаг 4 необходим для подключения prev старого заголовка к новому заголовку.

Это ситуация после шага 3:

Затем после шага 4 prev для старого заголовка (который был нулевым) устанавливается значение, указывающее на новый заголовок:

И затем шаг 5 делает заголовок указывающим на новый узел (новый заголовок):

If head.prev != null then head не является первым элементом списка. Это должно быть проверено как предварительное условие, и IllegalStateException должно быть выбрано. Дальнейшая обработка вставки бессмысленна, поскольку указатель на первую позицию должен быть восстановлен.

После шага 3 new_node настройка завершена, и new_node однонаправленный элемент связан new_node.next с бывшим первым, теперь вторым элементом head . Для завершения двойной ссылки head.prev необходимо установить новый предшественник head . Это то, что делает шаг 4, если вы опускаете if .

 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;
        }
    }
}