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

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

目录

前言

一、用数组结构的好处

1.数组的优缺点

2.链表的优缺点

3.总结

二、用数组实现链表

1.认识构造、初始化

2.将x插入到头结点

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

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

三、完整代码演示

四、数组实现双向链表

1.初始化

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

3.删除第k个点

五、完整代码

---

前言

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

typedef struct ListNode {
	int data;
	struct ListNode* next;
}List;

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

head	表示头节点
e[N]	表示存储结点数值的数组
ne[N]	表示结点的下一个结点的位置
idx   表示当前存储元素的位置   当前存储到哪里了就是

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

一、用数组结构的好处

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

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

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

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

1.数组的优缺点

认识数组：

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

优点：

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

缺点：

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

比如：

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

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

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

2.链表的优缺点

认识链表

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

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

缺点：

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

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

3.总结

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

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

二、用数组实现链表

1.认识构造、初始化

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

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

初始化代码：

//使用c++更简单，先用c++的形式实现
const int N = 100010;
int head, e[N], ne[N], idx; //全局变量
void init() {
	head = -1;
	idx = 0;//进行初始化的操作，idx为当前链表中（数组）最后一个元素（末尾），下标位置
}

2.将x插入到头结点

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

图示：

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

代码如下：

void add_to_head(int x) {
	e[idx] = x;//将x数值存入到e[]数组中
	ne[idx] = ne[head];//将idx新插入的结点的下一个位置存储到ne[idx]中  ，全局变量 ne以及n数组初始化为0
	head = idx;
	idx++;
}

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

图示：

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

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

图示：

代码如下：

//在第k个插入的数字之后插入数据
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}

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

//将下标为k的点后面的点删掉
void remove(int k, int ne[]) {
	ne[k] = ne[ne[k]];//表示k的下一个位置（ne）为下一个位置的下一个位置，这样跳过了原来的ne[k]结点
}//使用的时候应该是  删除的是k之后的点

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

三、完整代码演示

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
 
 
const int N = 100010;
int n, e[N], ne[N], idx, head;
 
 
//初始化
void init() {
	head = -1;
	idx = 0;
}
 
//头插
void add_to_head(int x) {
	e[idx] = x;
	ne[idx] = head;
	head = idx;
	idx++;
}
 
//在第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()
{
	init();
	add_to_head(1);
	add_to_head(2);
	add_to_head(3);
	add_to_head(4);
	add_to_head(5);
	add(2-1, 10);
	add(2-1, 2);
	add(2-1, 3);
	add(2-1, 4);
	add(2-1, 5);
	add_to_head(50);
	for (int i = head; i != -1; i=ne[i]) {
		printf("%d ", e[i]);
	}
	printf("\n");
	for (int i = head; i != -1; i = ne[i]) {
		printf("%d ", ne[i]);
	}
	return 0;
}
 

四、数组实现双向链表

1.初始化

//初始化
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示为左端点，1表示为右端点
	r[0] = 1;
	l[1] = 0;
	idx = 2;//从2开始
}

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

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

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

//在第k次插入的点的右边插入x；
 
void add(int k, int x) {
	e[idx] = x;//数值x给当前idx位置的e数组存储
	r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后将k的右端点的左端点连接idx
	r[k] = idx++;//最后将k的右端点连接idx
}

3.删除第k个点

//删除第k个点
void remove(int k) {
	//就是将k的左端点和右端点相互连接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}

五、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
//使用数组的形式实现双向链表
 
 
//e[N]	表示存储结点的数值
//l[N]	表示当前结点的左结点位置
//r[N]	表示当前结点的右节点位置
//idx	表示当前结点存储的位置
 
//初始化
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示为左端点，1表示为右端点
	r[0] = 1;
	l[1] = 0;
	idx = 2;//从2开始
}
 
//在第k次插入的点的右边插入x；
 
void add(int k, int x) {
	e[idx] = x;//数值x给当前idx位置的e数组存储
	r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后将k的右端点的左端点连接idx
	r[k] = idx++;//最后将k的右端点连接idx
}
 
//删除第k个点
void remove(int k) {
	//就是将k的左端点和右端点相互连接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}
 
int main()
{
	init();//初始化
	//添加元素
	for (int i = 0; i < 10; i++)
	{
		add(i, i);//在第i次插入的元素的后面，插入节点x
	}
	//实现遍历
 
	//因为e存储的是实际元素，但是由于要实现双向链表，即创建左右数组，表示当前idx的左右下标
	//如果我们需要进行正向，即向右，只需要以r[i]为下标，不断输出e的元素即可
	//反之以l[i]
	for (int i = 0; i < 10; i++)
	{
		//num表示当前此时下标位置
		cout << e[r[i]] << " ";//每一次循环不断更新当前节点的下一个节点的下标位置
	}
 
	cout << endl;
	for (int i = 0; i <10 ; i++)
	{
		//idx表示当前此时下标位置
		cout << e[--idx] << " ";//每一次循环不断更新当前节点的下一个节点的下标位置
	}
	//以上是正序和逆序的遍历
	cout << endl;
 
	return 0;
}