用数组实现链表、栈和队列_数组可以实现链表

前言

众所周知，链表可以用结构体和指针来实现，而栈和队列可以直接调用STL，那为什么还要费尽心思用数组来实现这三种数据结构呢？

首先，对于用结构体和指针实现的链表，每次创建节点都要使用 new 关键字，这一步非常慢，尤其是当链表的长度 $\ge 10^5$ 时，用这种方法构造的链表在处理各种操作时很有可能TLE。其次，STL容器本身就要比原生数组慢，当数据量非常庞大的时候，使用数组来模拟这些数据结构是一个不错的选择。

一、用数组实现链表

1.1 单链表

通常，我们习惯用结构体和指针来实现单链表（两个成员变量+三个构造函数）：

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
1
2
3
4
5
6
7

我们把用上述方式实现的链表称为动态链表，把用数组方式实现的链表称为静态链表。具体来说

• 使用动态链表存储数据，无需预先申请内存空间，而是在需要的时候用 malloc 或 new 关键字进行申请，所以链表的长度没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，需要通过指针来顺序访问；
• 使用静态链表存储数据，需要预先申请足够大的一块内存空间，所以链表的初始长度一般是固定的。静态链表因为是用数组实现的，所以每个节点的物理地址连续。

对于动态链表，每个节点不仅存储了一个值，还存储了指向下一个节点的指针，在动态链表上进行移动也是用的指针。静态链表自然也需要具备这些特性，那如何用数组的方式进行实现呢？

不妨给链表中的节点从 $0$ 开始编号，如果链表有 $n$ 个节点，则编号依次为 $0,1,\cdots ,n-1$。每个节点的编号可以视为指向该节点的「指针」，于是用指针访问节点便成了用「索引」访问节点（因为索引就是从 $0$ 开始的）。设链表可能达到的最大长度为 $N$，因此开两个数组分别用来存储每个节点的值和指向下一个节点的指针：

int val[N], nxt[N];  // val用来存储每个节点的值，nxt用来存储指向下一个节点的指针
1

例如，对于下图中的链表（红色为节点编号，黑色为节点存储的值）

val 数组和 nxt 数组应当分别为（规定空指针为 $-1$）

val[0] = 4, nxt[0] = 1;
val[1] = 2, nxt[1] = 2;
val[2] = 1, nxt[2] = 3;
val[3] = 3, nxt[3] = -1;
1
2
3
4

当然，仅用这两个数组来表示链表是远远不够的，我们还需要头指针 head 和一个指向待插入位置的指针 idx（因为是从小到大进行编号的，所以 idx 只会增加不会减少）

int head, idx;  // head是头指针，idx是指向待插入位置的指针，只增不减
1

头指针始终指向链表的头节点。初始时，链表为空，头指针为空指针，因此有 head = -1。因为链表中没有节点，故位置 $0$ 待插入，所以 idx = 0。链表的初始化函数如下

void init() {
    head = -1, idx = 0;
}
1
2
3

接下来，我们研究静态链表的插入与删除操作。

操作一：在链表头部插入元素 x。

因为 idx 为待插入的位置，因此执行 val[idx] = x 相当于创建了一个节点，接下来执行 nxt[idx] = head 相当于让该节点指向头节点，最后执行 head = idx 让头指针指向该节点。当然，不要忘了 idx++，因为 idx 已经被用过了（已经被编号了），因此待插入的位置变成 idx + 1。

void insert(int x) {
    val[idx] = x, nxt[idx] = head, head = idx++;
}
1
2
3

操作二：在第 $k$ 个插入的数后面插入一个数 x。

⚠️ 第 $k$ 个插入的数并不是指当前链表的第 $k$ 个数。例如操作过程中一共插入了 $n$ 个数，则按照插入的时间顺序，这 $n$ 个数依次为：第 $1$ 个插入的数，第 $2$ 个插入的数，$\cdots$，第 $n$ 个插入的数。

显然，idx 记录了插入顺序。即 idx 所指向的节点为按照时间顺序第 idx + 1 个插入的数（注意 idx 是从 $0$ 开始的）。

void insert(int k, int x) {
    val[idx] = x, nxt[idx] = nxt[k - 1], nxt[k - 1] = idx++;
}
1
2
3

操作三：删除第 $k$ 个插入的数后面的数，$k=0$ 时表示删除头节点。

void remove(int k) {
    if (k) nxt[k - 1] = nxt[nxt[k - 1]];
    else head = nxt[head];
}
1
2
3
4

⚠️ 切勿写成 nxt[k - 1] = nxt[k]，因为编号只在数组中连续，但不一定在链表中连续，所以 nxt[k - 1] 不一定等于 k。

操作四：输出链表。

for (int i = head; ~i; i = nxt[i]) cout << val[i] << ' ';
1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/616206