【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理_分别建立两个有3个元素结点的单链表(无头结点),然后对两个链表进行各自排序(显示

• 博主简介：努力学习的预备程序媛一枚~
• 博主主页： @是瑶瑶子啦
• 所属专栏: Java岛冒险记【从小白到大佬之路】

前言

因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛，最近在学习算法相关的知识。我是借助AcWing网站来学习的，这篇文章是我学习就我学习内容的一个笔记，其中的一些对原理的解释是我学习过程中可能看到弹幕或者评论的小伙伴，觉得讲的很有道理醍醐灌顶，就引用过来了。
这篇是关于数据结构，主要是利用数组模拟各种数据结构，主要是提高算法效率。
对于一些比较晦涩难懂\让人头秃的地方，我习惯采用画图的方式来理解，所以你将看到我基于算法模板或题目精心绘制的图解，希望能帮助一起学算法的同学噢！
因为瑶瑶子目前还是小菜鸡，可能会有理解不到位的地方，或者可以理解得更好的地方，还请大家多多指出哦！❤

注意！下面每一种数据结构的讲解方式，采用代码模板+文字说明&解释+图解

1.单链表(邻接表）

作用：多用于邻接表，存储图和树

代码模板

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点,后一个
int head, e[N], ne[N], idx;
//NULL相当于-1,所以head = -1相当于head=NULL
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{   
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
//将x插入到下标是k的点之后
void insert(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k]
	ne[k] = idx;
	idx ++;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
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

• 存储节点数组的e[N]和存储该节点的next指针数组ne[N]通过下标关联
• idx只是记录当前的操作的位置，一般实现的链表idx是乱序的(前后的节点的数组下标不需要连续，需要通过当前的ne[i]找到下一个idx。这也是两者的联系。
• head一开始=-1，这个-1相当于物理地址的NULL，表示链表为空，即head指向一个头节点，而使用头插法，又巧妙的使这个空节点成为尾节点。联想结构体实现的单链表，最后一个节点的指针域是NULL所以，数组实现单链表的最后一个节点，假设是i,那么ne[i]=-1；
• 这里模拟的是没有头节点，head指针直接指向首元节点的单链表
• 虽然数组模拟的链表没有用结构体/类模拟的好理解，但是本质都是一样的，我们可以类比一下，对于一个节点Node。
• 所以其实画图的时候，也没必要分的那么清楚，其实在我学习数组模拟链表之前，我一直认为数组&链表属于物理结构，现在才发现，其实链表是一种逻辑结构！

图解

插入操作（头插法）

2.双链表

学习了数组模拟单链表，其实双链表就很好理解了。其实就是多了一个指针域。

• 单链表：ne[i]存储指针为i的节点的next指针
• 双链表
  • l[i],指针为i的节点的前驱（指向前一个节点）
  • r[i],指针为i的节点的后驱（指向后一个节点）

//e[index],表示节点的值，l[index]表示节点的左指针，r[index]表示节点的右指针，idx表示当前用到哪个节点的”地址“

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

//初始化
void init(){
  //0是左端点，1是右端点
  r[0] = 1,l[1] = 0;
  idx = 2;
}
//在节点a的右边插入一个数x
void insert(int a,int x){
  //1、让待插入节点占位
  e[idx] = x;
  //2、处理待插入点左右两侧
  l[idx] = a,r[idx] = r[a];//注意，这里必须是r[a]，因为a的下一个节点不一定和a顺序存储
  //3、处理前一个节点和后一个节点
  l[r[a]] = idx,r[a] = idx++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Java岛冒险记【从小白到大佬之路】

LeetCode每日一题–进击大厂