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 结构体来声明实体类。

[JocyeI]

K神，vx或qq群吗

[krahets]

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

[yizhiteamo]

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

[JocyeI]

经典，膜拜的第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 回收

[andwind1223]

请教一下各位大佬，就是当链表进行插入的时候，如果只知道要插入的位置的前节点的值，是不是复杂度就是O(n)了，因为需要从头开始遍历找到该值对应的节点。删除也是同理。

[bingegege]

并不是，时间复杂度是O(1)，这里函树的入参是前一节点的内存地址(java中就是引用传递)，知道了对象的内存地址，即可直接寻址到，不需要从头遍历

[bingegege]

打错字了，是函数

[liaoruochenxin]

是的，如果只知道值就是O(n)

[JakeZhangZJK]

JavaScript，留下足迹

[xuhuaigu]

/* 在链表中查找值为 target 的首个节点 */
int Find(ListNode? head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

不是说返回节点吗？怎么变成返回值了？这里可能需要调整一下。

[liaoruochenxin]

返回节点的索引

[promsie]

/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode n0) {
if (n0.next == null)
return;
// n0 -> P -> n1
ListNode P = n0.next;
ListNode n1 = P.next;
n0.next = n1;
}
为什么不直接n0.next = P.next; 多引入一个中间变量n1是不是有点多余？

[hncjxywyh]

便于理解可能

[Yangaiety]

可能是这样，在删除时设置一个临时指针Tmp指向要被删除的节点P，在执行完n0.next = P.next后，再去释放该空间。

[FrierenGreatDemonLord]

也可以编写一个循环将数组转换成链表，并封装成链表类的方法，方便链表的初始话，如Python：

class ListNode:
    def __init__(self, val: int):
        self.val: int = val
        self.next: ListNode | None = None

    @staticmethod
    def get_ls(nums: list) -> ListNode:
        head = ListNode(nums[0]) if nums else None  # 头节点
        pre = head  # 上一个节点
        for i in range(1, len(nums)):
            current = ListNode(nums[i])
            pre.next = current  # 上一个节点指向当前节点
            pre = current  # 更新上一个节点
        return head



head = ListNode.get_ls([1, 2, 3, 4, 5])

[GarenXie1]

您好，如果加上 Linux Kernel 内 如何实现 链表内容，那内容将更加全面了.

[chrishxxy]

您好,请问图是使用什么软件画出来的呢

[wzhuo2022]

我感觉PPT可以。

[M1aoo]

/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {
for (int i = 0; i < index; i++) {
if (head == nullptr)
return nullptr;
head = head->next;
}
return head;
}

有个地方我没弄懂，就是这段代码里head = head->next之后是否会导致越来越短，链表头结点会变成他的下一个节点吗

[codespider17]

哥们这只是指针指向变了用来查找啊，真正的节点还是存在的啊，这个代码只是把下一个节点当做头结点而已，不是真的取代了

[PAIOyzh]

因为作为函数传入的参数head只是一个局部变量副本，链表原来的头节点并没有发生变化

[ginitaimeiyty]

这是值传递，你说的这种情况叫引用传递，把ListNode *head改成ListNode *&head就会发生你说的情况

[lihahaya123]

def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
n1 = n0.next
P.next = n1
n0.next = P
这段代码改为：
def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
P.next = n0.next
n0.next = P
会有影响吗

[solaxido]

没影响的。这里的n1可能是为了方便阅读代码而设置的一个中间变量。

[wqk756633]

真的吗？

[zhuiguang49]

没有影响，就是记了个中间变量

[solaxido]

有个疑问，我们在链表中实现插入/删除某个节点时，应该是头指针遍历到某个位置后，才能进行插入/删除。从这方面看，时间复杂度是O(n)。那我们平时在谈到链表的插入/删除操作时，时间复杂度应该是指哪一个？O(n)还是O(1)？

[ffmm520]

回去查看时间复杂度一章，你就有答案了

[MicroSharpAnt]

可以看博主的算法实现，插入和删除的函数中，都没涉及到循环，显然时间复杂度为O(1)

[BrianChen666]

这里的插入和删除指的插入和删除某个节点的下一个结点，你知道了某个结点，下一个就是要添加的，所以是1。你说的情况是别的情况，比如单项链表删除前一个结点而不是后一个的时候，或这是插入在上一个结点和传入结点中间，那么为n。时间复杂度要和具体插入和删除情况而定

[lzhlrcoding]

def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
n1 = n0.next
P.next = n1
n0.next = P
在插入节点中，n1 = n0.next这句应该是多余的吧，写这句没有必要啊。请大佬指点指点。

[jingningwang]

把 no的下一个节点先找出来，再进行修改

[qiuxiran]

n1=n0.next代码的含义是把n0下一节点的值赋值给n1节点，显然，n0下一节点为P

[zhuiguang49]

不要这一句也可以的

P.next = n0.next
n0.next = P

[cyone123]

不是多余的。你估计是没搞清楚，这个函数的功能是在任意节点后插入，不只是在第一个节点后插入。

[yrrlxhj]

/* 链表节点结构体 */
struct ListNode {
int val; // 节点值
ListNode *next; // 指向下一节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
这个构造函数是怎么理解的？看不明白求教大佬

[halfpoundJ]

可以理解为它把两部操作写在一起了
ListNode(int x) {
val = x;
next = nullptr;
}

[ZhongGuanbin]

来信获悉，感谢您的支持！耑此奉复 钟冠彬This is an automatic reply, confirming that your e-mail was received.Thank you

[iLoveRatRace]

感谢来信，你的邮件已经收到。

[ginitaimeiyty]

int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) { 
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

int find(ListNode *head,int target){
	for(int i=0;;i++){
		if(head->next==nullptr||head==nullptr){
			return -1;
			break;
		}
		else if(head->val==target)
		{	
			return i;
			break;
		}
		head=head->next;
	}
}

我有一个问题：就是这两段代码都能实现相同的功能，而且时间复杂度都是O（n），假如考试的时候刚好考到这个算法，那这两段代码谁得的分最高？还是说都是满分？