萌新学习静态链表的笔记：
静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。
1、静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。
2、动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。
而在算法题中经常使用静态链表而不是动态，因为动态的new使用的时间太长了，
而用数组实现静态链表的操作如下：
先熟悉一下基础知识：
链表的结构：
struct node{int val; //数据域内容(最简单的数据)。数据域int length;//有时候会用长度来计算有多少个节点。 struct node *next；//指向下一个节点。};
静态链表不需要开辟新的节点；
而用数组来实现静态链表，不仅仅可以更好的熟悉链表的内容，还可以用更简
单的方式来表达链表，而虽然简单的结构却五脏俱全。
用代码来实现：
1.初始化：
void init() /*初始化变量*/{head=-1; //头节点指向空节点，所以为-1。idx=0;//存储已经用到了哪个点(index)}
再来与之对应结构体的链表内容：
1.数据域的数据值：e[i];
2.指向下一个节点的地址：ne[i];具体的含义：第i个点的next是多少
接下来就是链表的实现操作了：
2.头结点的插入：
在头节点后插入一个值为x的点
void addh(int x){e[idx]=x;ne[idx]=head;head=idx;idx++;//可以简化成head=idx++;}
插入操作的代码解释：
e[idx]=x; ————将要插入的值赋值；
ne[idx]=head; ————先要进行的操作：将idx（要插入的点）的next指向头节点的下一个节点；
head=idx; ————头节点的next指向idx（插入的点）；
idx++; ————插入点个数加一；
3.普通的插入操作了：
在坐标为k的点后插入一个值为x的点
void add(int k,int x)//插入下标是k这个点的后面{e[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;}
代码解释：
e[idx]=x; ————将要插入的值赋值；
ne[idx]=ne[k]; ————将第idx(要插入的)元素的next指向第k个元素的next；
ne[k]=idx;————将k元素的next指向idx；
idx++; ————插入点个数加一；
4.删除：
void sc (int k) {ne[k]=ne[ne[k]];}
删除在坐标为k的下一个节点,看情况idx要不要变，因为静态链表没有专门计算节点长度的length，如果有那么length–，这里就当他不存在。
代码解释：
将k的next 指向 k的next的next;
代码看过了，接下来就是题目了：
#include<iostream>using namespace std;const int N=10010;int head,idx;int e[N],ne[N];//首先定义几个变量；//1.头节点，head 坐标为-1；void /*初始化变量*/csh(){head=-1;idx=0;//存储已经用到了哪个点？}//*** 2.再就是头节点之后的节点，用e[i]来表示，含义是第i个点的值；//***（1）.ne[i]指的第i个点的next的指针是多少；//***（2）.注意使用坐标来连接两个节点的位置 ex：ne[idx]=head,head=idx;void addh(int x){e[idx]=x;ne[idx]=head;head=idx;idx++;}void add(int k,int x)//插入下标是k这个点的后面{e[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;}void sc (int k) //删除在坐标为k的下一个节点,看情况idx要不要变，因为静态链表没有专门计算节点长度的length，如果有那么length--，这里就当他不存在。{ne[k]=ne[ne[k]];}int main(){int m;cin>>m;csh();while(m--){int k,x;char ch;cin>>ch;if(ch=='H'){cin>>x;addh(x);}else if(ch=='D'){cin>>k;if(!k)head =ne[head];//判断条件不可少注意边界值sc(k-1);}else if(ch=='I'){cin>>k>>x;add(k-1,x);}}for(int i=head;i!=-1;i=ne[i])printf("%d ",e[i]);}
有几个需要注意的点：
在进行链表操作时记得初始化；
第k个输入的元素值为k-1；
双向链表也是一样的：
代码如下：
#include<iostream>using namespace std;const int N=100000;int idx,l[N],r[N],e[N];void csh(){r[0]=1;l[1]=0;idx=2;//已经占用了两个点且不需要头节点。}void add(int k,int x)//在第k个元素后插入一个元素{e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;//与下一步的顺序不可以反；记得从后往前考虑r[k]=idx;}void sc(int k){l[r[k]]=l[k];r[r[k]]=r[k];}int main(){ios::sync_with_stdio(false);cin >> m;csh();while(m--){int k,x;string op;if(op=="R"){cin >> x;add(l[1], x); //! 0和 1 只是代表 头和尾 所以 最右边插入 只要在 指向 1的 那个点的右边插入就可以了}else if(op=="L")//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入{cin >> x;add(0, x);}else if(op=="D"){cin >> k;sc(k + 1);}else if(op=="IL"){cin >> k >> x;add(l[k + 1], x);}else{cin >> k >> x;add(k + 1, x);}}for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';}
交换的时候记得注意顺序即可，最好是从后往前进行交换指向；
