Skip to content

链表

2021-03-06

简介

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

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

链表节点

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

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

初始化

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

cpp
Node *head, *tail;

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

插入/删除节点

如何在 u 的后面插入 v

建立节点 v

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

cpp
// 在节点 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;
}

查找节点

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

清空链表

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

使用数组模拟链表

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

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

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