# 4. 双链表

## 概念

**双链表**（Doubly Linked List）是线性表的一种**链式存储**实现，每个结点除了数据域和指向**后继**的指针 `next` 外，还多了一个指向**前驱**的指针 `prior`。这样既能向后遍历，也能向前遍历。

- **逻辑结构**：线性结构（同顺序表、单链表）。
- **存储结构**：链式存储。结点含 `data`、`prior`（前驱指针）、`next`（后继指针）三部分。
- **带头结点**：同单链表，推荐使用头结点统一操作逻辑。头结点的 `prior` 指向 NULL。
- **特点**：
  - 优点：既支持向后也支持向前遍历；给定结点时，**前插 O(1)**（单链表前插需要从头找前驱 O(n)，双链表直接用 `prior`）；删除给定结点也只需 O(1)。
  - 缺点：每个结点多一个指针，存储开销比单链表大；插入/删除时需要修改的指针更多（更易出错）；仍不能随机存取。
- **适用场景**：需要双向遍历、频繁在某结点之前插入、需要高效删除已知结点的场景（如 LRU 缓存的双向链表实现）。

> **与单链表对比**：单链表只能单向、前插需 O(n)；双链表双向、前插 O(1)，代价是每个结点多存一个指针。

## 核心操作

| 操作     | 说明                                           |
| -------- | ---------------------------------------------- |
| 初始化   | 创建头结点，prior 与 next 均置 NULL            |
| 判空     | 头结点 next 是否为 NULL（动态分配，无判满）    |
| 按位查找 | 从头计数，返回第 i 个结点（O(n)）              |
| 后插     | 在结点 p 之后插入新结点（O(1)，仅改 4 个指针） |
| 前插     | 在结点 p 之前插入新结点（O(1)，利用 p->prior） |
| 删除     | 删除给定结点 p（O(1)，直接改前后指针并释放）   |
| 遍历打印 | 正向（next）与反向（prior）两种遍历            |

> 核心技巧：**双链表的插入/删除关键都是「先改前驱的 next 和 后继的 prior」，再修改 p 自身的指针**。注意断开顺序，防止丢失结点。

## 复杂度分析

| 操作            | 时间复杂度 | 空间复杂度 | 原因                                   |
| --------------- | ---------- | ---------- | -------------------------------------- |
| 初始化          | O(1)       | O(1)       | 只创建头结点                           |
| 判空            | O(1)       | O(1)       | 比较头结点指针                         |
| 按位查找        | O(n)       | O(1)       | 不能随机存取，需从头遍历               |
| 给定结点 p 后插 | O(1)       | O(1)       | 只需修改 p、p->next、新结点共 4 个指针 |
| 给定结点 p 前插 | O(1)       | O(1)       | 用 p->prior 直接得到前驱，无需查找     |
| 给定结点 p 删除 | O(1)       | O(1)       | 直接连接 p->prior 与 p->next           |
| 正向 / 反向遍历 | O(n)       | O(1)       | 各扫描一遍                             |

> 相比单链表：双链表把「前插」和「删除已知结点」从 O(n) 降到了 O(1)，这是多存一个 `prior` 指针换来的时间收益。

## 语言实现

### C

