双向链表，顾名思义和单向链表很相似，均为链表，两者之间的操作也十分相近，最明显的不同之处就是双向链表的单个结点带有两个指针域，分别指向前后两个元素。

1. 基本框架的构建

节点的结构如图：

在双向链表中，每个节点不仅需要知道其下一个节点的位置（通过next指针），还需要知道其前一个节点的位置（通过prev指针）。这样的结构允许双向遍历：既可以从链表的头部向尾部遍历，也可以从尾部向头部遍历。

// 实现双向链表的节点作为静态内部类
static class ListNode {
    public int val; // 节点存储的数据

    // 定义指向前一个节点和后一个节点的指针
    public ListNode next; // 指向下一个节点的指针
    public ListNode prev; // 指向前一个节点的指针

    // 构造函数，用于创建一个新的节点并初始化其值
    public ListNode(int val) {
        this.val = val; // 设置节点存储的数据
        // 默认情况下，前后指针都为空，表示没有连接到其他节点
        this.next = null; // 初始化时，下一个节点指针为空
        this.prev = null; // 初始化时，前一个节点指针为空
    }
}

实现逻辑

1. 节点数据：val属性存储节点所包含的数据，这是节点的主要内容。
2. 双向指针：
   • next属性是指向链表中下一个节点的指针，如果当前节点是链表的最后一个节点，则next为null。
   • prev属性是指向链表中上一个节点的指针，如果当前节点是链表的第一个节点，则prev为null。
3. 构造函数：通过构造函数创建节点时，需要传入节点存储的数据val。构造函数还负责初始化next和prev指针为null，表示节点尚未连接到链表中的其他节点。

2. 打印链表

• display方法用于打印双向链表中的所有节点值。它从链表的头部开始，遍历整个链表，逐个输出每个节点存储的数据，直到链表结束。

• 遍历链表：使用while循环遍历链表，循环的条件是cur不等于null。这保证了只要cur指向一个有效的节点，循环就会继续执行。

// 打印链表中的所有节点值
public void display() {
    ListNode cur = head; // 从链表的头节点开始遍历
    while (cur != null) { // 循环遍历链表直到当前节点为null，表示链表结束
        System.out.print(cur.val + " "); // 打印当前节点存储的数据
        cur = cur.next; // 移动到链表中的下一个节点
    }
}

3. 查找链表长度

size方法用于计算并返回双向链表的长度，即链表中节点的数量。它通过遍历链表，对遍历过程中遇到的每个节点进行计数来实现。

// 计算并返回链表的长度
public int size() {
    int count = 0; // 初始化计数器为0
    ListNode cur = head; // 使用cur指针从链表的头节点开始遍历链表
    while (cur != null) { // 当cur指针不为null，即还没有遍历完整个链表时，继续遍历
        count++; // 对于每个遍历到的节点，计数器增加1
        cur = cur.next; // 将cur指针移动到下一个节点，继续遍历
    }
    return count; // 遍历结束后，返回计数器的值，即链表的长度
}

4. 头插法

addFirst方法用于在双向链表的头部插入一个新的节点。这种头插法需要考虑两种情况：链表为空时和链表已包含元素时。

// 在双向链表头部添加新节点
public void addFirst(int data) {
    // 申请一个新的节点，并初始化其数据为传入的data
    ListNode node = new ListNode(data);
    
    // 当链表为空时（即head为null）
    if(head == null) {
        // 直接将新节点设为头节点和尾节点，因为此时链表中只有一个节点
        head = node;
        tail = node; // 这里设置尾节点是双向链表特有的操作
    } else {
        // 当链表中已存在元素时
        // 将当前头节点的前指针指向新节点
        head.prev = node;
        // 将新节点的下一个节点指针指向原头节点
        node.next = head;
        // 更新头节点为新节点
        head = node;
    }
}

实现逻辑：

1. 创建新节点：首先，为待插入的数据data创建一个新的ListNode节点。
2. 链表为空的处理：如果链表当前为空（即head为null），将新节点同时设置为链表的头节点和尾节点。这是因为插入操作后，链表中只有这一个节点。
3. 链表非空的处理：
   • 设置当前头节点head的前指针prev指向新节点，建立从原头节点到新节点的反向链接。
   • 设置新节点的下一个节点指针next指向原头节点，建立从新节点到原头节点的正向链接。
   • 更新head为新节点，因为新节点现在成为了链表的头部。

链表包含元素时图示如下：

​

5. 尾插法

addLast方法用于在双向链表的尾部添加一个新的节点。这种尾插法同样需要考虑两种情况：当链表为空时和当链表中已存在元素时。

