chapter_array_and_linkedlist/linked_list/

[giscus[bot]]

chapter_array_and_linkedlist/linked_list/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_array_and_linkedlist/linked_list/

[Blackcat308]

请教k大，在fig.链表定义与存储方式图中，浅蓝色的存储结点指针是占用一块内存地址吗？还是和结点值各占一半呢？谢谢解答。

[krahets]

哈喽，非常好的问题！文中只是一个示意图，只是定性表示，没有定量。如果考虑定量的话，需要分情况：

• 不同类型的结点值占用的空间是不同的，比如 int, long, double, 或者是类的实例等等。
• 指针变量占用的内存空间大小根据所使用的操作系统及编译环境而定，大多为 8 字节或 4 字节。

[whh13345]

请教k大！在看图Fig. 链表定义与存储方式和下面的代码时，感觉有些奇怪，这两个描述的是不是不是一个层面，在java中一切都是对象，那绿色的值的节点存的也是指针吧，那他们一个是内存层面一个是代码层面，不是一个层面的数据结构为什么能直接运用到java的对象中呢？

[krahets]

抱歉，没有太看懂你的问题。可以再组织描述一下吗？

[ZhenhongDu]

k神链表常用操作里，“输出结点在链表中的索引”，代码都是return -1, 是不是应该return index?

[ZhenhongDu]

sorry，我看明白了，其实是我没看清楚，应该没问题, 😅

[KKStudyCoding]

没找到表示返回-1，返回一个负数。如果返回index，已知index最小为0，就算返回为0也表示找到了，在第一个结点中。

[iLoveRatRace]

链表访问节点处的代码的for循环中，先令 head = head.next 再判断 head 是否为空，请问一下先判断head.next 是否为空，若为空则返回 null ；不为空再令 head = head.next 会不会好一点点。

[iLoveRatRace]

删除节点 n0 后的首个节点的代码中ListNode P = n0.next; ListNode n1 = P.next; n0.next = n1; 此处是否可以简化为 n0.next = n0.next.next；

[krahets]

谢谢已统一。

可以这样简化，但为了提升可读性，本书把结点 P 显式地写出来了。

[WenlongDai]

想问一下 链表的插入和删除确实是O(1) 但是查找既然是需要遍历。那应该是O(n)不是么？

[ZZhenF]

是的，只做一次插入和删除操作时间复杂度是O（n），一般来说链表插入删除操作讨论的是大量插入和删除数据

[krahets]

对，补充楼上：如果是先查找元素、再删除元素，那么是 $O(n)$ 。但是这种只是一种特例，链表的 O(1) 插入与删除在其他应用上可以得到体现，比如「双向队列」适合使用链表实现，有指针（变量）始终指向头结点、尾结点，每次插入、删除都是 O(1) 。

[pleomax0730]

刪除結點後，是不是把 P.next 設為 None比較好呢？
我是看Python代碼，目前的代碼的鏈表結果會變成 P也同時指向n1
n0 -> n1
P -> n1

[Reanon]

引用计数就是其他的节点是否有引用它。一个节点没有被任何其他节点引用，那么它就是一个无引用的对象，所以就算 p->next 不为nil，也是会被 gc 的

[zrcoder]

@krahets @Reanon 问得好。 仔细梳理起来是这样的： p 的 next 指针还指向一个节点 x， 试想经过一段时间，x 节点没有被其他任何指针引用了，实际上运行时在gc时应该回收 x，但是，因为我们在删除 p 的时候，忽略了p的next指针指向x，x 就不会被回收 —— 当然需要追溯，gc 要看 p 是否回收，p 回收后会继续回收x，但当前（在删节点这个函数里）我们是不知道 p 是否还被其他节点引用的，健壮的做法就是及时断开p和x的链接。

@Reanon 垃圾回收的方式不止是引用计数，另有标记清除、分代回收等。Go 是标记清除法。

[zrcoder]

可以看看Go标准库 container/list 的实现，比如其删节点函数是这样：

// remove removes e from its list, decrements l.len
func (l *List) remove(e *Element) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
}

这是个双向链表，可以看到把 e 的前驱和后继指针都置为空了，且特意注释了这么做的理由。

[krahets]

@zrcoder 我们应该明确一下问题，讨论的是节点 p 的内存回收是否会受到 p.next 的影响。假设是一个逻辑清晰的链表，那么 p.next 的值不会影响到节点 p 的内存回收。

