动态链表和静态链表

链表实现（动态链表和静态链表）

方式一：链表通常可以使用结构体+指针来实现[动态链表]

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 个插入的数。

动态链表和静态链表

推荐阅读更多精彩内容