【数据结构和算法】使用数组的结构实现链表（单向或双向）

上文我们通过结构体的结构实现了队列、以及循环队列的实现，我们或许在其他老师的教学中，只学到了用结构体的形式来实现链表、队列、栈等数据结构，本文我想告诉你的是，我们可以使用数组的结构实现链表、单调栈、单调队列

目录

前言

一、用数组结构的好处

1.数组的优缺点

2.链表的优缺点

3.总结

二、用数组实现链表

1.认识构造、初始化

2.将x插入到头结点

3.将x插入到第k次插入数值之后的位置

4.删除第k次插入的结点

三、完整代码演示

四、数组实现双向链表

1.初始化

2.在第k次插入的点的右边插入x

3.删除第k个点

五、完整代码

你之前实现链表的形式，是不是这一种结构来实现

但是我如果告诉你只需要这样两个数组就能模拟实现链表，你相信吗！！！

 接下来我们来实现单链表，以及双向链表

我们在日常学习的过程中，老师教授给我们的都是以结构体的形式实现的链表，但是呢，比如我们要创建100000个结点，这样的话， 用结构体的话，时间太长，空间太大，反观数组，就显得很有优势了。

1.在搞算法的时候，使用数组的形式去模拟链表，会使得运算速度变快，更加适合写算法，打比赛的小朋友。

2.在笔试的适合，会更快的创建实现链表的基础功能，进行插入删除元素，并根据下标直接找到所需元素等

我们在来了解一下数组和链表的优缺点吧

认识数组：

数组是一种线性结构，存储的空间是内存连续的（物理连续），每当创建一个数组的时候，就必须先申请好一段指定大小的空间。（一次申请即可指定大小的空间）

优点：

由于内存连续这一特征，数组的访问速度很快，直到索引下标之后，可以实现O(1)的时间复杂度的访问。

缺点：

1.在任意位置删除和插入操作的时候，就会涉及到部分元素的移动，这样的话我们对于数组的任意位置的删除和插入的操作的时间复杂度为O(n)。

比如：

1>在i点后面插入数据，那么就需要i+1位置以及之后的元素，整体后移一位（for循环操作），然后再将插入的数据放在i+1的位置上

2>在i点之后删除元素，那么就需要，将i+1以及之后的元素，整体前移一位，总元素个数减一

以上是数组的优缺点，可以快速访问，达到O(1)，但是在任意删除和插入元素的时候，会耗时间，达到O(n)。

认识链表

1.链表也是一种线性结构，但是他存储空间是不连续的（物理不连续，逻辑连续），链表的长度是不确定且支持动态扩展的。每次插入元素的时候，都需要进行申请新节点，然后赋值，插入链表中。

优点： 在插入数据或者删除数据的时候，只需要改变指针的指向即可，不需要类似于数组那样部分整体移动，整个过程不涉及元素的迁移，因此链表的插入和删除操作，时间复杂度为O(1)

缺点：

在查找任意位置的结点的数值域的时候，需要遍历，时间复杂度为O(n)

但是我们在任意位置插入或者删除元素的时候，需要查找这个指定的元素的结点位置，所以综合起来，链表的插入和删除仍为O(n)。

无论数组还是链表，查找的时间复杂度都是O(n)，查找都要挨个遍历，直到找到满足的条件的数据为止，所以对于链表，如果没有给定，指针的地址，只是要插入删除第N位元素的时候，加上查找，综合起来时间复杂度为O(n)。

但是我们如果以数组的形式来实现链表，那么插入删除指定元素位置的时候，是不是就更加简便了呢，在第N位插入删除元素的时候，直接以O(1)的时间复杂度找到该位置结点，然后再由于链表的删除插入都是O(1)的，所以整个删除或插入操作，综合时间复杂度为O(1),比普通链表快很多。

我们先由图示了解初始化的时候的准备工作

我们使用c++会更加方便理解，因为c++支持用变量来定义数组

初始化代码：

就是所谓的链表中的头部插入

图示：

实际上和普通链表的头插一样，只是流程next指针换成了ne[N]数组的形式，记录的是下一结点的数值。

代码如下：

图示：

我们要说明一个问题，ne[N]这个数组存放的数值，是不需要管的，因为不管是add还是remove，插入还是删除结点，都不会重复，实际上，e[ne[head]]是得到head结点下一个结点的数值，ne[]数组只作为，下标使用。 

我们是在第k次插入的之后的位置插入x，但是与此同时 ，此时的idx成为新的第k次插入数据下标，也就是说，再次对第k次插入数值之后的位置插入的x，实际上是在上一次的新插入的结点之后进行插入

图示：

代码如下：

直接跳过即可，和链表类似

我们设定，用e[N]数组来记录数据，在用 l[N] 、 r[N]数组表示结点的左右指针，一开始，0表示为左端点，1表示右端点，然后r、l两个数组记录，数值下标从2开始

e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点