线性表——双链表

在Java中，双链表（Doubly Linked List）是一种常见的数据结构，它允许从两端进行元素的插入和删除操作。

与单链表相比，双链表的每个节点除了存储数据本身外，还包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。这使得双链表在遍历、插入和删除操作上更加灵活。

双链表提供了比单链表更灵活的操作，特别是在需要频繁地在链表两端进行插入和删除操作时。然而，由于每个节点都需要额外的空间来存储前驱节点的指针，因此双链表在内存使用上会比单链表稍多一些。

1. 节点（Node）的定义（双链表）

在双链表中，每个节点（Node）除了包含存储的数据外，还包含两个引用（或指针）：一个指向前一个节点的prev，另一个指向后一个节点的next。这样的设计使得从任一节点都可以向前或向后遍历链表。

class Node<T> {  
    T data; // 存储的数据  
    Node<T> prev; // 指向前一个节点的指针  
    Node<T> next; // 指向后一个节点的指针  
  
    // 构造函数  
    public Node(T data) {  
        this.data = data;  
        this.prev = null;  
        this.next = null;  
    }  
}

2. 双链表的定义

双链表是一种由节点组成的链表，其中每个节点都包含三个部分：数据域、指向前一个节点的指针和指向后一个节点的指针。双链表可以从两端开始遍历，支持在链表的两端快速地进行插入和删除操作。

class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) { val = x; }
}

DoublyListNode createDoublyLinkedList(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    DoublyListNode head = new DoublyListNode(arr[0]);
    DoublyListNode cur = head;
    // for 循环迭代创建双链表
    for (int i = 1; i < arr.length; i++) {
        DoublyListNode newNode = new DoublyListNode(arr[i]);
        cur.next = newNode;
        newNode.prev = cur;
        cur = cur.next;
    }
    return head;
}

// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 从头遍历双链表
for (DoublyListNode p = head; p != null; p = p.next) {
    System.out.println(p.val);
}

// 从尾遍历双链表（假设我们有尾节点的引用 tail）
for (DoublyListNode p = tail; p != null; p = p.prev) {
    System.out.println(p.val);
}


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 在双链表头部插入新节点 0
DoublyListNode newHead = new DoublyListNode(0);
newHead.next = head;
head.prev = newHead;
head = newHead;
// 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

DoublyListNode tail = head;
// 先走到链表的最后一个节点
while (tail.next != null) {
    tail = tail.next;
}

// 在双链表尾部插入新节点 6
DoublyListNode newNode = new DoublyListNode(6);
tail.next = newNode;
newNode.prev = tail;
// 更新尾节点引用
tail = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 在第 3 个节点后面插入新节点 66
// 找到第 3 个节点
DoublyListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// 组装新节点
DoublyListNode newNode = new DoublyListNode(66);
newNode.next = p.next;
newNode.prev = p;

// 插入新节点
p.next.prev = newNode;
p.next = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除第 4 个节点
// 先找到第 3 个节点
DoublyListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// 现在 p 指向第 3 个节点，我们它后面那个节点摘除出去
DoublyListNode toDelete = p.next;

// 把 toDelete 从链表中摘除
p.next = toDelete.next;
toDelete.next.prev = p;

// 把 toDelete 的前后指针都置为 null 是个好习惯（可选）
toDelete.next = null;
toDelete.prev = null;

// 现在链表变成了 1 -> 2 -> 3 -> 5


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除头结点
DoublyListNode toDelete = head;
head = head.next;
head.prev = null;

// 清理已删除节点的指针
toDelete.next = null;

// 现在链表变成了 2 -> 3 -> 4 -> 5


// 创建一条双链表
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除尾节点
DoublyListNode p = head;
// 找到尾结点
while (p.next != null) {
    p = p.next;
}

// 现在 p 指向尾节点
// 把尾节点从链表中摘除
p.prev.next = null;

// 把被删结点的指针都断开是个好习惯（可选）
p.prev = null;

// 现在链表变成了 1 -> 2 -> 3 -> 4

3. 双链表的基本操作

• 添加（Append）：在链表末尾添加一个新节点。
• 添加至头部（Prepend）：在链表头部添加一个新节点。
• 删除：删除链表中的指定节点。
• 查找：根据数据查找链表中的节点。
• 遍历：从头节点或尾节点开始遍历整个链表。
• 反转：将链表中的节点顺序反转。

4. 优点和缺点

优点：

1. 灵活性：可以从链表的两端进行插入和删除操作，这使得双链表在某些应用场景下（如队列和栈的混合操作）非常有用。
2. 双向遍历：由于每个节点都包含指向前一个节点的指针，因此可以方便地向前遍历链表，这在某些算法中非常有用。
3. 空间效率：与数组相比，双链表在插入和删除节点时不需要移动其他元素，因此具有更好的空间效率。

缺点：

1. 内存使用：每个节点都需要额外的空间来存储指向前一个节点的指针，这增加了内存的消耗。
2. 缓存效率：由于链表中的节点在内存中通常不是连续存储的，这可能导致较差的缓存效率，尤其是在遍历链表时。
3. 查找效率：与数组相比，链表的查找效率较低，因为需要从头节点开始逐个遍历节点。尽管双链表提供了双向遍历的能力，但这并不改变其查找效率的基本性质。