```c
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prior;   // 前驱指针
    struct DNode *next;    // 后继指针
} DNode, *DLinkList;

// 初始化：创建带头结点的空双链表
DLinkList initList(void) {
    DLinkList L = (DNode *)malloc(sizeof(DNode));
    if (L == NULL) exit(1);
    L->prior = NULL;
    L->next = NULL;
    return L;
}

int isEmpty(DLinkList L) {
    return L->next == NULL;
}

// 后插：在结点 p 之后插入新结点（O(1)）
void insertAfter(DNode *p, int x) {
    DNode *s = (DNode *)malloc(sizeof(DNode));
    if (s == NULL) exit(1);
    s->data = x;
    s->prior = p;
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;   // 让原后继的前驱指向 s
    p->next = s;
}

// 前插：在结点 p 之前插入新结点（O(1)）
void insertBefore(DNode *p, int x) {
    DNode *s = (DNode *)malloc(sizeof(DNode));
    if (s == NULL) exit(1);
    s->data = x;
    s->prior = p->prior;      // 新结点的前驱 = p 的前驱
    s->next = p;
    if (p->prior != NULL)
        p->prior->next = s;   // 让 p 的原前驱的后继指向 s
    p->prior = s;
}

// 删除结点 p（O(1)），用 e 带回其值；头结点不可删
int deleteNode(DLinkList L, DNode *p, int *e) {
    if (p == L) return 0;            // 不能删头结点
    *e = p->data;
    p->prior->next = p->next;        // 前驱的后继跳过 p
    if (p->next != NULL)
        p->next->prior = p->prior;   // 后继的前驱跳过 p
    free(p);
    return 1;
}

// 按位查找：返回第 i 个结点（i 从 1 开始），无则 NULL
DNode *getNode(DLinkList L, int i) {
    if (i < 1) return NULL;
    DNode *p = L->next;
    int j = 1;
    while (p && j < i) { p = p->next; j++; }
    return p;
}

// 按值查找：返回第一个值为 x 的结点
DNode *locateNode(DLinkList L, int x) {
    DNode *p = L->next;
    while (p && p->data != x) p = p->next;
    return p;
}

// 正向遍历
void printForward(DLinkList L) {
    if (isEmpty(L)) { printf("空链表\n"); return; }
    DNode *p = L->next;
    while (p) {
        printf("%d", p->data);
        if (p->next) printf(" <-> ");
        p = p->next;
    }
    printf("\n");
}

// 反向遍历（利用 prior）
void printBackward(DLinkList L) {
    if (isEmpty(L)) { printf("空链表\n"); return; }
    DNode *p = L->next;
    while (p->next) p = p->next;   // 走到表尾
    while (p != L) {               // 直到头结点
        printf("%d", p->data);
        if (p->prior != L) printf(" <-> ");
        p = p->prior;
    }
    printf(" (反向)\n");
}

int main(void) {
    DLinkList L = initList();
    printf("初始状态: ");
    printForward(L);
    printf("判空=%d\n", isEmpty(L));

    // 后插建立 10 20 30（始终插在末尾之后）
    DNode *tail = L;
    int vals[] = {10, 20, 30};
    for (int i = 0; i < 3; i++) {
        insertAfter(tail, vals[i]);
        tail = tail->next;
    }
    insertAfter(getNode(L, 2), 15);   // 在 20 之后后插 15（后插演示）
    DNode *p = locateNode(L, 20);
    insertBefore(p, 18);              // 在 20 之前前插 18（前插演示）
    printForward(L);
    printBackward(L);

    p = getNode(L, 2);                // 按位查找
    printf("第2个结点值=%d\n", p->data);

    int e;
    p = locateNode(L, 15);            // 删除值为 15 的结点
    if (p && deleteNode(L, p, &e))
        printf("删除元素=%d\n", e);
    printForward(L);

    // 释放所有结点
    DNode *q = L;
    while (q) {
        DNode *t = q->next;
        free(q);
        q = t;
    }
    return 0;
}
```

### C++

