C32.【C++ Cont】静态实现双向链表及STL库的list

目录

1.知识回顾

2.静态实现演示图

3.静态实现代码

1.初始双向链表

2.头插

3.遍历链表

4.查找某个值

4.任意位置之后插入元素

 5.任意位置之前插入元素

 6.删除任意位置的元素

4.STL库的list

---

1.知识回顾

96.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删
97.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

上述文章均为动态实现双向链表,由于竞赛中追求运行速度快,因此不会动态实现双向链表,本文介绍静态实现双向链表

2.静态实现演示图

由于每一个结点要存储三个信息,因此静态实现使用三个数组:数值数组val,前驱数组prev,后继数组next,三个数组中同一个下标位置的元素打包成一个节点,如下图所框的(head指向头节点)

注:这里实现的双向链表为不循环的

将上方图改成逻辑结构再画图

3.静态实现代码

1.初始双向链表

	const int N=1e5+10;//一开始prev数组和next数组元素值都为-1(无效下标),为空链表int prev[N]=-1; int val[N];int next[N]=-1;//初始情况head和id都指向哨兵位结点 int head=0;int id=0;

2.头插

先保存新数据的值,再修改next和prev数组

只要①指针最后修改即可

	void push_front(int data){val[++id]=data;next[id]=next[head];prev[next[head]]=id;prev[id]=head;next[head]=id;//确保next[head]最后被修改 }

3.遍历链表

只需要看next数组即可遍历

	void print(){for (int i=next[head];i!=-1;i=next[i]){cout<<val[i]<<" ";}	} 

4.查找某个值

和打印逻辑一样,按链表的方式遍历,注意不能只查val数组,有些元素被"删除"了(即按链表的方式查不到),但仍然存在于val数组中

只需要看next数组,查找到data在链表中第一次出现的位置 ,此方法时间复杂度为

	void find(int data){for (int i=next[head];i!=-1;i=next[i]){if (val[i]==data){cout<<data<<"的下标为"<<i;return; }}cout<<"未找到";}

如果使用标记数组mp优化(哈希表),直接return mp[x],时间复杂度,但此方法有局限

4.任意位置之后插入元素

设在任意位置pos之后插入元素data,本质上和头插操作一样.,只要最后修改pos的后继指针即可

	void insert_after(int pos,int data){val[++id]=data;next[id]=next[pos];prev[next[pos]]=id;prev[id]=pos;next[pos]=id;//确保next[pos]最后被修改 }

 5.任意位置之前插入元素

设在任意位置pos之前插入元素data,本质上和头插操作一样.,只要最后修改pos的前驱指针即可

	void insert_before(int pos,int data){val[++id]=data;next[prev[pos]]=id;prev[id]=prev[pos];next[id]]=pos;prev[pos]=id;//确保prev[pos]最后被修改 }

 6.删除任意位置的元素

修改两个指针即可

	void erase(int pos){prev[next[pos]]=prev[pos];next[prev[pos]]=next[pos];}

4.STL库的list

提醒:list 的底层就是动态实现的双向循环链表,增删会涉及new和delete,执行速度慢,竞赛中不建议使用

初始化list: list<任意数据类型> 名称

list<int> l;

头插: l.push_front 尾插: l.push_back 头删: l.pop_front 尾删: l.pop_back