大家好我是Tony Bai。欢迎来到我们的专栏 《AI 时代软件工程师的算法图谱》的第四讲。前三讲我们处理的都是数组Slice和字符串它们在内存中是连续的访问速度极快。但今天我们要进入一个“碎片化”的世界——链表Linked List。在现代高级编程如 Python/Java/Go 业务层中链表似乎不如数组常用。但在操作系统内核、内存分配器Malloc、Redis 底层Ziplist/Quicklist这些硬核领域链表是绝对的王者。它不需要连续内存插入删除极其灵活是连接离散数据的纽带。对于 Go 工程师来说理解链表不仅是为了刷题更是为了理解container/list标准库甚至是 Go Runtime 内部的mspan链表管理机制。今天我们将通过指针的“穿针引线”体验内存操纵的艺术。模式解构指针的“断与连”链表的核心在于节点Node与指针Pointer/Reference。每个节点包含数据和指向下一个节点的指针。操作链表时最容易犯的错误就是“断链”丢失了节点的引用和“成环”死循环。为了驾驭它我们需要掌握几个核心模式虚拟头节点 (Dummy Head)痛点处理头节点Head非常麻烦因为头节点没有“前驱节点”。删除头节点和删除中间节点的逻辑不一样。解法创建一个dummy节点指向head。这样所有业务节点都有了前驱逻辑统一。场景几乎所有链表题目删除、合并、反转。
