链表

简介 #

链表只能按顺序依次访问元素，而数组支持随机访问.
链表支持在任意位置插入或删除元素，而数组不支持.

链表节点 #

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

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;
}

插入/删除节点 #

如何在 1 和 2 之间插入 3 ？

step 1

step 2

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

void insert(Node *before, int val) { // 在节点 before 后面插入数据为 val 的新节点
    q = new Node(); q->val = val;
    Node *after = before->next;
    after->prev = q, q->next = after;   // Step 1
    before->next = q, q->prev = before; // Step 2
}

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

查找节点 #

Node* indexOf(int val) { // 返回链表中第一个出现的值为 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);
}