链表和 list

一、单链表的模拟实现

1.实现方式

链表的实现方式分为动态实现和静态实现两种。

动态实现是通过 new 申请结点，然后通过 delete 释放结点的形式构造链表。这种实现方式最能体

现链表的特性；

静态实现是利用两个数组配合来模拟链表。一个表示数据域，另一个表示指针域，它的运行速度很快。下面演示的也都是单链表的静态实现。

2.定义 - 创建 - 初始化

两个足够大的数组，elem数组（e）用来存数据，next数组（ne）用来存下一个结点的位置；变量 h ，充当头指针，表示头结点的位置；变量 id ，为新来的结点分位置。

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

3.头插

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

4.遍历链表

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

5.按值查找

int mp[N]; // mp[i] 表示 i 在这个元素存放的位置
//push_front的时候,mp[x] = id; // x 这个元素存放的位置是 id
//按值查找
int find(int x)
{//策略一int i;for(i=ne[h];i;i=ne[i]){if(e[i]==x)return i;	}return 0;//策略二return mp[x];
}

第一种方式就是遍历链表，如果存储的值数据范围不大，就可以用哈希表优化，就是第二种方式。当然第二种方式是有局限性的，一是存的数据过大会导致崩溃，二是不能存在相同的数据，否则这个数组中的部分数据会进行刷新。

6.在任意位置之后插入元素

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

7.删除任意位置之后的元素

//删除任意位置之后的元素
void erase(int p)
{if(ne[p]){mp[e[ne[p]]]=0;ne[p]=ne[ne[p]];}
}

在单链表的模拟实现中，我们可以发现虽然一个节点是由其数据域和指针域组成的，但真正代表该节点信息的是数据域和下标，指针域只是为了连接下一个节点的工具（其实就是下一个节点的下标，本质上是属于下一个节点的）。有了这个工具我们就能通过elem数组找到下一个节点的数据域，也能通过next数组找到下一个节点的指针域。以上就是单链表的内容了。那我们为什么不像顺序表一样，实现一个尾插、尾删、删除任意位置的元素等操作呢？ 其实是能实现，但是没必要。因为时间复杂度是 O ( N ) 级别的。

二、双向链表的模拟实现

1.实现方式

依旧采用静态实现的方式。双向链表无非就是在单链表的基础上加上一个指向前驱的指针，那就再来一个数组，充当指向前驱的指针域即可。

2.定义

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

3.头插

//头插
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;
} 

4.遍历链表

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

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

5.按值查找

不考虑特殊情况，直接使用 mp 数组优化了。

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

6.在任意位置之后插入元素

//在任意位置之后插入元素
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;
}

7.在任意位置之前插入元素

//在任意位置之前插入元素
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;
}

8.删除任意位置的元素

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

我们可以看出，双向链表只是在单链表的基础上加了pre这个前驱指针数组，本质和单链表无异，就是清楚指针域之间的关系。

三、循环链表的模拟实现

回看之前实现的带头单向链表。我们定义0表示空指针，但其实哨兵位就在0位置，所有的结构正好成环。因此循环链表就是在原有的基础上，让最后一个元素指向表头即可。在这里就用一道算法题来说明循环链表。

因为报数一直绕着圈进行，所以我们可以使用循环链表。操作的次数比较明显，因为要使所有人出圈，所有要操作总人数的次数，也就是n。在进行每一步操作时，要数m个人，但是如果数到第m个的话，我们改变其前面元素的指针域就会很困难了，所以我们可以数m-1次，再使用指针域找到第m个人的信息。

#include <iostream>
using namespace std;
const int N=110;
int ne[N]; 
int main() 
{int n,m;cin >> n >> m;for(int i=1;i<n;i++){ne[i]=i+1;}ne[n]=1;int t=n;for(int i=1;i<=n;i++){for(int j=0;j<m-1;j++){t=ne[t];}cout << ne[t] << " ";ne[t]=ne[ne[t]];}return 0;
}

四、动态链表 - list

STL 里面的 list 的底层就是动态实现的双向循环链表，增删会涉及 new 和 delete，因为new 和 delete 是非常耗时的操作，效率不高，在竞赛中一般不会使用。因为和vector都是STL的容器，使用操作也差不多，只要正常使用接口就能实现。

1. 创建 list

list<int> lt;

2.push_front / push_back

push_front ：头插；push_back ：尾插。

 // 尾插lt.push_back(i);// 头插lt.push_front(i);

3. pop_front / pop_back

pop_front ：头删；pop_back ：尾删

 // 头删lt.pop_front();// 尾删lt.pop_back();