- 链表实现（动态链表和静态链表）
方式一：链表通常可以使用结构体+指针来实现[动态链表]
struct Node{
int val;
Node* next;
}// 结构体+指针的实现方式
new Node(); // 慢！
这是第一种实现方式，但是这种方式有一些弊端，比如链表添加节点需要new一个新的Node，new是非常慢的过程，还消耗内存资源。算法题中链表的大小一般是100万级别，单单new出100万个节点就已经会超时了。
方式二：数组模拟链表[静态链表] 每一个节点提前准备好，没有指针的语言中可以使用
好处：快！而且普通链表的功能比如排序也都有，就是实现起来麻烦一点~。
特点：链表的实现也是可以不借助指针的。
-
数组模拟单链表
邻接表是一堆单链表
应用：使用邻接表的方式存储树和图 ；或者说，使用本质是数组的链表来模拟树和图，大型数据结构也是由基本数据结构构成的。
单链表—>邻接表—>树和图数组模拟单链表本质上是使用两个数组，通过下标关联即可
int val[N]; int next[N];image-20220211165447012// 静态链表操作轮子 #include <iostream> const int N = 10e5+10; int ne[N],val[N],head,idx; int m; using namespace std; void init(){ head = -1; idx = 0; } void add_head(int x){ val[idx] = x; ne[idx] = head; head = idx; idx++; // idx为新诞生节点的序号 } // 删除下标（idx）是k的后面的节点 void del(int k){ ne[k] = ne[ne[k]]; } // 将x插入到下标为k的点的后面 void add(int x,int k){ val[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx++; } int main(){ cin >> m; while(m--){ char c; cin >> c; if(c == 'H'){ int x; cin >> x; add_head(x); }else if(c == 'D'){ int k; cin >> k; del(k-1); }else if(c == 'I'){ int x,k; cin >> x >> k; add(x,k-1); } } for(int i = head;i != -1;i = ne[i]){ cout << val[i] << " "; } return 0; }
-
数组模拟双向链表
应用：优化某些问题。
和单链表类似，每一个节点都有两个指针
#include <iostream> using namespace std; const int N = 10e5+10; int l[N],r[N],val[N]; // 当然也可以使用结构体来模拟，但是发现使用数组模拟的话代码比较简单 struct Node{ int l,r,val; }node[N]; // 初始化 void init(){ r[0] = 1,l[1] = 0; // 0号点的右边是1号点，1号点的左边是0号点 默认0号点是头结点，1号点是尾结点 idx = 2; } // 插入操作 分为向左插入和向右插入 // 向右插入编号是idx的节点 void add_r(int k,int x){ // 向编号是k的节点右端添加值为x的节点 // 新的节点编号是上一次++之后未曾使用的数字 r[idx] = r[k]; l[idx] = k; l[r[idx]] = idx; r[k] = idx; idx++; // 插完之后记得idx自增一个 } // 在k的左边插入一个新的数，其实不用重新写，就是在k-1的右边重新插入一个数x 妙！！！ void add_l(int k,int x){ add_r(k-1,x); } // 删除第k个点 void remove(){ r[l[k]] = r[k]; l[r[k]] = l[k]; } int main(){ return 0; }
单链表往往需要head来指向第一个节点；但是双链表不需要head，而是直接使用两个数(0,1)来表示初始左右节点，但是这两个节点里面没有值，注意idx需要从2开始。
Acwing: 双链表
实现一个双链表，双链表初始为空，支持 5 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10e5+10;
int m;
// 依然是默认的静态链表
int l[N],r[N],e[N],idx;
int k,x;
void init(){
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;
idx++;
}
void remove(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(){
cin >> m;
string op;
init();
while(m--){
cin >> op;
if(op == "L"){
cin >> x;
add(0,x); // 这样做的双链表的前后两端一定是0和1
}else if(op == "R"){
cin >> x;
add(l[1],x);
}else if(op == "D"){
cin >> k;
remove(k+1); // 第k个插入的数应该要从k+1删除 k=1时，则idx=2
}else if(op == "IL"){
cin >> k >> x;
add(l[k+1],x);
}else if(op == "IR"){
cin >> k >> x;
add(k+1 , x);
}
}
for(int i = r[0];i!=1;i = r[i]) { cout << e[i] << " "; }
return 0;
}
实现一个双链表，双链表初始为空，支持 5 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