// 在双向链表尾部添加新节点
public void addLast(int data) {
    // 创建新节点，初始化其数据为传入的data
    ListNode node = new ListNode(data);
    
    // 当链表为空时（即head为null）
    if(head == null) {
        // 直接将新节点设为头节点和尾节点，因为此时链表中只有这一个节点
        head = node;
        tail = node;
    } else {
        // 当链表中已存在元素时
        // 设置当前尾节点的下一个节点指针指向新节点
        tail.next = node;
        // 设置新节点的前一个节点指针指向当前尾节点
        node.prev = tail;
        // 更新尾节点为新节点
        tail = node;
    }
}

实现逻辑：

1. 创建新节点：基于给定的数据data创建一个新的ListNode节点。
2. 链表为空的处理：如果链表当前为空（即head为null），则将新节点同时设置为链表的头节点和尾节点。这个操作确保了链表从空状态到有一个节点的正确转变。
3. 链表非空的处理：
   • 设置当前尾节点tail的下一个节点指针next指向新节点，建立从原尾节点到新节点的正向链接。
   • 设置新节点的前一个节点指针prev指向当前尾节点，建立从新节点到原尾节点的反向链接。
   • 更新tail为新节点，因为新节点现在成为了链表的尾部。

当链表中已存在元素时图示如下：

​

6. 任意位置插入

addIndex方法用于在双向链表的任意有效位置插入一个新的节点。这个方法处理了几个关键情况：检查索引的合法性、头部插入、尾部插入，以及一般位置的插入。

// 在双向链表的指定index位置插入新节点
public void addIndex(int index, int data) {
    // 创建新节点
    ListNode node = new ListNode(data);
    // 1.判断index的合法性
    if(index < 0 || index > size()) {
        System.out.println("index不合法");
        // 抛出自定义的异常
        throw new IndexWrongFulException("index不合法");
    }
    // 2.头插法处理
    if(index == 0) {
        addFirst(data);
        return;
    }
    // 2.尾插法处理
    if(index == size()) {
        addLast(data);
        return;
    }
    // 3.一般位置的插入
    // 找到要插入位置的节点
    ListNode cur = find(index);
    // 进行节点的插入操作
    cur.prev.next = node;
    node.next = cur;
    node.prev = cur.prev;
    cur.prev = node;
}

实现逻辑：

1. 创建新节点：基于给定的数据data创建一个新的ListNode节点。
2. 索引合法性检查：确保传入的index在0（包括头部）和链表长度（包括尾部）之间。如果index不合法，抛出自定义的IndexWrongFulException异常。
3. 头部和尾部插入处理：如果index为0，调用addFirst实现头插法；如果index等于链表的长度，调用addLast实现尾插法。
4. 一般位置的插入：
   • 使用find方法找到要插入位置的当前节点cur。
   • 将新节点node插入到cur节点前面：设置node的next指向cur，node的prev指向cur的prev，然后调整cur.prev的next和cur的prev以正确链接新节点。

辅助方法：

1.自定义异常类IndexWrongFulException用于处理索引不合法的情况，提高代码的健壮性。

public class IndexWrongFulException extends RuntimeException{
    public IndexWrongFulException(String message) {
        super(message);
    }
}

2.find(int index)：通过遍历链表来找到指定索引位置的节点。从头节点head开始，沿着链表向前移动index次。

private ListNode find(int index){
    ListNode cur = head;
    while(index != 0){
        cur = cur.next;
        index--;
    }
    return cur;
}

详细分析： 这里主要分析一般情况下在链表中间插入的情况

注：紫色数字为指针顺序。

7. 查找是否存在关键词key

contains方法用于在双向链表中查找是否存在值等于key的节点。此方法通过遍历链表并逐一比较节点值来实现

// 在双向链表中查找是否存在值为key的节点
public boolean contains(int key) {
    ListNode cur = head; // 从头节点开始遍历链表
    while (cur != null) { // 循环遍历直到链表末尾
        if (cur.val == key) { // 如果找到一个节点的值等于key
            return true; // 返回true，表示链表中存在值为key的节点
        }
        cur = cur.next; // 移动到下一个节点继续查找
    }
    return false; // 遍历结束，如果没有找到值为key的节点，则返回false
}

8. 删除第一次出现的关键词key

remove方法用于从双向链表中删除第一次出现的值等于key的节点。这个方法处理了几个关键情况：删除头节点、删除尾节点，以及删除链表中间的节点。

