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

一、实现方式

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

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