数据结构-链表

链表一般分为两种：1）单链表  2）双链表，二者是及其相似的，但双链表有两个指针

1.单链表：

//数组模拟链表(快)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N=1e6+10;
using namespace std;
typedef pair<int,int>PII;
//head 表示头节点的下标
//e[i] 表示结点的value
//ne[i] 表示节点i的next指针是多少
//idx 存储当前的已经用到了哪个点 
int head,e[N],ne[N],idx;

//初始化
void init(){
   head=-1;
   idx=0;
}

//将x插到头节点
void add_to_head(int x){
  e[idx]=x;    //3
  ne[idx]=head; //1
  head=idx;    //2
  idx++;       //4
}

//将x插到下标是k的点的后面
void add(int k,int x){
     e[idx]=x;    
     ne[idx]=ne[k];
     ne[k]=idx;
     idx++;
}

//将下标是k的后面的点删去
void remove(int k){
  ne[k]=ne[ne[k]];
}
int main(){
 ios::sync_with_stdio(false);
 
  return 0;
}

2.双链表

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N=1e6+10;
using namespace std;
typedef pair<int,int>PII;
int m;
int e[N],l[N],r[N],idx;

//初始化
void init(){
// 0表示左端点,1表示右端点
 r[0]=1,l[1]=0;
 idx=2;
}

//在下标是k的点的右边，插入x
void add(int k,int x){
  e[idx]=x;
  r[idx]=r[k];
  l[idx]=k;
  l[r[k]]=idx;
  r[k]=idx;
}

//删除第k个点
void remove(int k){
  r[l[k]]=r[k];
  l[r[k]]=l[k];
}
int main(){
 ios::sync_with_stdio(false);
  return 0;
}