Java双向链表按照顺序添加节点的方法实例

下面是Java双向链表按照顺序添加节点的方法实例的完整攻略。

1. 创建双向链表节点类和链表类

首先需要定义一个双向链表节点类，和一个双向链表类。代码如下：

public class DLLNode {
    int val;
    DLLNode prev, next;

    public DLLNode(int val, DLLNode prev, DLLNode next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

public class DoublyLinkedList {
    DLLNode head, tail;
    int size;

    public DoublyLinkedList() {
        head = new DLLNode(0, null, null);
        tail = new DLLNode(0, head, null);
        head.next = tail;
        size = 0;
    }
}

以上代码中， DLLNode 类表示链表节点，包含 val、prev 和 next 三个属性，其中 val 表示该节点的数值， prev 表示该节点的前一节点， next 表示该节点的后一节点。 DoublyLinkedList 类表示双向链表，包含 head、tail 和 size 三个属性，其中 head 表示链表头节点， tail 表示链表尾节点， size 表示链表节点数。

2. 实现双向链表节点的添加方法

(1) 在链表末尾添加节点

在双向链表的末尾添加节点是比较简单的，只需要在链表的尾节点前插入新节点即可。代码如下：

public void addNode(int val) {
    DLLNode newNode = new DLLNode(val, tail.prev, tail);
    tail.prev.next = newNode;
    tail.prev = newNode;
    size++;
}

以上代码中， addNode 方法实现了在双向链表的末尾添加节点的操作，首先创建一个新的节点，然后将新节点插入到链表的尾节点前面，最后使得尾节点的 prev 属性指向新节点。

(2) 在链表中按顺序添加节点

在双向链表中按照顺序添加节点需要先判断当前的节点数，然后再遍历链表找到应该插入位置的前一节点，然后将新节点插入到前一节点和前一节点的后一节点之间。代码如下：

public void addNodeInOrder(int val) {
    DLLNode newNode = new DLLNode(val, null, null);
    if (size == 0) {
        newNode.prev = head;
        newNode.next = tail;
        head.next = newNode;
        tail.prev = newNode;
    } else {
        DLLNode cur = head.next;
        while (cur != tail && cur.val < val) {
            cur = cur.next;
        }
        newNode.prev = cur.prev;
        newNode.next = cur;
        cur.prev.next = newNode;
        cur.prev = newNode;
    }
    size++;
}

以上代码中， addNodeInOrder 方法实现了在双向链表中按照顺序添加节点的操作，首先创建一个新的节点，然后判断链表是否为空，如果为空，则将新节点插入到头节点和尾节点之间，否则遍历链表找到应该插入位置的前一节点，然后将新节点插入到前一节点和前一节点的后一节点之间。