如果想要讨论 p.next 是否会影响后继节点的内存回收，这是另一个问题。你提到“我们是不知道 P 是否还被其他节点引用”，那可能性有两种：

第一种情况：程序中仍然长时间存在对 P 的引用，那么这将可能导致 A 不能被垃圾收集器回收，因为它们在理论上仍然是可达的。这种情况下，P.next = null 有助于防止内存泄漏。

第二种情况：给定的不是一个单链表。这种情况下，需要 case by case 地考虑。

假设有两个节点都指向 P ，那么实际上有两条链表，并且是“相交链表”，它俩拥有共同的尾部。记这两条链表为 A 和 B ，任务是从链表 A 中删除节点 P 。

如果我们执行了 P.next = null ，会导致节点 P 从链表 B 中也被删除了，而这并不是我们想要的结果。 也就是说，在这个案例中，我们不应该执行 P.next = null ，因为我们不希望在对链表 A 的操作中影响到链表 B 。

从工程角度看，由于庞大项目的复杂性，P.next = null 有助于防止内存泄漏，并且可以加速内存回收。从数据结构角度看，在一条单链表中 P.next = null 不是必须的；而在相交链表或图等复杂数据结构中，需要 case by case 地看，以达到我们想要的结果。只要程序逻辑正确，节点对象都可以被正常回收。

[zrcoder]

@krahets 赞，说得非常清楚。

[akppx]

Fig. 在链表中插入与删除结点示意图中，插入操作示例 节点P的插入顺序错了，应该是
1、P.next = n1
2、n0.next = P

[akppx]

代码是对的，先把 n0.next 保存起来了。按照链表的特性，修改了 n0.next 后就找不到 n1 了，所以示意图这样的表示顺序就不对了吧。

[krahets]

明白了。示意图里的 n1 是一个变量，即代码里的 n1 哈。第一步代表已知（即已暂存） n0 和 n1

[akppx]

哦哦，明白。但我还是觉得示意图有问题，应该先连 P 和 n1 之间的这根线，然后再断开 n0 和 n1 之间的线，最后再连接 n0 和 P ，觉得现在的这个容易造成误解。

[krahets]

谢谢建议！

[sample214]

想问一下github里，主函数里面为什么没有链表的定义，只有链表初始化？谢谢

[krahets]

Hi 链表结点的定义可以在 codes/java/include/ListNode.java 中找到，本项目将公共模块统一设计为 module

[HNUIsak]

在链表插入操作中，请问一下可以写成这段代码吗：

void Insert(ListNode* n0, ListNode* p)
{
    p->next = n0->next;
    n0->next = p;
}

[krahets]

没问题，实际上一般就是这么写～本文把 P 显式地写出来，便于理解。

[HNUIsak]

嗯嗯感谢您的解答！！

[ZhenhongDu]

k神请教一个问题，python里的链表的定义比较好理解，定义了一个ListNode类，这个类有两个属性，一个是存储的值，另一个是指向下一个数据的地址。

class ListNode:
    def __init__(self, x):
        self.val = x      # 结点值
        self.next = None  # 指向下一结点的指针（引用）

但是c++的这个结构体的定义看着我有点迷糊。
如果定义一个结构体指针，我的理解应该是 struct ListNode *next;, 为什么LeetCode上和k神的实现都没有struct关键字呢？

