简介

链表由若干节点前后连接而成。

@LR;
1->2->3->4->5

链表和数组的区别

• 「数组」支持 $O(1)$ 访问任意一个位置的元素（随机访问），而「链表」不支持。
• 「链表」支持在任意位置 $O(1)$ 插入或删除元素，而「数组」不支持。

链表节点

用一个结构体表示链表的节点，其中可以存储任意数据。每个节点有 prev 和 next 两个指针，指向前后相邻的节点。

@LR;
prev [@plain];
val [@big];
next [@plain];
prev -> val [dir=back];
val -> next [dir=forward];

struct Node {
    int val; // 数据（可以是任意类型）
    Node *prev, *next; // 指针
};

初始化

初始化链表时，额外建立两个节点 head 和 tail 代表链表的头尾，把实际节点存储在 head 与 tail 之间，简化链表边界的判断。

Node *head, *tail;

void init() {
    head = new Node();
    tail = new Node();
    head->next = tail;
    tail->prev = next;
}

插入/删除节点

如何在 $u$ 的后面插入 $v$？

@neato;
1[@(-1, 0), @n0]
u[@(0, 0)]
2[@(1, 0), @n0]
3[@(2, 0), @n0]
1 -> u -> 2 -> 3[@both]

建立节点 $v$。

@neato;
v[@(.5, .5)]
1[@(-1, 0), @n0]
u[@(0, 0)]
2[@(1, 0), @n0]
3[@(2, 0), @n0]
1 -> u -> 2 -> 3[@both]

将「$u$ 的后继」的 prev 设置成 $v$，将 $v$ 的 next 设置成 「$u$ 的后继」。

@neato;
v[@(.5, .5)]
1[@(-1, 0), @n0]
u[@(0, 0)]
2[@(1, 0), @n0]
3[@(2, 0), @n0]
v -> 2[@both]
1 -> u[@both]
u -> 2
2 -> 3[@both]

将 $u$ 的 next 设置成 $v$，将 $v$ 的 prev 设置成 $u$。

@neato;
v[@(.5, .5)]
1[@(-1, 0), @n0]
u[@(0, 0)]
2[@(1, 0), @n0]
3[@(2, 0), @n0]
u -> v -> 2[@both]
1 -> u[@both]
2 -> 3[@both]

删除节点运用到类似的方法。

// 在节点 u 后插入数据为 val 的新节点
void insert(Node *u, int val) {
    v = new Node(), v->val = val;           // step 1
    u->next->prev = v, v->next = u->next;   // step 2
    u->next = v, v->prev = u;               // step 3
}

// 删除节点 p
void remove(Node *p) {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
}

查找节点

// 返回链表中第一个出现的值为 val 的节点指针
Node* indexOf(int val) {
    for (Node *p = head->next; p != tail; p = p->next)
        if (p->val == val) return p;
    return NULL;
}

清空链表

void clear() {
    while(head != tail) {
        head = head->next;
        delete head->prev;
    }
    delete tail;
}

使用数组模拟链表

使用指针需要动态分配空间，效率低且不稳定。

使用数组模拟链表是更可靠的做法。

struct Node {
    int val;
    int prev, next;
} node[];

int head, tail, tot;

void init() {
    head = 0, tail = 1, tot = 2;
    node[head].next = tail;
    node[tail].prev = head;
}

void insert(int p, int val) {
    int q = ++ tot; node[q].val = val;
    node[node[p].next].prev = q;
    node[q].next = node[p].next;
    node[p].next = q;
    node[q].next = p;
}

void remove(int p) {
    node[node[p].prev].next = node[p].next;
    node[node[p].next].prev = node[p].prev;
}

int indexOf(int val) {
    for (int p = node[head].next; p != tail; p = node[p].next)
        if (node[p].val == val)
            return p;
    return -1;
}

void clear() {
    head = tail = tot = 0;
    memset(node, 0, sizeof node);
}