用数组模拟单链表和双链表（图+代码）详解_数组模拟链表

 链表，可以理解成环环相扣的数据组，通过一些方法链接在一块。

一.模拟单链表

单链表通过 node->next 链接在一起，如下图：用数组模拟也是一样。想办法找到某些条件通过数组来把数据链接在一起。

我们通过两个数组来实现，一个数组（e[n]）来存要存的数据，一个数组（ne[n]）来存放存数据数组的下标。

接下来先对head和idx进行初始化。链表会对head->next=NULL一样，让 head = -1表示head的下一个是空的。idx=0，表示从头开始，头也就是第0个（head头无法存储数据）。

初始化完后，我们可以实现一些功能了。

1.开始时在头节点的后面插入一个数值

先看代码：

​
void add_head(int x)
{
	e[idx]=x;
	ne[idx]=head;
	head=idx;
	idx++;
}
 
​

e[idx]本是就是一个储存我们要存的数据的一个数组，存完值后让e[idx]这个数组指向head的下一个值（可能是空的，也可能使有数据），让head指向e[idx],最后idx的值顺势加1.

2.在第k个插入的数的后面插入一个数

先看代码;

void add(int k,int x)
{
	e[dix]=x;
	ne[dix]=ne[k];
	ne[k]=dix;
	dix++;
}

大体思路上与在头节点后面插入相同。一开始A->B,我们要实现A->B->C，那就让A的ne[ ]值是B的下标，B的ne值是C的下标，相当于在链表中用next链接。

3.删除第 k 个插入的数后面的数

先看代码：

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

比如说要把A->B->C中的B删掉，那就是把第k个（就是A）后的数删掉，直接越过B，让A的ne[ ]值等于C的下标，把B跳过去，这样B就没有啦

4.总结

模拟单链表通个存储每个存数据的数组的下标来实现链接在一起，ne[ ]存的就是下一个节点的下标，如果下标是-1的话，那么就是空的，本质上与结构体链表没什么区别

二.模拟双链表

双链表与单链表的区别就是要照顾左右两个方向的链接。

首先进行初始化：l[1]=0.r[0]=1,idx=2,定义两个头节点，左右各一个，l[ ]存的是向左走的下一个数组的下标，r[ ]存的是向右走的下一个数组的下标，看一下图​​​​​​​

注意：不要将r和l弄反了

1.将第k个插入的数删除

思路与单链表相同，就是越过一个节点，直接用下标链接起来，代码：

void del(int k)
{
	r[l[k]]=r[k];
	l[r[k]]=l[k];
}

l[k]是A的下标，r[A的下标]=r[k]（r[k]就是C的下标），这样向右的链就越过B直接连上了；

r[k]是C的下标，l[C的下标]=l[k]（l[k]就是A的下标），这样向左的链就越过B直接连上了。

2.在第k个插入的数的左边插入一个数

代码：

void addl(int k,int x)
{
	e[idx]=x;
	r[idx]=k;
	l[idx]=l[k];
	r[l[k]]=idx;
	l[k]=idx;
	idx++;
}

图有点乱，大家见谅。

思路：让A的 r 链接到D上，D的下标链接到B上，向左处理同理。D的下标是idx。先储存好D的值，然后开始链接，只看一个方向的原理同上述单链表相同。但要注意的是l[k]=idx这步要最后实现，因为A->D的 r 还没有连，如果让l[k]=idx放在前面，那么A就连不上D了。

3.在第k个插入的数右边插入一个数

思路与左边插入的数一样，这里就不过多赘述了直接上代码;

void addr(int k,int x)
{
	e[idx]=x;
	l[idx]=k;
	r[idx]=r[k];
	l[r[k]]=idx;
	r[k]=idx;
	idx++;
}

文章到这里结束啦，创造不易，如果喜欢的话点个赞点个关注

谢谢大家^_^