链表的种类

💡 打个比方

单链表是单行道：每个路口只写着一个"下一站地址"，只能往前走，想回头只能从起点重走。

双链表是双向街道：每个节点多存一个"上一站地址"（prev），既能往前也能往后，想去哪边都行。

循环链表是地铁环线：最后一站的"下一站"又指回第一站，永远走不到尽头，一圈一圈转。

🖼️ 大图看明白

📏 建双链表，只要 3 步

1. 第 1 步：造节点。新建一个节点，把值存进 val，prev 和 next 先都设为 NULL（还没有邻居）。
2. 第 2 步：尾插接上。把新节点的 prev 指向旧 tail，旧 tail 的 next 指向新节点；然后让 tail 变成新节点。如果这是第一个节点，head 也指向它。
3. 第 3 步：双向遍历。从 head 顺着 next 往前走是正序；从 tail 顺着 prev 往后走是倒序。两个方向都能走到所有节点。

💻 C++ 怎么写

// 双链表节点：值 + 上一站 + 下一站
struct Node {
    int val;
    Node *prev;
    Node *next;
};
Node *head = nullptr, *tail = nullptr;

void tailInsert(int x) {        // 尾插
    Node *p = new Node{x, tail, nullptr};
    if (tail) tail->next = p;   // 旧尾指向新节点
    tail = p;                   // 新节点成为新尾
    if (!head) head = p;        // 第一个节点也是头
}

int main() {
    tailInsert(10); tailInsert(20); tailInsert(30);
    Node *p = head;
    while (p) {                 // 正序遍历
        cout << p->val << " "; p = p->next;
    }
    p = tail;
    while (p) {                 // 倒序遍历
        cout << p->val << " "; p = p->prev;
    }
    return 0;
}

✋ 你来试试