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]

[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 回收

[main520]

python语法小白笔记

1. 类型注解

self.next: ListNode | None = None

: ListNode | None为类型注解，意为类型可能是 ListNode，也可能是 None，需要手动初始化
2. 文件与模块

if __name__ == "__main__":
```只在执行文件时运行，作为模块导入时需要放在`if __name__ == "__main__":`之外
3.函数参数
```python
def print_list(head: ListNode):
    while head:
        print(head.val, end=" -> " if head.next else "\n")
        head = head.next

head为函数参数的局部变量，其改变不影响外部变量，如n0，主程序中修改n0则会导致链表丢失

看helloalgo之前只看了一点python语法，好多都不太懂，不过chatgpt功能真强大，不仅每行代码解释的明明白白的，还很会鼓励，学得很有劲！

[main520]

啊，markdown没换行

[NameZH131]

c才是好玩哇，指针，指针的地址
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct LinkNode {
ElemType data;
struct LinkNode *next;
} LinkNode, *LinkList;

// 创建新节点
LinkNode *createNode(int data) {
LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
if (node == NULL) {
printf("内存分配失败\n");
exit(1);
}
node->data = data;
node->next = NULL;
return node;
}

// 初始化链表（头节点）
LinkList initList() {
LinkList head = createNode(0); // 头节点数据设为0，可以用于存储链表长度等信息
return head;
}

// 头插法创建链表
void createListHead(LinkList *list, int n) {
*list = initList();
for (int i = 1; i <= n; i++) {
LinkNode *newNode = createNode(i);
newNode->next = (*list)->next;
(*list)->next = newNode;
}
}

// 尾插法创建链表
void createListTail(LinkList *list, int n) {
*list = initList();
LinkNode *tail = *list; // 尾指针初始指向头节点

for (int i = 1; i <= n; i++) {
    LinkNode *newNode = createNode(i);
    tail->next = newNode;
    tail = newNode;
}

}

// 打印链表
void printList(LinkList list) {
if (list == NULL) {
printf("链表为空\n");
return;
}

LinkNode *p = list->next; // 跳过头节点
int i = 1;
while (p != NULL) {
    printf("节点%d: 数据=%d, 地址=%p, 下一节点地址=%p\n", 
           i++, p->data, (void*)p, (void*)p->next);
    p = p->next;
}

}

// 检查链表是否为空
bool isEmpty(LinkList list) {
return list == NULL || list->next == NULL;
}

// 释放链表内存
void destroyList(LinkList *list) {
LinkNode *p = *list;
while (p != NULL) {
LinkNode *temp = p;
p = p->next;
free(temp);
}
*list = NULL;
}

int main() {
LinkList list1 = NULL;
LinkList list2 = NULL;

printf("创建链表1(头插法):\n");
createListHead(&list1, 5);
printList(list1);

printf("\n创建链表2(尾插法):\n");
createListTail(&list2, 5);
printList(list2);

printf("\n释放链表内存...\n");
destroyList(&list1);
destroyList(&list2);

return 0;

}

[iLoveRatRace]

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

[freehuoshan]

把我的也分享一下，Rust

use std::{cell::RefCell, rc::Rc};

struct Node<T: PartialEq> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>, 
}

impl<T:PartialEq> Node<T> {
    fn new(value: T) -> Self {
        Node { value, next: None }
    }
}

fn instantiate() -> Rc<RefCell<Node<i32>>> {

    let node0 = Rc::new(RefCell::new(Node { value: 0, next: None }));
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: None }));

    node0.borrow_mut().next = Some(node1.clone());
    node1.borrow_mut().next = Some(node2.clone());

    node0
}

fn get_pre_node<T:PartialEq>(node: &Rc<RefCell<Node<T>>>, index: usize) -> Rc<RefCell<Node<T>>> {
    if index <= 1 {
        return node.clone();
    }
    let next_node = node.borrow().next.as_ref().unwrap().clone();
    get_pre_node(&next_node, index - 1)
}

fn insert<T:PartialEq>(head: &Rc<RefCell<Node<T>>>, value: T, index: usize) {
    let pre = get_pre_node(head, index );
    let new_node = Rc::new(RefCell::new(Node { value, next: pre.borrow().next.clone() }));
    pre.borrow_mut().next = Some(new_node);
}


fn delete<T:PartialEq>(head: &Rc<RefCell<Node<T>>>, index: usize) {
    let pre = get_pre_node(head, index);
    let next = pre.borrow().next.as_ref().unwrap().borrow().next.clone();
    pre.borrow_mut().next = next;
}

