双向链表：在前面添加一个节点。来自 geeksforgeeks（java 代码）

Question

这是在双向链表的最前面添加一个节点的代码。我在这里不明白的是第 4 步。就在这里，在我看来它正在将 new_Node 的地址存储到变量 head.prev 中。变量 head.prev 现在将保存新节点。这甚至没有意义，因为变量 'head' 也将保持 new_node。所以现在我们有两个变量指向同一个地址。

即使在任何情况下，这段代码的意思是 new_node = head.prev，那也没有意义，因为 head.prev 此时将为 null点，然后 new_node 将指向一个空值。

// Class 双向链表 public class DLL { 节点头； // 列表头

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

如果 head.prev != null 则 head 不是列表的第一个元素。这应该被检查为 pre-condition，并且应该抛出 IllegalStateException。插入的进一步处理是没有意义的，因为必须恢复指向第一个位置的指针。

在第 3 步之后，new_node 设置完成，new_node 通过 new_node.next 单向链接到前一个元素，现在是第二个元素 head。要使 double-link 完整，必须将 head.prev 设置为新的前任 head。如果您省略 if.

，这就是第 4 步的作用

Answer 2

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

Answer 3

需要第4步将旧头的prev连接到新头

这是第3步后的情况：

然后在第 4 步之后，旧头部（为空）的 prev 被设置为指向新头部：

然后第5步使head指向新节点（新head）：

双向链表：在前面添加一个节点。来自 geeksforgeeks（java 代码）

Doubly linked list: adding a node at front. From geeksforgeeks (java code)

java

doubly-linked-list