上一篇文章把数组算法进阶过了一遍有序数组的平方的双指针解法和长度最小的子数组的滑动窗口解法都捋清楚了。今天继续往下推进课程进入了链表部分主要讲了三块内容链表理论基础、移除链表元素和设计链表对应LeetCode上的203题和707题。链表和数组是两种最基本的数据结构它们在内存组织方式上有根本性的差异这也决定了它们各自适合不同的应用场景。先回顾一下链表的基本概念。线性表的链式存储结构是用一组任意的存储单元来存放线性表的数据元素这组存储单元可以是连续的也可以是不连续的。那么对于某一元素如何找到它的下一个元素的存放位置呢对每个数据元素ai除了存储其本身的信息之外还需存储一个指示其直接后继存放位置的指针。这两部分信息组成数据元素ai的存储映像称为结点。结点包括两个域存储数据元素信息的域称为数据域存储直接后继存放位置的域称为指针域。如果每个结点只设置一个指向其后继结点的指针成员这样的链表称为线性单向链接表简称单链表。如果每个结点中设置两个指针成员分别用以指向其前驱结点和后继结点这样的链表称之为线性双向链接表简称双链表。单链表的结点定义在Python中就是一个类包含data属性存储数据next属性存储指向下一个结点的指针。链表的头结点是第一个结点尾结点的next指向None。这种结构的核心特点是每个结点只知道自己的下一个结点是谁查找某个位置的元素必须从头开始逐个遍历。链表和数组的对比是一个重点。数组是连续空间优点是可以通过下标快速访问任何位置的元素时间复杂度O(1)但缺点是插入和删除操作需要移动大量元素时间复杂度O(n)。链表是非连续空间优点是插入和删除操作只需要修改指针不需要移动元素时间复杂度O(1)但缺点是查找元素必须从头遍历时间复杂度O(n)。这两种数据结构没有绝对的好坏取决于具体的应用场景。如果需要频繁随机访问数组更合适如果需要频繁插入删除链表更合适。移除链表元素这道题是LeetCode 203题题意是删除链表中等于给定值val的所有节点。示例1输入head [1,2,6,3,4,5,6]val 6输出[1,2,3,4,5]。这道题看起来简单但有一个重要的技巧就是使用虚拟头结点。因为链表的头结点可能被删除如果直接操作head指针删除头结点的情况需要单独处理。使用一个虚拟头结点dummy它的next指向真正的头结点这样所有节点的删除操作就统一了不需要单独处理头结点的情况。删除节点的核心操作是让当前节点的next跳过目标节点直接指向目标节点的next。遍历链表的时候检查当前节点的下一个节点的值是否等于val如果是就让当前节点的next指向下一个节点的next如果不是就继续往后移动。这样一趟遍历就能删除所有目标节点时间复杂度O(n)。设计链表这道题是LeetCode 707题是一个综合性更强的题目要求实现一个链表类支持获取第n个节点的值、头部插入节点、尾部插入节点、在第n个节点前插入节点、删除第n个节点这五个操作。这道题训练的是对链表基本操作的完整掌握。获取第n个节点的值需要从头开始遍历到第n个节点注意索引从0开始。循环for i in range(n)会执行n次指针从dummy开始移动n次后正好落在第n个节点上。头部插入节点就是在dummy和第一个节点之间插入一个新节点新节点的next指向原来的第一个节点dummy的next指向新节点。尾部插入节点需要先遍历到尾节点然后让尾节点的next指向新节点。在第n个节点前插入节点需要先找到第n-1个节点然后新节点的next指向第n个节点第n-1个节点的next指向新节点。删除第n个节点需要找到第n-1个节点然后让它的next指向第n个节点的next。这些操作的核心都是找到目标位置的前一个节点然后修改指针。对于头部的操作虚拟头结点再次发挥了重要作用它让头部插入和头部删除的操作和其他位置完全一致不需要特殊处理。把链表和前面学的数组放在一起看这两种数据结构是计算机科学中最基础的两种存储结构。数组的连续存储带来了随机访问的高效但也带来了插入删除的低效。链表的离散存储带来了插入删除的高效但也带来了随机访问的低效。在实际开发中Python的列表是动态数组的实现既保留了数组的随机访问优势又通过动态扩容解决了固定长度的问题所以大多数场景下直接使用列表就够用了。但理解链表的原理对于后续学习更复杂的数据结构至关重要。希望这篇文章能给正在入门链表同学一些参考有问题欢迎来交流。