// 从双向链表中删除第一次出现的值为key的节点
public void remove(int key) {
    ListNode cur = head; // 从头节点开始遍历链表
    while (cur != null) { // 遍历链表直到末尾
        if (cur.val == key) { // 找到第一个值等于key的节点
            if (cur == head) { // 特殊情况：要删除的节点是头节点
                head = head.next; // 将头节点指向下一个节点
                if (head != null) { // 如果新的头节点不为null，清除其prev指向
                    head.prev = null;
                } else { // 如果新的头节点为null，说明链表变空了，尾节点也应该置为null
                    tail = null;
                }
            } else { // 一般情况：要删除的节点在链表中间或尾部
                cur.prev.next = cur.next; // 跳过当前节点，从而删除它
                if (cur.next != null) { // 如果当前节点不是尾节点，更新其后节点的prev指向
                    cur.next.prev = cur.prev;
                } else { // 如果当前节点是尾节点，更新尾节点为当前节点的前一个节点
                    tail = cur.prev;
                }
            }
            return; // 删除完成，退出方法
        }
        cur = cur.next; // 移动到下一个节点继续查找
    }
}

实现逻辑：

1. 遍历链表查找key：从头节点开始遍历整个链表，寻找第一个节点值等于key的节点。
2. 删除头节点：如果要删除的节点是头节点，则将头节点更新为它的下一个节点。特别注意，如果新的头节点非空，需要清除它的prev指针；如果链表只有一个节点被删除后变为空，则同时更新tail为null。
3. 删除中间或尾节点：对于链表中间或尾部的节点，首先通过cur.prev.next = cur.next跳过当前节点实现删除。然后，如果被删除节点不是尾节点，还需更新其后节点的prev指向。如果被删除节点是尾节点，则更新tail指向当前节点的前一个节点。

1.删除头节点图示​

2.删除中间节点图示

3.删除尾部结点图示

9. 删除所有关键词key

此版本的remove方法用于删除双向链表中所有值等于key的节点。与删除单个key的区别在于，此处不在找到第一个匹配节点后立即返回，而是继续遍历整个链表，删除所有符合条件的节点。

// 从双向链表中删除所有值为key的节点
public void remove(int key) {
    ListNode cur = head; // 从头节点开始遍历链表
    while (cur != null) { // 遍历整个链表
        if (cur.val == key) { // 找到值等于key的节点
            if (cur == head) { // 如果要删除的节点是头节点
                head = head.next; // 更新头节点
                if (head != null) { // 如果新的头节点非空，清除其前向指针
                    head.prev = null;
                } else { // 如果新的头节点为空，说明链表已空，尾节点也需更新为null
                    tail = null;
                }
            } else { // 删除链表中间或尾部的节点
                cur.prev.next = cur.next; // 跳过当前节点
                if (cur.next != null) { // 如果不是尾节点，更新后续节点的前向指针
                    cur.next.prev = cur.prev;
                } else { // 如果是尾节点，更新尾节点为前一节点
                    tail = cur.prev;
                }
            }
            // 注意：与删除单个key不同，这里没有return，继续遍历删除所有key
        }
        cur = cur.next; // 移动到下一个节点继续检查
    }
}

实现逻辑：

1. 遍历整个链表：从头节点开始，逐个检查每个节点的值是否等于key。
2. 删除头节点的特殊处理：如果待删除节点是头节点，更新头节点为其下一个节点。如果更新后头节点非空，清除新头节点的prev指针。如果链表变空（即新头节点也为空），则尾节点也设置为null。
3. 删除中间节点或尾节点：对于链表中的其他节点，通过调整前后节点的指针来删除当前节点。特别地，如果删除的是尾节点，需要更新尾节点为当前节点的前一个节点。
4. 继续遍历：与删除单个key的方法不同，此方法在找到并处理一个匹配节点后不立即返回，而是继续遍历链表，直到链表末尾，以确保删除所有值为key的节点。

10. 清空链表

clear方法用于清空双向链表，即删除链表中的所有节点，使链表变成一个空链表。与单向链表相比，双向链表的节点不仅有next指针指向下一个节点，还有prev指针指向前一个节点。因此，在清空双向链表时，需要确保每个节点的next和prev指针都被设置为null，以断开所有节点间的连接，这有助于垃圾收集器回收这些节点占用的内存

// 清空双向链表
public void clear() {
    ListNode cur = head; // 从头节点开始遍历链表
    while (cur != null) { // 遍历整个链表
        ListNode curNext = cur.next; // 临时保存当前节点的下一个节点
        // 将当前节点的前后指针都置为null，断开与其他节点的连接
        cur.next = null;
        cur.prev = null;
        // 继续遍历链表的下一个节点
        cur = curNext;
    }
    // 遍历结束后，将头尾节点指针也置为null，表示链表已完全清空
    head = null;
    tail = null;
}