数组模拟链表（超详细）

链表

• 何为链表
• 单链表的构成
• 双链表的构成

---

何为链表

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

链表和数组的区别：采用顺序存储结构时称为为数组，采用链式存储结构时称为为链表。但二者同为线性表。

简单的说：
数组通过下标将每一个元素值联系在一起，并且用一组地址连续的存储单元（物理位置相邻）来存储表中的元素值

链表通过指针把每一个元素的值联系在一起，不要求逻辑上（链表逻辑）相邻的两个元素在物理位置上也相邻，那么就需要链表元素需要两个数据，一个是储存该元素的值，一个是储存链表下一个元素的地址，两者统称为一个节点，接下来每一个元素都用对应的节点表示，阐明两个存储数据

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

单链表的构成

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

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

首先链表里面需要两个数据，一个是值，一个是下一个元素的地址

一般的 : 我们用e[]数组储存链表里面的值，用ne[]数组储存链表每个元素下一个元素的地址

const int N = 1e6+10;

int e[N],ne[N];
1
2
3

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

const int N = 1e6+10;

int e[N],ne[N],idx=1;   //因为有一个头节点，所以idx为一
ne[0]=-1;
1
2
3
4

那么一个单链表的雏形构建完毕，我们接下来应该对链表进行操作，实现链表的基本功能

1，在第k个节点插入元素x

void to_insert(int k,int x)
{
	e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
    //注意顺序不能翻！！！
}

1
2
3
4
5
6
7

我们将idx节点的元素先赋值，就是e[idx]=x.

再将idx节点下一个元素的地址赋值（这个值是k节点的下一个元素的地址，即ne[k]）所以是ne[idx]=ne[k].

最后在把k节点的下一个元素的地址指向idx，所以是ne[k]=idx.

示例代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int e[N],ne[N],idx;  

void init() {idx=1;ne[0]=-1;}

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

int main()
{
	init();
    int t;
    cout<<"请输入你要访问的次数: ";
    cin >> t;
    while(t--)
    {
		int k,x;
        cout<<"请输入你要在单链表第几号节点插入数字: "; 
        cin>>k;
        cout<<"插入的数字是: ";
        cin>>x;
        to_insert(k,x);
        cout<<"该单链表变为: ";
        for(int i = ne[0];i != -1;i = ne[i]) cout<<e[i]<<" ";
        cout<<endl<<endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

结果如下：

2，删除第k个节点后面的元素

void remove(int k)
{
	ne[k]=ne[k]];//直接让k<指向的地址>指向k+1<指向的地址>，即把k+1节点跳过
}

1
2
3
4
5
6

单链表基本上以及完成，让我们带上一个简单的例题看看最终的代码：

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的数；
3. 在第 k 个插入的数后插入一个数

输入格式

第一行包含整数 MM，表示操作次数

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. H x，表示向链表头插入一个数 x。
2. D k，表示删除第 k个插入的数后面的数（当 k 为 0 时，表示删除头结点）
3. I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）

输出格式

共一行，将整个链表从头到尾输出

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
1
2
3
4
5
6
7
8
9
10
11

输出样例：

6 4 6 5
1

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int e[N],ne[N],idx;  

void init() {idx=1;ne[0]=-1;}

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

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

int main()
{
	init();
    int t;  cin>>t;
    while(t--)
    {
        char c;
        int x,k;
        cin>>c;
	       	if(c=='H')	
            	{
	       			cin>>x;
	       			to_insert(0,x);
			   	}
        	
        	if(c=='D')	
            	{
 					cin >> k;
  	     			remove(k);
				}
        
        	if(c=='I')  
            	{
        			cin >> k >> x;
        			to_insert(k,x);
				}
 
            
    }
    
    for(int i = ne[0];i != -1;i = ne[i])	cout<<e[i]<<" ";
    
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

双链表的构成

一个元素有三个数据，一个是元素的值，一个是下一个元素的地址，还有一个是上一个元素的地址，像这样的链表就是双链表

总体上同样和单链表类似，用数组模拟。

一般的 : 我们用e[]数组储存链表里面的值，用r[]数组储存链表每个元素右一个元素的地址，用l[]数组储存链表每个元素左一个元素的地址。这里我们同样默认链表两端有两个不变的数0，1来防止空链表的情况,这时k=2.

const int N = 1e6+10;

int e[N],l[N],r[N],idx;

void init()
{
    r[0]=1;l[1]=0;idx=2;
}
1
2
3
4
5
6
7
8

1，双链表在第k个节点右边插入元素x

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

1
2
3
4
5
6

如果是左侧插入，只需让k节点左侧插入变为k-1节点右侧插入，就是l[k]进入子函数

样例代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int e[N],l[N],r[N],idx;  

void init() {idx=2;r[0]=-1;l[-1]=0;}

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

int main()
{
	init();
    int t;
    cout<<"请输入你要访问的次数: ";
    cin >> t;
    cout<<endl;
    while(t--)
    {
		int k,x;
		char p;
        cout<<"请输入你要在双链表第几号节点插入数字: "; 
        cin>>k;
       	cout<<"请输入插入方向：";
		cin>>p; 
        cout<<"插入的数字是: ";
        cin>>x;
        if(p=='r') to_insert(k,x);
        else to_insert(l[k],x);
        cout<<"该单链表变为: ";
        for(int i = r[0];i != -1;i = r[i]) cout<<e[i]<<" ";
        cout<<endl<<endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

结果如下：

2，删除k节点的数

在这里插入图片描述

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

1
2
3
4
5
6