数据结构 双链表的模拟实现

一、实现方式

依旧采⽤静态实现的⽅式。
双向链表⽆⾮就是在单链表的基础上加上⼀个指向前驱的指针，那就再来⼀个数组，充当指向前驱的指针域即可。

const int N = 1e5 + 10;
int h; // 头结点 
int id; // 下⼀个元素分配的位置 
int e[N]; // 数据域 
int pre[N], ne[N]; // 前后指针域 
// h 默认等于 0，指向的就是哨兵位 
// 此时链表为空，没有任何⼏点，因此 ne[h] = 0

二、头插

// 头插 
void push_front(int x)
{id++;e[id] = x;mp[x] = id; // 存⼀下 x 这个元素的位置 // 左指向哨兵位，右指向哨兵位的下⼀个位置，也就是头结点 pre[id] = h;ne[id] = ne[h];
// 先修改头结点的指针，再修改哨兵位，顺序不能颠倒 pre[ne[h]] = id;ne[h] = id;
}

顺序（方便记忆）：

先把x的两个结点分别指向前一个和后一个。

然后把x后面那个左指针指向x。

最后把x前面的右指针指向x。（必须是最后一步）

三、遍历链表

和单链表遍历的方法一样。

// 打印链表 
void print()
{for(int i = ne[h]; i; i = ne[i]){cout << e[i] << " ";}cout << endl << endl;
}

四、按值查找

直接使⽤mp数组优化了。

// 查找元素 x 在链表中存储的位置 
int find(int x)
{// ⽤ mp 优化 return mp[x];

五、在任意位置之后插⼊元素

// 在存储位置为 p 的元素后⾯，插⼊⼀个元素 x 
void insert_back(int p, int x)
{id++;e[id] = x;mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指向 p，右指向 p 的后继 pre[id] = p;ne[id] = ne[p];// 先让 p 的后继的左指针指向 id // 再让 p 的右指针指向 id pre[ne[p]] = id;ne[p] = id;
}

和头插差不多。

注意思路

六、在任意位置之前插⼊元素

void insert_front(int p, int x)
{id++;e[id] = x;mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指针指向 p 的前驱，右指针指向 p pre[id] = pre[p];ne[id] = p;// 先让 p 的前驱的右指针指向 id // 再让 p 的左指针指向 id ne[pre[p]] = id;pre[p] = id;
}

顺序（方便记忆）：

先把x的左右指针指向p的前驱和p。

然后把p前驱后指针指向id

最后p的前指针指向id。（必须是最后一步）

七、删除任意位置的元素

// 删除下标为 p 的元素 
void erase(int p)
{mp[e[p]] = 0; // 从标记中移除 ne[pre[p]] = ne[p];pre[ne[p]] = pre[p];
}

所有测试代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 创建双链表 
int e[N], ne[N], pre[N], id, h;
int mp[N]; // mp[i] 表⽰：i 这个值存储的位置 
// 遍历链表 
void print()
{for(int i = ne[h]; i; i = ne[i]){cout << e[i] << " ";}cout << endl << endl;
}
// 头插 
void push_front(int x)
{id++;e[id] = x;mp[x] = id;// 先修改新来结点的左右指针 pre[id] = h;ne[id] = ne[h];// 修改哨兵位下⼀个结点的左指针 pre[ne[h]] = id;ne[h] = id;
}
int find(int x)
{return mp[x];
}
// 在任意位置 p 的后⾯插⼊新的元素 x 
void insert_back(int p, int x)
{id++;e[id] = x;mp[x] = id;pre[id] = p;ne[id] = ne[p];pre[ne[p]] = id;ne[p] = id;
}
// 在任意位置 p 的前⾯插⼊新的元素 x 
void insert_front(int p, int x)
{id++;e[id] = x;mp[x] = id;pre[id] = pre[p];ne[id] = p;ne[pre[p]] = id;pre[p] = id;
}
// 删除任意位置 p 的元素 
void erase(int p)
{mp[e[p]] = 0; // 把标记清空 ne[pre[p]] = ne[p];pre[ne[p]] = pre[p];
}
int main()
{for(int i = 1; i <= 5; i++){push_front(i);print();}//cout << find(3) << endl;//cout << find(5) << endl;//cout << find(0) << endl;// insert_front(2, 22);// print();// insert_front(3, 33);// print();// insert_front(4, 44);// print();erase(2);print();erase(4);print();return 0;
}