线性结构之链表

链表的概念定义：

链表是个逻辑概念，就是指插入和删除时间复杂度均为O(1)的线性表，讲链表就常常和数组对比，说数组插入删除时间复杂度都是O(n)，这里要明确，这里的链表和数组都是逻辑概念，数组就描述的是那种相邻元素之间没有关联的那种线性结构，对于这种如果你要删除某个元素，那只能后面每个元素逐个前移对不对，而链表因为相邻元素之间存在指针，所以断掉链接就可以了。所以要记住链表是逻辑结构，它和数组是逻辑功能上的区别，不是物理实现上的区别，因为链表也可以是静态链表，用数组来实现，所以一般意义上区分链表和数组，是区分逻辑功能，不是区分实现方式。

链表这个逻辑概念再细分，有单链表，双链表，循环链表。链表从实现上分可以分为动态链表和静态链表，静态链表就是依托数组这种物理存储方式去实现链表的逻辑功能。

对于链表，我们一般肯定要实现插入、删除，查找可能是查找第k个结点，第k个插入的结点，值为具体某个值的结点，若要查找第k个插入的结点，那么静态链表自然而然能存储插入顺序，动态链表可以用指针数组来实现。

头尾指针or哨兵结点?

用哨兵结点(gurad)，我们一般实现了插入、删除操作以后，是基于已知某个指针，然后在它左右来插入删除，那么你要头插/尾插/删头/删尾这些涉及到头尾的操作的话你得有头指针和尾指针，如果你删了尾结点那么尾指针还得动对不对，所以gurad的意义就在于此，用头指针和尾指针的话太麻烦，gurad能让你对头尾结点的操作和对普通结点的操作一样样的。

• 哨兵结点，一定要用哨兵结点，单链表用一个，双链表用两个，用了哨兵结点以后头插/尾插/头删/尾删就跟一般删插一样了
• 单链表，哨兵结点作为“第0个插入的结点”
• 单链表插入两步，双链表插入四步
• 单链表删除一步，双链表删除两步

单链表：

静态单链表：

两数组：e[N],ne[N]

两指针: idx,head

#include<iostream>
using namespace std;
const int N =100000;
int e[N],r[N],idx;void init()
{idx=1;//idx=0是哨兵结点for(int i=0;i<=N-1;i++) r[i]=-1;
}void add(int k,int x)//在第 k个插入的数后面插入一个数 x
{e[idx]=x;r[idx]=r[k];r[k]=idx;idx++;
}void del(int k)//删除第 k个插入的数后面的数，k=0代表删除头结点
{r[k]=r[r[k]];
}void show()//输出整个链表
{for(int i=r[0];i!=-1;i=r[i])cout<<e[i]<<" ";puts("");
}int main()
{init();int n;cin>>n;while(n--){string op;cin>>op;if(op=="H"){int x;cin>>x;add(0,x);//头插一个数x}else if(op=="D"){int k;cin>>k;del(k);//删除第 k个插入的数后面的数}else {int k,x;cin>>k>>x;add(k,x);//在第 k个插入的数后面插入一个数 x}}show();return 0;
}

动态单链表：

#include<iostream>
using namespace std;
const int N=100000;
class Node
{public:int data;Node* next;Node(int d,Node* n){this->data=d;this->next=n;}
};Node* arr[N];//指针数组，用来存储结点插入的顺序
int idx=0;void init()
{for(int i=0;i<N;i++) arr[i]=nullptr;arr[0]=new Node(0,nullptr);idx=1;
}void add(int k,int x)
{arr[idx]=new Node(x,arr[k]->next);arr[k]->next=arr[idx];idx++;
}void del(int k)
{arr[k]->next=arr[k]->next->next;    
}void show()
{for(Node* i=arr[0]->next;i!=nullptr;i=i->next){cout<<i->data<<" ";}puts("");
}
int main()
{int M;cin>>M;init();while(M--){string op;cin>>op;if(op=="H") {int x;cin>>x;add(0,x);}else if(op=="D"){int k;cin>>k;del(k);}else{int k,x;cin>>k>>x;add(k,x);}}show();return 0;
}

双链表：

静态双链表:

三数组一指针：

• 使用哨兵结点，那么头哨兵结点下标是0，尾哨兵结点下标是1，那么真正有意义的结点下标是从2开始

#include<iostream>
using namespace std;
const int N =100010;
int M;
int e[N],l[N],r[N],idx;
void init()
{r[0]=1;l[0]=-1;l[1]=0;r[1]=-1;idx=2;
}void add(int k,int x)
{e[idx]=x;l[idx]=k;r[idx]=r[k];l[r[k]]=idx;r[k]=idx;idx++;}
void Del(int k)
{l[r[k]]=l[k];r[l[k]]=r[k];
}
void Show()
{for(int i=r[0];i!=1;i=r[i]){printf("%d ",e[i]);}
}
int main()
{init();string op;int k,x;scanf("%d",&M);while(M--){cin>>op;//     cout<<op<<endl;if(op=="L"){scanf("%d",&x);add(0,x);}else if(op=="R"){scanf("%d",&x);add(l[1],x);}else if(op=="D"){scanf("%d",&k);Del(k+1);}else if(op=="IL"){scanf("%d%d",&k,&x);add(l[k+1],x);}else if(op=="IR"){scanf("%d%d",&k,&x);add(k+1,x);}}//  cout<<"out"<<endl;Show();}

动态双链表

#include<iostream>
using namespace std;
const int N=100010;class Node
{public:int data;Node* left;Node* right;Node(int d,Node* l,Node* r){this->data=d;this->left=l;this->right=r;}
};Node* arr[N];//指针数组，用来存储结点插入的顺序
int idx=0;void init()
{for(int i=0;i<N;i++) arr[i]=nullptr;arr[0]=new Node(0,nullptr,nullptr);arr[1]=new Node(0,nullptr,nullptr);arr[0]->right=arr[1];arr[1]->left=arr[0];idx=2;
}void add(Node* ptr,int x)
{arr[idx]=new Node(x,ptr,ptr->right);ptr->right->left=arr[idx];ptr->right=arr[idx];idx++;
}void del(int k)
{arr[k]->left->right=arr[k]->right;arr[k]->right->left=arr[k]->left;
}void show()
{for(Node* i=arr[0]->right;i!=arr[1];i=i->right){cout<<i->data<<" ";}puts("");
}int main()
{init();int M;cin>>M;while(M--){string op;cin>>op;if(op=="L"){int x;cin>>x;add(arr[0],x);}else if(op=="R"){int x;cin>>x;add(arr[1]->left,x);}   else if(op=="D") {int k;cin>>k;del(k+1);}else if(op=="IL"){int k,x;cin>>k>>x;add(arr[k+1]->left,x);}else {//IRint k,x;cin>>k>>x;add(arr[k+1],x);}}show();return 0;
}