```C++
#include <iostream>
using namespace std;

struct DNode {
    int data;
    DNode *prior;
    DNode *next;
    DNode(int d) : data(d), prior(nullptr), next(nullptr) {}
};

class DLinkList {
private:
    DNode *head;   // 头结点

    // 私有：获取表尾结点（用于尾插建立）
    DNode *getTail() const {
        DNode *p = head;
        while (p->next) p = p->next;
        return p;
    }

public:
    DLinkList() { head = new DNode(0); }

    ~DLinkList() {
        DNode *p = head;
        while (p) {
            DNode *t = p->next;
            delete p;
            p = t;
        }
    }

    bool isEmpty() const { return head->next == nullptr; }

    // 尾插：在表尾之后插入（建立用）
    void insertTail(int x) {
        DNode *tail = getTail();
        DNode *s = new DNode(x);
        s->prior = tail;
        tail->next = s;
    }

    // 后插：在给定结点 p 之后插入（O(1)）
    void insertAfter(DNode *p, int x) {
        DNode *s = new DNode(x);
        s->prior = p;
        s->next = p->next;
        if (p->next) p->next->prior = s;
        p->next = s;
    }

    // 前插：在给定结点 p 之前插入（O(1)）
    void insertBefore(DNode *p, int x) {
        DNode *s = new DNode(x);
        s->prior = p->prior;
        s->next = p;
        if (p->prior) p->prior->next = s;
        p->prior = s;
    }

    // 删除给定结点 p（O(1)），返回其值
    int deleteNode(DNode *p) {
        int e = p->data;
        p->prior->next = p->next;
        if (p->next) p->next->prior = p->prior;
        delete p;
        return e;
    }

    DNode *getNode(int i) const {
        if (i < 1) return nullptr;
        DNode *p = head->next;
        int j = 1;
        while (p && j < i) { p = p->next; j++; }
        return p;
    }

    DNode *locateNode(int x) const {
        DNode *p = head->next;
        while (p && p->data != x) p = p->next;
        return p;
    }

    void printForward() const {
        if (isEmpty()) { cout << "空链表" << endl; return; }
        DNode *p = head->next;
        while (p) {
            cout << p->data;
            if (p->next) cout << " <-> ";
            p = p->next;
        }
        cout << endl;
    }

    void printBackward() const {
        if (isEmpty()) { cout << "空链表" << endl; return; }
        DNode *p = head->next;
        while (p->next) p = p->next;
        while (p != head) {
            cout << p->data;
            if (p->prior != head) cout << " <-> ";
            p = p->prior;
        }
        cout << " (反向)" << endl;
    }
};

int main() {
    DLinkList L;
    cout << "初始状态: ";
    L.printForward();
    cout << "判空=" << L.isEmpty() << endl;

    // 尾插建立 10 20 30
    L.insertTail(10);
    L.insertTail(20);
    L.insertTail(30);

    L.insertAfter(L.getNode(2), 15);  // 在 20 之后后插 15
    L.insertBefore(L.locateNode(20), 18);  // 在 20 之前前插 18
    L.printForward();
    L.printBackward();

    DNode *p = L.getNode(2);          // 按位查找
    cout << "第2个结点值=" << p->data << endl;

    p = L.locateNode(15);             // 按值查找并删除
    cout << "删除元素=" << L.deleteNode(p) << endl;
    L.printForward();
    return 0;
}
```

### Java

```java
public class DLinkListDemo {
    // 双链表结点
    static class DNode {
        int data;
        DNode prior;
        DNode next;
        DNode(int d) { data = d; }
    }

    static class DLinkList {
        private final DNode head;   // 头结点

        DLinkList() { head = new DNode(0); }

        boolean isEmpty() { return head.next == null; }

        // 尾插（建立用）
        void insertTail(int x) {
            DNode tail = head;
            while (tail.next != null) tail = tail.next;
            DNode s = new DNode(x);
            s.prior = tail;
            tail.next = s;
        }

        // 后插：在 p 之后插入（O(1)）
        void insertAfter(DNode p, int x) {
            DNode s = new DNode(x);
            s.prior = p;
            s.next = p.next;
            if (p.next != null) p.next.prior = s;
            p.next = s;
        }

        // 前插：在 p 之前插入（O(1)）
        void insertBefore(DNode p, int x) {
            DNode s = new DNode(x);
            s.prior = p.prior;
            s.next = p;
            if (p.prior != null) p.prior.next = s;
            p.prior = s;
        }

        // 删除给定结点 p（O(1)）
        int deleteNode(DNode p) {
            int e = p.data;
            p.prior.next = p.next;
            if (p.next != null) p.next.prior = p.prior;
            return e;
        }

        DNode getNode(int i) {
            if (i < 1) return null;
            DNode p = head.next;
            int j = 1;
            while (p != null && j < i) { p = p.next; j++; }
            return p;
        }

        DNode locateNode(int x) {
            DNode p = head.next;
            while (p != null && p.data != x) p = p.next;
            return p;
        }

        void printForward() {
            if (isEmpty()) { System.out.println("空链表"); return; }
            DNode p = head.next;
            while (p != null) {
                System.out.print(p.data);
                if (p.next != null) System.out.print(" <-> ");
                p = p.next;
            }
            System.out.println();
        }

        void printBackward() {
            if (isEmpty()) { System.out.println("空链表"); return; }
            DNode p = head.next;
            while (p.next != null) p = p.next;
            while (p != head) {
                System.out.print(p.data);
                if (p.prior != head) System.out.print(" <-> ");
                p = p.prior;
            }
            System.out.println(" (反向)");
        }
    }

    public static void main(String[] args) {
        DLinkList L = new DLinkList();
        System.out.print("初始状态: ");
        L.printForward();
        System.out.println("判空=" + L.isEmpty());

        L.insertTail(10);
        L.insertTail(20);
        L.insertTail(30);

        L.insertAfter(L.getNode(2), 15);          // 后插演示
        L.insertBefore(L.locateNode(20), 18);     // 前插演示
        L.printForward();
        L.printBackward();

        DNode p = L.getNode(2);                   // 按位查找
        System.out.println("第2个结点值=" + p.data);

        p = L.locateNode(15);                     // 按值查找并删除
        System.out.println("删除元素=" + L.deleteNode(p));
        L.printForward();
    }
}
```

