数据结构--单链表

前言：我们都知道链表的一般模式是由结构体加指针来实现的，但是在实际的比赛中，结构体指针来实现链表的操作并不常用，原因是因为我们在增加节点时需要开辟新的内存，而比赛时给出的样例大多都是十几万个数据，就只是c++的new就要消耗很大一部分时间，我们知道比赛一般往往更倾向于时间复杂度更优的算法，很多的算法也都是基于此目的而衍生和创建出来的，今天我们就来学习如何利用数组在比赛中快速模拟实现链表的操作。

何为链表

首先要理解什么是链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表和数组的区别：采用顺序存储结构时称为为数组，采用链式存储结构时称为为链表。但二者同为线性表。 简单的说： 数组通过下标将每一个元素值联系在一起，并且用一组地址连续的存储单元（物理位置相邻）来存储表中的元素值 链表通过指针把每一个元素的值联系在一起，不要求逻辑上（链表逻辑）相邻的两个元素在物理位置上也相邻，那么就需要链表元素需要两个数据，一个是储存该元素的值，一个是储存链表下一个元素的地址，两者统称为一个节点，接下来每一个元素都用对应的节点表示，阐明两个存储数据

下面这张图是单链表的结构，其中红色代表元素值，蓝色代表下一个元素地址,每次遍历都是从下一个元素的地址指向下一个元素

单链表的构成

只能从左往右一条指针遍历的链表

这里我们用数组模拟单链表更好的理解

1.数组实现的相关要求和原理

我们期望利用数组来帮助我们实现链表，链表的一些基本功能就一定要满足，比如单链表的增删查改操作等，下面我们就来用问题引出方法:

1.1 链接关系和权值该怎么表示？

在结构体模式的链表中，我们通过next指针来实现链表的”链接“功能，而在数组中，我们可以尝试建立两个数组，用来分别存储点的权值和该点的下一个节点，我们这里以e[i]和ne[i]来命名，我们可以在e[i]中保存我们点对应的值，而在ne[i]中存储i节点的下一个节点下标，为了方便，我们以数组的下标来唯一标识节点位置，注意我们的下标表示的是该节点插入链表的顺序，这样我们就可以在ne[i]中保存数组的下标，从而达到链接的目的。

const int N = 1e6+10; int e[N],ne[N];

让我们来思考一个问题，如果当链表为空怎么办呢？说明链表里面没有元素，所以我们规定链表两端还有不会变的一个头节点和一个空节点,头节点本身没有数值，但是它会指向下一个元素的地址,当链表为空时指向空节点地址（规定为-1），用idx来表示第几个节点

const int N = 1e6+10; int e[N],ne[N],idx=1; //因为有一个头节点，所以idx为一 ne[0]=-1;

节点插入链表的顺序，这里我们需要指明，假设第三个节点插入，那么假设该节点的下标为3，此后3下标对应的点被删掉了，那么链表中就不存在下标为3的节点了，也就是说3这个不再使用了，我们下标的使用规则是一直增大，不会减小。

1.2链表的头结点和结束标志是什么？

初始时，我们可以创建一个head变量，并将其赋值为-1，可能有人会问这里的结束标志如何才能不与节点的数据域的数据冲突，其一，我们的head表示的是头结点所对应的下标，和数据域并没有直接联系，其二，数组的下标是不可能为负数的，所以我们的结束判断条件可以使用。

1.3遍历方法

我们通过头结点指向的下标开始，每次输出该下标对应的权值，然后将下标改为上一个下标对应的节点所表示的下一个节点的下标，继续遍历，重复此过程，直到某一次节点的下一个节点的下标为-1，即为遍历结束。

void print() { int i = head; while (1) { printf("%d ", e[i]); i = ne[i]; if (i == -1) break; } printf("\n"); }

下面，我们就尝试画出结构图来帮助理解：

1.4链表的相关操作的模拟实现举例 头插增加一个节点

void add_front(int x)//在链表头插入一个元素 { e[idx] = x;//保存权值 ne[idx] = head; head = idx; idx++; } 尾插一个节点

