数组模拟单链表

由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

单链表的特点：

  1. 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
  2. 单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
     
    对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述：

1
2
3
4
typedef struct LNode{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next; //指针域
}LNode, *LinkList;

但采用上述方法申请新结点，需要用到new Node()函数，这样会浪费大量时间，特别是在曹祖数特别大的情况下，这样，用数组模拟链表可以省去大量时间，且可以完成链表存在的所有操作。

数组模拟方法

数组模拟链表需要用到两个数组value[N]以及next[N]，其中value[N]数组用来保存节点的值；next[N]数组用来保存当前节点所指向节点的数组下标；

同时用head变量记录当前的头节点，idx记录当前可插入的数组下标，见下图所示：

数组示意图

这里主要介绍单链表的三个操作：delete、insert、head_insert，分别对应删除第k次操作后的节点，在第k次操作后的节点后插入x，在头部插入值x。

delete操作

首先说明，如果k为0，则delete操作删除头节点。主要思想为：将删除的节点的上一个节点的next指针指向删除节点的next指针即可。

1
2
3
void delete_(int k){
    ne[k]=ne[ne[k]];
}

这里需要注意，在主程序中首先判断k是否为0，如果为0，则将head指向next(head)即可。

head_insert操作

头插操作，基本思想为：将要插入的节点的next指向当前head节点，随后更新head即可。

1
2
3
4
5
6
void head_(int x){
    v[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

insert操作

插入操作，与头插操作类似，基本思想为：将要插入的节点的next指向当前k的next指向的节点，随后更新next[k]为插入节点即可。

1
2
3
4
5
6
void insert(int k, int x){
    v[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>

using namespace std;
const int N=1e5+10;

int v[N], ne[N], head, idx;
void init(){
    head=-1;
    idx=0;
}
void head_(int x){
    v[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void insert(int k, int x){
    v[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

void delete_(int k){
    ne[k]=ne[ne[k]];
}

int main(){
    init();
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        char a;
        cin>>a;
        if(a=='I'){
            int x, y;
            cin>>x>>y;
            insert(x-1, y);
        }
        else if(a=='D'){
            int x;
            cin>>x;
            if(x==0)head=ne[head];
            delete_(x-1);
        }
        else if(a=='H'){
            int x;
            cin>>x;
            head_(x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])cout<<v[i]<<' ';
    return 0;
}