### Python

```python
class DNode:
    """双链表结点"""

    def __init__(self, data):
        self.data = data
        self.prior = None
        self.next = None


class DLinkList:
    """带头结点的双链表"""

    def __init__(self):
        # 初始化：创建头结点
        self._head = DNode(None)

    def is_empty(self) -> bool:
        return self._head.next is None

    def insert_tail(self, x) -> None:
        """尾插（建立链表用）"""
        tail = self._head
        while tail.next is not None:
            tail = tail.next
        s = DNode(x)
        s.prior = tail
        tail.next = s

    def insert_after(self, p: DNode, x) -> None:
        """后插：在结点 p 之后插入（O(1)）"""
        s = DNode(x)
        s.prior = p
        s.next = p.next
        if p.next is not None:
            p.next.prior = s
        p.next = s

    def insert_before(self, p: DNode, x) -> None:
        """前插：在结点 p 之前插入（O(1)）"""
        s = DNode(x)
        s.prior = p.prior
        s.next = p
        if p.prior is not None:
            p.prior.next = s
        p.prior = s

    def delete_node(self, p: DNode):
        """删除给定结点 p（O(1)），返回其值"""
        e = p.data
        p.prior.next = p.next
        if p.next is not None:
            p.next.prior = p.prior
        return e

    def get_node(self, i: int):
        """按位查找：返回第 i 个结点（i 从 1 开始）"""
        if i < 1:
            return None
        p = self._head.next
        j = 1
        while p is not None and j < i:
            p = p.next
            j += 1
        return p

    def locate_node(self, x):
        """按值查找：返回第一个值为 x 的结点"""
        p = self._head.next
        while p is not None and p.data != x:
            p = p.next
        return p

    def print_forward(self):
        if self.is_empty():
            print("空链表")
            return
        vals = []
        p = self._head.next
        while p is not None:
            vals.append(str(p.data))
            p = p.next
        print(" <-> ".join(vals))

    def print_backward(self):
        if self.is_empty():
            print("空链表")
            return
        vals = []
        p = self._head.next
        while p.next is not None:
            p = p.next          # 走到表尾
        while p is not self._head:
            vals.append(str(p.data))
            p = p.prior
        print(" <-> ".join(vals), "(反向)")


if __name__ == "__main__":
    L = DLinkList()
    print("初始状态:", end=" ")
    L.print_forward()
    print("判空 =", L.is_empty())

    L.insert_tail(10)
    L.insert_tail(20)
    L.insert_tail(30)

    L.insert_after(L.get_node(2), 15)          # 后插演示
    L.insert_before(L.locate_node(20), 18)     # 前插演示
    L.print_forward()
    L.print_backward()

    p = L.get_node(2)                          # 按位查找
    print("第2个结点值 =", p.data)

    p = L.locate_node(15)                      # 按值查找并删除
    print("删除元素 =", L.delete_node(p))
    L.print_forward()
```