C++ 数组模拟单双向链表实现与优化

时间复杂度：O(1)

2.1.3 遍历链表

// 遍历链表
void print() {
    for (int i = ne[0]; i; i = ne[i]) {
        cout << e[i] << endl;
    }
}

时间复杂度：O(N)

2.1.4 按值查找

策略一：遍历整个链表

int find(int x) {
    for (int i = ne[0]; i; i = ne[i]) {
        if (e[i] == x) return i;
    }
    return 0;
}

时间复杂度：O(N)

策略二：使用哈希表优化

int find(int x) {
    return mp[x];
}

时间复杂度：O(1)

2.1.5 在任意位置之后插入元素

void insert(int p, int x) // 一定要注意，这里的 p 是位置，不是元素
{
    id++;
    e[id] = x;
    ne[id] = ne[p]; // x 指向 p 的后面
    ne[p] = id;     // p 指向 x
}

时间复杂度：O(1)

2.1.6 删除任意位置之后的元素

void erase(int p) {
    if (ne[p]) {
        mp[e[ne[p]]] = 0; // 将 p 后面的元素从 mp 中删除
        ne[p] = ne[ne[p]]; // 指向下一个元素的下一个元素
    }
}

时间复杂度：O(1)

2.1.7 遗留问题

为什么不像顺序表一样，实现一个尾插、尾删、删除任意位置的元素等操作？ 答：能实现，但是没必要。因为时间复杂度是 O(N) 级别的。使用各种数据结构是方便我们去解决问题的，而不是添堵（增加时间复杂度）的。

2.1.8 所有测试代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int h; // 头指针
int id; // 下一个元素分配的位置
int e[N], ne[N]; // 数据域和指针域
int mp[N]; // mp[i] 表示 i 在这个元素存放的位置

// 头插
void push_front(int x) {
    id++;
    e[id] = x;
    ne[id] = ne[h];
    ne[h] = id;
    mp[x] = id;
}

// 遍历链表
void print() {
    for (int i = ne[0]; i; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

// 按值查找
int find(int x) {
    return mp[x];
}

// 在任意位置之后插入元素
void insert(int p, int x) {
    id++;
    e[id] = x;
    ne[id] = ne[p];
    ne[p] = id;
}

// 删除存储位置为 p 后面的元素
void erase(int p) {
    if (ne[p]) {
        mp[e[ne[p]]] = 0;
        ne[p] = ne[ne[p]];
    }
}

int main() {
    for (int i = 1; i <= 5; i++) {
        push_front(i);
        print();
    }
    return 0;
}

运行结果：

2.2 双向链表的模拟实现

2.2.1 实现方式

双向链表无非就是在单链表的基础上加上一个指向前驱的指针，那就再来一个数组充当指向前驱的指针域即可。

2.2.2 定义

const int N = 1e5 + 10;
int h; // 头结点
int id; // 下一个元素分配的位置
int e[N]; // 数据域
int pre[N], ne[N]; // 前后指针域

2.2.3 头插

// 头插
void push_front(int x) {
    id++;
    e[id] = x;
    pre[id] = h;
    ne[id] = ne[h];
    pre[ne[h]] = id;
    ne[h] = id;
}

时间复杂度：O(1)

2.2.4 遍历链表

直接无视 prev 数组，与单链表的遍历方式一致。

void print() {
    for (int i = ne[0]; i; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

时间复杂度：O(N)

2.2.5 按值查找

直接使用哈希表的思想进行优化。

int find(int x) {
    return mp[x];
}

时间复杂度：O(1)

2.2.6 在任意位置之后插入元素

void insert_back(int p, int x) {
    id++;
    e[id] = x;
    pre[id] = p;
    ne[id] = ne[p];
    // 先让 p 的后继的左指针指向 id
    // 再让 p 的右指针指向 id
    pre[ne[p]] = id;
    ne[p] = id;
}

时间复杂度：O(1)

2.2.7 在任意位置之前插入元素

void insert_front(int p, int x) {
    id++;
    e[id] = x;
    pre[id] = pre[p];
    ne[id] = p;
    // 先让 p 的前驱的右指针指向 id
    // 再让 p 的左指针指向 id
    ne[pre[p]] = id;
    pre[p] = id;
}

时间复杂度：O(1)

2.2.8 删除任意位置的元素

void erase(int p) {
    ne[pre[p]] = ne[p];
    pre[ne[p]] = pre[p];
}

时间复杂度：O(1)

2.2.9 所有测试代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int h; // 头结点
int id; // 下一个元素分配的位置
int e[N]; // 数据域
int pre[N], ne[N]; // 前后指针域
int mp[N]; // mp[i] 表示 i 在这个元素存放的位置

// 头插
void push_front(int x) {
    id++;
    e[id] = x;
    pre[id] = h;
    ne[id] = ne[h];
    pre[ne[h]] = id;
    ne[h] = id;
    mp[x] = id;
}

// 遍历链表
void print() {
    for (int i = ne[0]; i; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

// 按值查找
int find(int x) {
    return mp[x];
}

// 在存储位置为 p 的元素后面，插入一个元素 x
void insert_back(int p, int x) {
    id++;
    e[id] = x;
    pre[id] = p;
    ne[id] = ne[p];
    pre[ne[p]] = id;
    ne[p] = id;
}

// 在任意位置之前插入元素
void insert_front(int p, int x) {
    id++;
    e[id] = x;
    pre[id] = pre[p];
    ne[id] = p;
    ne[pre[p]] = id;
    pre[p] = id;
}

// 删除任意位置 p 的元素
void erase(int p) {
    ne[pre[p]] = ne[p];
    pre[ne[p]] = pre[p];
}

int main() {
    for (int i = 1; i <= 8; i++) {
        push_front(i);
        print();
    }
    return 0;
}

运行结果：

2.3 循环链表的模拟实现

回看之前实现的带头单向链表。我们定义 0 表示空指针，但其实哨兵位就在 0 位置，所有的结构正好成环。