void add_back(int x) { e[idx] = x; int i = head; while (ne[i] != -1) //找到最后一个节点 { i = ne[i]; } ne[i] = idx; ne[idx] = -1; idx++; } 删除pos位置的节点

//删除pos位置处的数据 void remove_pos(int pos) { int i = head; while (ne[i] != pos) i = ne[i]; ne[i] = ne[ne[i]]; } 在pos之前插入数据

void add_insert_front(int pos,int x) { if (pos == 0) add_to_head(x); else { //目前我只想到了从前往后遍历才能找到pos之前的节点,所以各位大佬有何高明见解欢迎指出 int i = head; while (ne[i] != pos) { i = ne[i]; } e[idx] = x; ne[i] = idx; ne[idx] = pos; idx++; } } 2.相关的链表增删查改功能实现

代码为理想情况下的实现，有欠考虑的非法样例，如果读者发现错误，还请指出，您指出的BUG对你对我都是提升，何乐而不为呢？

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int e[maxn], ne[maxn], idx, head;//e表示点的权值，ne表示节点的下一个节点所代表的下标,idx表示当前可以插入的点的下标位置，head表示头结点，初始指向-1表示为空 //初始化 void init() { head = -1;//初始时head指向-1 idx = 1;//idx可以为1也可以为0,区别只是开始存的下标不一致 } //在头部插入数据 void add_to_head(int x) { e[idx] = x; ne[idx] = head;//将新的节点的下一个节点改为头结点 head = idx;//头结点更新为新插入的节点 idx++;//下一个待插入的位置 } //销毁链表 void destory() { ne[head] = -1;//直接将头结点的下一个节点更新为-1即可，数组中存在的值不用销毁 } //在尾部插入数据 void add_to_back(int x) { //先找到最后一个节点 int i = 0; for (i = head; ne[i] != -1; i = ne[i]); //插入即可,此时i就是最后一个节点的下标 e[idx] = x; ne[i] = idx; ne[idx] = -1; idx++; } //查找指定数据 void find_x(int x) { for (int i = head; i != -1; i = ne[i]) { if (e[i] == x) { printf("查找成功\n,第一个%d存储在下标为%d的位置处\n", x, i); return; } } printf("查无此节点\n"); return; } //在pos之前插入数据，这里的pos表示下标,如果idx初始化为0，则pos可以等于0，否则pos需大于0 void add_insert_front(int pos,int x) { if (pos == 0) add_to_head(x); else { //目前我只想到了从前往后遍历才能找到pos之前的节点,所以各位大佬有何高明见解欢迎指出 int i = head; while (ne[i] != pos) { i = ne[i]; } e[idx] = x; ne[i] = idx; ne[idx] = pos; idx++; } } //在pos之后插入数据 void add_insert_back(int pos, int x) { if (ne[pos] == -1)//最后一个节点后面插入相当于后插,但是后面的也是可以使用的，这里if...else可以合并 add_to_back(x); else { e[idx] = x; ne[idx] = ne[pos]; ne[pos] = idx; idx++; } } //打印链表 void print() { int i = 0; for (i = head; ne[i] != -1; i = ne[i]) { printf("%d->", e[i]); } printf("%d\n", e[i]); } //在头部删除数据 void front_remove() { if (ne[head] == -1)//表示没有数据 { printf("没有数据\n"); return; } else { head = ne[head];//头结点指向所指向节点的下一个节点 } } //在尾部删除数据 void back_remove() { int i = head; if (head == -1) { printf("链表没有数据\n"); return; } else { while (ne[ne[i]] != -1) i = ne[i]; ne[i] = -1; return; } } //删除pos位置处的数据 void remove_pos(int pos) { int i = head; while (ne[i] != pos) i = ne[i]; ne[i] = ne[ne[i]]; } //删除pos位置后的数据 void remove_back_pos(int pos) { if (ne[pos] == -1) { printf("该元素为最后一个，无法再删除后面的元素\n"); return; } else { ne[pos] = ne[ne[pos]]; } } //修改pos位置处的函数 void modify_pos(int pos,int x) { e[pos] = x; } //测试代码 int main() { init(); add_to_head(1); add_to_head(2); add_to_back(3); add_to_back(4); print(); find_x(3); add_insert_front(3, 5); add_insert_back(3, 6); print(); front_remove(); back_remove(); print(); remove_pos(3); print(); remove_back_pos(4); print(); modify_pos(5, 6); print(); return 0; }

Acwing 826

#include <iostream> using namespace std; const int N = 100010; // head表示头节点的下标 // e[i] 表示节点i的值 // 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, ne[idx] = head, head = idx, idx ++; } // 将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() { int m; cin >> m; // 首先初始化 init(); while(m --) { int k, x; char op; cin >> op; if(op == 'H') { cin >> x; add_to_head(x); } else if(op == 'D') { cin >> k; if(!k) head = ne[head]; remove(k - 1); } else{ cin >> k >> x; add(k - 1, x); } } // 打印整个链表 for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; //cout << endl; return 0; }