/* 链表结点结构体 */
struct ListNode {
    int val;         // 结点值
    ListNode *next;  // 指向下一结点的指针（引用）
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

[ZhenhongDu]

我明白了，感谢chatgpt! 原因是struct中的成员默认的访问权限是public的。在结构体中，可以直接访问结构体内部的成员变量，包括指针类型的成员变量，所以定义的时候可以省略struct关键字。而class的定义里，成员变量的默认的访问权限是private; 希望可以帮助同样有疑惑的同学。

[krahets]

Hi 不好意思昨天这条消息漏回了…… 你说的对，在 C++ 的 class 里成员变量默认 private ，如果用 class 写成这样就可以

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

看你的问题，感觉你想问的不是 private 和 public 的区别，而是要不要加 struct ？那是不用加的，因为那是在初始化一个变量。

另外，在 c++/c/go 中，我们一般使用 struct 结构体来声明实体类。

[Walhalla-Summary]

K神，vx或qq群吗

[krahets]

@Walhalla-Summary 有的，加我 WeChat krahets-jyd

[yizhiteamo]

好清晰的说明，要是当时学数构有这边书就好了。(•̀ω•́ 」∠)

[Walhalla-Summary]

经典，膜拜的第n遍，每次阅读都有不一样的收获，对于我这种似懂非懂算法的小白来说。非常nice的开源项目~

[krahets]

谢谢鼓励！如果可以的话加我微信 krahets-jyd ，想请你谈谈阅读感受、提提意见！

[CuiKing1270]

看这个之前自己也买了本书，最终发现还是作者讲得好啊。让我从原理明白了数据结构的魅力

[F9rozen]

可以添加一些链表的常见应用

单向链表

单向链表是一种常见的链表结构，每个节点包含一个指向下一个节点的指针。

1. 资源管理：单向链表可以用来管理资源，例如内存分配中的空闲块链表，通过将空闲的内存块连接成一个链表，可以方便地进行分配和释放。
2. 队列实现：单向链表可以用于实现队列（FIFO）的数据结构，通过在链表的尾部添加元素，并在链表的头部移除元素，可以实现高效的入队和出队操作。
3. 图的表示：在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。单向链表可以用于表示有向图或无向图中顶点的邻居关系。
4. 任务调度：在任务调度系统中，可以使用单向链表来管理待执行的任务列表，通过将任务连接成一个链表，可以按照特定的顺序进行调度和执行。
5. 多级反馈队列调度算法：多级反馈队列调度算法中，任务被分成多个优先级队列，并按照一定规则进行调度。每个队列可以使用单向链表来管理任务，实现按优先级进行任务调度。
6. 符号表和字典实现：在符号表和字典的实现中，可以使用单向链表来存储键值对。每个节点包含一个键和一个值，并通过指针连接成一个链表，实现高效的查找、插入和删除操作。

环形链表

首尾相接的链表结构，

1. 约瑟夫问题（Josephus Problem）：在约瑟夫问题中，有n个人围成一个环形，每次从指定位置开始计数，并按照固定规则将当前位置的人移出环形，直到最后只剩下一个人。环形链表可以用来模拟和解决这个问题。
2. 循环队列（Circular Queue）：循环队列是一种特殊的队列数据结构，当队列的尾部达到数组的末尾时，可以绕回数组的开头，形成一个循环。环形链表可以用来实现循环队列，提供高效的队列操作。
3. 循环链表遍历：使用环形链表可以实现循环遍历，即从任意节点开始遍历整个链表，而不会出现遍历到尾节点后的终止条件。
4. 环形缓冲区（Circular Buffer）：环形缓冲区是一种常见的数据结构，用于在固定大小的缓冲区中循环存储数据。环形链表可以用来实现环形缓冲区，实现高效的数据读写操作。
5. 快慢指针算法（Floyd's Cycle Detection Algorithm）：快慢指针算法是一种使用两个指针在环形链表中寻找环的算法。该算法可以应用于检测环形链表中是否存在环以及找到环的起始节点等问题。

双向链表

双向链表是一种链表结构，每个节点都包含指向前一个节点和后一个节点的指针。

1. LRU缓存（Least Recently Used Cache）：LRU缓存是一种常见的缓存替换策略，其中最近最少使用的数据被淘汰。双向链表可以用来实现LRU缓存，每次访问数据时，将其移到链表的头部，这样尾部的节点就是最近最少使用的数据，可以方便地淘汰。
2. 双向队列（Deque）：双向队列是一种具有队列和栈的特性的数据结构，可以在队列的头部和尾部进行插入和删除操作。双向链表可以用来实现双向队列，提供高效的插入和删除操作。
3. 图的表示：在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。双向链表可以用于表示有向图或无向图中顶点的邻居关系，每个顶点可以同时保存指向前一个邻居和后一个邻居的指针。
4. 浏览器历史记录：在浏览器中，双向链表可以用来实现浏览器的历史记录功能。每次访问一个新的页面，将其添加到链表的尾部，可以方便地实现前进和后退功能。
5. 文本编辑器的撤销和重做操作：在文本编辑器中，双向链表可以用来实现撤销和重做操作。每次编辑操作都可以将编辑内容添加到链表的尾部，可以通过向前或向后遍历链表来实现撤销和重做操作。
6. 音乐播放器的播放列表：在音乐播放器中，双向链表可以用来实现播放列表，每个节点表示一个音乐文件，可以方便地在当前歌曲的前后插入或删除歌曲。

[SihanMA]

牛啊, 结合应用感觉理解更深刻了

[longsizhuo]

谢谢大佬

[riiyn]

大佬，请教一下，删除链表元素P的时候，N0指向N1就可以了，但是P还是指向的N1，那P最终是被GC回收了吗

[krahets]

是的，由于已经没有任何变量引用 P ，因此 P 会被 GC 回收

[genskyff]

你已经学会了链表了，快用Safe Rust写一个实用的链表吧！

[zhangxiao-qing]

链表的插入中关于python的代码，不是三个节点吗？为什么只有n0和P呢，函数里引入了中间变量n1是什么作用呢，这段代码不是等于同于 n0.next=n0.next吗，这样也没有实现插入呀

[river505]

第一行是用n1获得n0的下一个指向，这里把n1理解成temp就行，用temp保存一下n0的下一个节点，让将要插入的节点P指向这个temp，再把n0的next指向P，n1是临时变量，在这个插入函数中传入的只是要插入的节点，和插入位置的前一个结点。再者说，第二行是P的next修改为n1，第三行是n0的next修改为P，没有n0.next=n0.next一说

[zhangxiao-qing]

我懂了！非常感谢你的解惑！

[nzxQAQ]

这里的 4.访问节点 与 5.查找节点 函数中，用到了head = head->next;
似乎会改变原本head指针指向的值，造成污染？
感觉应该将head指针复制为一个新的指针变量temp，在函数中操作temp，这样能够避免污染。

[nzxQAQ]

哦，我反应过来了。在C语言中，所有的函数参数都是值传递，包括指针类型。也就是说，当我将一个指针类型的参数传递给函数时，实际上传递的是指针变量的值（即指向某个内存地址的指针值），而不是指针变量本身。在函数内部改变指针变量的值，并不会影响到函数外部的指针变量。
所以这里的head不会被影响。

[SmallHamster2020]

用vscode运行python代码时报错，我这里不能像head: ListNode | None或者list[int]这样声明变量，不知道是不是因为编译器的问题。

Traceback (most recent call last):
File "/hpcfs/fhome/liyang/project/hello-algo/codes/python/chapter_array_and_linkedlist/linked_list.py", line 12, in
from modules import ListNode, print_linked_list
File "/hpcfs/fhome/liyang/project/hello-algo/codes/python/modules/init.py", line 6, in
from .list_node import (
File "/hpcfs/fhome/liyang/project/hello-algo/codes/python/modules/list_node.py", line 26, in
def linked_list_to_list(head: ListNode | None) -> list[int]:
TypeError: unsupported operand type(s) for |: 'type' and 'NoneType'

[hpstory]

Hi @SmallHamster2020, 请参考16.1节检查本地的python版本，推荐使用3.10及以上版本

[krahets]

Hi，书中的 python 代码使用了最新的 type hints 语法，需要使用 python 3.10 或更新版本

[FortuneBush]

删除节点的C++代码中，请问为什么要再定义一个ListNode *n1 = P->next; n0->next = n1;，直接让n0->next = P->next;这样不是更简单吗，请问这个两种方法有什么区别

[krahets]

没有什么区别，熟练后就用你的写法～书中显式地将 n1 写出来，以与图示完全对应

[nors1993]

Cpp里面需要释放内存~

[Study-missZhang]

Day2，加油！

[xxc111111]

me to

[tide-rhythm]

链表中等号的含义是什么呢？n1->next=n2和n1=n2有什么区别吗？

[krahets]

在编程语言中，等号代表赋值操作：

• n1->next=n2 代表将 n2 赋给 n1->next ，从逻辑上是让 n1 指向 n2 。
• n1 = n2 代表将 n2 赋给 n1 ，此时变量 n1 和 n2 指向同一个节点。

[tide-rhythm]

谢谢解答，但我还有一点不太明白，这样n1 = n2代表n1 和 n2 指向同一个节点，这样和n1->next=n2->next不就是一样的了吗？

[peso12345]

我觉得“变量n1和n2指向同一个节点”，可以理解成他们是同一个节点，内存地址指向同一个节点。

[nors1993]

cpp里面，一个表示指针，一个表示引用。

[Autumn00air]

n1->next是n1的下一个节点的地址，n1是n1的地址
n1->next=n2意思是让n1->next不指向n1的下一个节点，而是指向n2，也就是n1的下一个节点改为n2
n1=n2的意思是让n1指向n2，也就是原本的n1丢失了

[cuizisong]

不懂就问，为什么node要是指针类型的而不是直接定义为ListNode类型变量

[JohnIreal]

从C语言的视角来看，malloc函数的作用是申请一段连续存储空间，并返回这段空间的首地址。
node定义为指针类型是为了存储这段空间的首地址。
这样可以通过存储在node内的地址，来访问这个空间。
如果纯粹定义成结构体形式，它没法存储地址。

[chongayang]

可视化运行怎么变成cpp的模式

[2510466299]

可视化好像还没做cpp的模式，应该暂时只有python的模式

[CaMi1le]

链表删除节点的操作的时间复杂度是O(1)，但是查找节点是O(n)，这里是不是得修改一下

[lzy1960]

添加和删除O(1)，查找O(n)，没毛病呀，文中也没找到有错误的地方

[CaMi1le]

我意思是单向链表删除指定节点的复杂度是O(n)，没事我看到底下评论区了

[Tiro-Wang]

想问一下，删除节点中，C# 直接令n0.next=n1;为什么不可以呀，我看到评论区里c++代码可以直接n0->next = P->next;，这两种有什么不同呢？

[krahets]

没有什么不同，文中是先将 n1 = P.next; 记录下来，因此可以 n0.next = n1; 。这两个操作等价于 n0.next = P.next;

[Tiro-Wang]

感谢感谢，终于想明白了

[HuaWang135608]

Java 版的删除节点：

    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;

和

    n0.next = n0.next.next;

等价的

[resteven]

您好，在运行访问节点时，自己有一个小问题，这样返回了需要第i个节点，但是会丢掉原来的链表吧。这是为了初学者考虑所以尽量精简，只实现核心么？

[resteven]

Q2，k神，在比较数组和链表操作时间复杂度时，为什么链表的删除和插入都是O(1)的时间复杂度，虽然示例代码的实现里是这样的，但是这个删除操作是已经知道了n0，删除后面的一个节点，但是正常情况不应该是知道head，然后删除一个节点么，比如数组删除第i个元素（找到目标点，移动目标点后面的元素），第一步找到目标点是O(1),第二步是O(n)，所以是O(n)，提前感谢大大！

[resteven]

Q3，在高级数据结构里举了B树的例子，本书后面会说B树的内容么，因为正好这个学期学到的数据库里面似乎说到索引是用B+树实现的，如果对于后面的高级数据结构学习，是需要在算法的课程里面学习么

[krahets]

Q1：不会丢失，链表实际上是用头节点 head 记录的，我们向函数传入头节点，因此链表是已知的，执行函数也不会丢失
Q2：你说的情况是“查找 + 插入/删除”操作的情况，这是从组合操作角度的观察。但对于已知删除位置的情况（例如队列应用），数组仍然需要 O(n) 时间，而链表只需要 O(1) ，这是从操作本身角度出发的。
Q3：本书第一版集中介绍基础知识，B 树尚未涉及，可以先看看其他学习资源

[boybyte]

python有了列表还有必要要链表么?

[krahets]

大多数日常使用场景，列表就足够了（也通常比链表更优）。链表主要适用于“动态性”很强的场景，比如数据量非常大、增删操作频率很高等。

[MrJavaLiY]

我有一个问题希望作者或者其他同学帮我解答一下，文中提到的删除链表，可以看到例子中删除的是P节点，但是传入的却是n0节点，也就是说我并不知道P节点是谁，我实际上删除的是n0节点的下一个节点，那在实际运用中，我其实只知道P节点，我想删的也是P节点，但是我又不知道n0节点是谁，是不是只能通过遍历的方式一直判断当前节点的next是否为P，然后进行删除？

[wbzyo]

这里的no指的是头结点，我的理解是确实需要进行遍历式的逐个访问来确定该结点的next是否为p，所以也只能从头结点开始，因为无法知道任何其中一个结点的位置，这就是链表的特性

[XiAoY0]

注释里说明删除n0之后的p节点，如果不知道删除节点的上一个节点是谁，如果不是双向链表则需要遍历每一个节点，这时时间复杂度为O（n）