fn find<T: PartialEq>(head: Rc<RefCell<Node<T>>>, target: T) -> Option<usize> {

    fn check_at<T: PartialEq>(node: &Option<Rc<RefCell<Node<T>>>>, target: T, index: usize) -> Option<usize> {
        if let Some(n) = node {

             if n.borrow().value == target {
                return Some(index)
             }else {
                return check_at(&n.borrow().next, target, index + 1);
             }

        }
        None
    }

    check_at(&Some(head), target, 0)

}

fn current_node<T: PartialEq>(node: &Rc<RefCell<Node<T>>>, index: usize) -> Rc<RefCell<Node<T>>> {
    get_pre_node(node, index).borrow().next.as_ref().unwrap().clone()
}

fn print_items<T: std::fmt::Display + PartialEq>(head: &Rc<RefCell<Node<T>>>) {
    let mut current = Some(head.clone());
    while let Some(node) = current {
        print!("{} -> ", node.borrow().value);
        current = node.borrow().next.clone();
    }
    println!("None");
}


#[test]
fn test_create() {
    
    let head = instantiate();
    print_items(&head);

}

#[test]
fn test_new(){
    let head = Rc::new(RefCell::new(Node::new(0)));
    print_items(&head);
}


#[test]
fn test_insert() {
    let head = Rc::new(RefCell::new(Node::new(0)));
    insert(&head, 1, 1);
    insert(&head, 2, 2);
    insert(&head, 3, 3);
    insert(&head, 4, 4);
    print_items(&head);
}

#[test]
fn test_delete() {
    let head = Rc::new(RefCell::new(Node::new(0)));
    insert(&head, 1, 1);
    insert(&head, 2, 2);
    insert(&head, 3, 3);
    insert(&head, 4, 4);

    print_items(&head);

    delete(&head, 1);

    print_items(&head);

    delete(&head, 3);

    print_items(&head);
}

#[test]
fn test_current_node() {
    let head = Rc::new(RefCell::new(Node::new(0)));
    insert(&head, 1, 1);
    insert(&head, 2, 2);
    insert(&head, 3, 3);
    insert(&head, 4, 4);    

    println!("current node at index 1: {}", current_node(&head, 1).borrow().value);
}

#[test]
fn test_find() {
    let head = Rc::new(RefCell::new(Node::new(0)));
    insert(&head, 1, 1);
    insert(&head, 2, 2);
    insert(&head, 3, 3);
    insert(&head, 4, 4);    

    assert_eq!(find(head.clone(), 3), Some(3));
    assert_eq!(find(head.clone(), 5), None);
    
}

[iLoveRatRace]

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

[yangkegithub]

在java中由于不考虑内存清理问题，所以，链表节点的删除，也可以直接如下：
if (n0 != null && n0.next != null) {
n0.next = n0.next.next;
}

[iLoveRatRace]

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

[tide-rhythm]

抱歉我也不太清楚，我之前在网页上留过言，但是之后不知道为什么一直会抄送，如果打扰到你真的抱歉 zhao ***@***.***

[jingningwang]

我不知道，好像是平台的设置，我个人没有抄送

…

-----原始邮件----- 发件人:HNUIsak ***@***.***> 发送时间:2025-09-25 17:34:09 (星期四) 收件人: krahets/hello-algo ***@***.***> 抄送: kang_wang ***@***.***>, Comment ***@***.***> 主题: Re: [krahets/hello-algo] chapter_array_and_linkedlist/linked_list/ (Discussion #83) 抱歉不好意思打扰一下 请问一下为什么我一直能收到来自您的抄送邮件呢？ 在 2025-09-24 17:18:53，"iLoveRatRace" ***@***.***> 写道： 感谢来信，你的邮件已经收到。 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***> — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***> Kang Wang Haiyun campus, Xiamen University, Siming District, Xiamen 361005 Department of Mathematical Sciences · Department of Information and Computational Mathematics · Laboratory Building 501 Phone: +86 184 5554 3368

[zhaoyinchen84-svg]

2025.10.20 打卡!

[iLoveRatRace]

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

[whiteOsky]

2025年10月21日21:54:53加油！

[zhunaoguozai1]

您好，想请问一下链表中结点指针指向的是下一个节点的首地址，还是下一个节点存放指针的位置，我看图4-5指向的是存放指针的位置，但是问AI说的是下一个节点的首地址

[JenyTone]

个人理解：节点A指针应该是指向节点B的首地址，这样才能访问到节点B的“值”和指向节点C的“引用”。如果直接指向节点B引用位置，可能会丢失节点B的“值”

[zhengads]

依旧是基础概念大概过一遍脑子，有个基本的了解先

[iLoveRatRace]

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