第3章 链表
3.1 链表基础与特性
在第2章所实现的三种线性结构：数组、栈，队列。我们好像都没怎么写代码，只不过给JavaScript数组的方法重新套了一层壳（添加限制）。虽然也理解这三种数据结构特性并清楚对应的应用场景，但依旧很难有足够的成就感（并没有从零实现数据结构），但接下来的链表学习中，我们会从零实现，并且不利用数组等现成数据，而是利用语言本身的特性（类、引用、指针等等）来实现链表结构。
3.1.1 数组的缺点
要存储多个元素，数组（或选择链表）可能是最常用的数据结构，在第2章我们有说过，几乎每一种编程语言都有默认实现数组结构。但数组也有很多缺点，在2.1.2小节中有说明，数组中插入元素会导致后续所有元素都需要向后移动，产生大量数据搬迁的开销，因此在数组的开头或者中间位置插入数据的成本很高。
而且数组的创建通常需要申请一段连续的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当目前数组不能满足容量需求时，需要扩容（一般情况下是申请一个更大的数组，比如2倍。 然后将原数组中的元素复制过去）。
但在JavaScript中使用数组上好像不是固定的，开发者可以创建一个数组，然后随时往数组内添加数据，从这一角度来看，数组的大小并不是固定的，而是由开发者决定填入数据来决定。数组实际大小由开发者决定是一个错觉，开发者判断数组大小的方式是通过数组内的元素个数，而不是内存空间，这是视角上的问题。因为数组已经被JavaScript封装起来了，所以开发者是感知不到数组底层内存的变化的，而JavaScript数组底层依旧是申请一段连续固定大小的内存空间，元素个人达到临界点后就扩容。
由于JavaScript数组实际大小由内存空间决定，因此数组是可以在连续的内存空间中间选择空着不填入任何元素，这并不会导致后续元素往前列空余槽进行填补操作。空着的内存槽会一直空着，位置也会一直占据着，这被称为空槽，有空槽的数组被称为稀疏数组。稀疏数组在面对迭代方法时会被直接跳过，与用undefined值填充的槽不一样。
▼js复制代码const names = [] // 开发者感知的数组大小是逻辑长度，引擎管理的是物理容量 names.push("小余")
JavaScript数组底层扩容原理：
（1）检查容量：当 length >= capacity 时触发扩容。
（2）计算新容量：通常按一定比例增长（常见策略：newCapacity = oldCapacity * 1.5 + 16）。
（3）分配新内存：申请更大的连续内存空间。
（4）复制元素：将旧数组元素复制到新内存。
（5）更新引用：将内部指针指向新内存块。
在前面说明了数组存在稀疏数组的情况，而没有空槽的数组被称为密集数组。两种不同类型的数组有不同的存储策略，其中密集数组采用连续内存存储。但极度稀疏的数组（空闲内存位置一直被占据）会导致内存的浪费，因此现在JavaScript引擎的V8引擎面对该情况会采用更复杂的策略，即转为哈希表存储，哈希表会在第4章学习。
尽管JavaScript的Array底层可以帮我们做申请内存空间以及搬迁元素等事，不需要我们手动去操作，但数组背后的原理依然是这样。
3.1.2 链表的定义与优势
要存储多个元素，另外一个选择是链表。链表不同于数组，链表中的元素在内存中不必是连续的空间。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些编程语言称为指针或者链接)组成。
相对于数组，链表有以下3个优点：
（1）内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
（2）链表不必在创建时就确定大小，并且大小可以无限的延伸下去。
（3）链表在插入和删除数据时，时间复杂度可以达到O(1)，链表相对数组效率高很多。
但相对于数组，链表也有以下两个缺点：
（1）链表访问任何一个位置的元素时，都需要从头开始访问。(无法跳过第一个元素访问任何一个元素)。 （2）无法通过下标直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
3.1.3 链表究竟是什么？
在图2-2的数组与链表对比中，我们简单的提过了链表的结构，大致了解链表的形象，但在此处会更详细的说明。
链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客(类似于数据)，并且这个节点会连接下一个节点，以此类推，链表组成三部分如图3-1所示。
图3-1 链表组成三部分
链表主要由以下3部分组成：
（1）链节点（Node）：链表的基本单元，每个节点包含数据（Data）与指针（Pointer）。
- 数据（Data）：存储实际的数据，可以是任意类型，通常以指代称呼为item。
- 指针（Pointer）：指向下一个节点（在双向链表中还包括指向前一个节点的指针），通常称呼为next指针。
（2）头节点（Head）：指向链表的第一个节点。通过头节点可以遍历整个链表。
（3）尾节点（Tail）：链表的最后一个节点。在单向链表中，尾节点的指针通常指向null（或None等，表示空）。在双向链表中，尾节点的下一个指针为null，同时它还有一个指向前一个节点的指针。
链表由节点组成，我们根据位置因素将链表区分为三部分组成，即头节点、链节点以及尾节点。最需要注意的是头节点与尾节点：
- 头节点：不存储实际数据，只存储指向第一个链节点的引用。
- 尾节点：与链节点一致，也存储实际数据，特殊点在于尾节点的next指针指向null，表示链表结束。
链表对应信息获取在代码中的表现形式如下：
▼ts复制代码// 当前节点 node // 下一个节点 node.next // 下一个节点的值 node.next.item
3.2 链表的实现与封装
根据3.1小节了解了链表的基础特性，如果我们也想要自己实现一个链表，要从哪里入手？我觉得先把思路理清楚，把步骤列出来后再来实现会更好。
首先，已知链表由三部分组成，其中头节点，链节点与尾节点的本质是一样的，由数据+指针组成。而数据+指针的组合被称为节点，因此我们需要一个类来封装节点，实现快速重复创建节点，其中数据与指针都应该允许存在null的情况，因为头节点与尾节点分别在数据与指针分别为null。
其次，我们需要将链表串联起来，如果我手动一个个的创建节点，再手动的将节点们串联起来，这其中会多出很多重复的代码工作量，节点越多，串联链表的人工成本就会愈发沉重，这不符合封装抽象的计算机思想，因此还需要一个类，这个类要负责自动化组建链表，我们只需要将数据传递进去，该类就会负责将节点们联系在一起成为链表。
思路理清楚了，我们需要两个类，分别是节点类与链表类。
根据以上思路，我应该做出以下3个步骤：
（1）封装两个类。封装一个Node类，用于封装每一个节点上的信息（包括值和指向下一个节点的引用），它是一个泛型类；封装一个LinkedList类，用于表示我们的链表结构。 (和Java中的链表同名，不同Java中的这个类是一个双向链表，在第7章中我们也会实现双向链表结构)。
（2）结合两个类的联动。链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点。在链表类中实现将节点组成链表的方法。
（3）实现链表后，实现链表身上的常见操作方法。
3.2.1 节点类的封装
节点类如何封装？一个节点有数据和指针两个数据，因此我们以value和next两个属性来表示对应数据。
▼ts复制代码// 创建Node节点类 class Node<T> { value: T next: Node<T> | null=null } export {}
我们知道在JS或者TS中，复杂数据类型是引用传递的，因此Node实际只是一个引用（内存地址），也就是指针，指向下一个节点，当我们不再创建新的Node类之后，最后节点的next指针就无法指向到新的节点，而是指向null（初始化值）。PS：Node 在类型层面表示"Node 类型的实例"。
▼ts复制代码内存地址: 0x1000 内存地址: 0x2000 +-------------+ +-------------+ | value: 1 | | value: 2 | | next: -------->------| next: null | +-------------+ +-------------+ node1 node2
目前next属性有初始化值null，value属性是没有初始化值的（类属性必须要有初始化值），可value属性要什么初始化值呢？要设为null吗？但next属性可以固定为 null，因为它表示"没有下一个节点"的概念是通用的。可value属性的类型是泛型T，可能是任何数据类型，没有通用的"空值"能适配所有类型，链表节点的核心就是存储特定类型的值，这个值必须由使用者提供才有意义，因此必须通过构造函数来接收具体的值，而不是预设固定值。
无论什么初始化值都不合适，无法应对所有的情况，因此我们将决定权交给使用节点的开发者。我们使用构造函数，要求开发者在使用时需要传入一个值进来，在传入值的同时，也设置了对应的泛型或者由编辑器自动推导类型。
▼ts复制代码// 创建Node节点类 class Node<T> { value: T next: Node<T> | null = null constructor(value: T) { this.value = value } } export { }
3.2.2 链表类的创建
接下来我们创建LinkedList的类（链表类），在3.2.1的节点创建中，未涉及到头节点，因为头节点不在数据+指针形式的节点范围内。头节点是链表类中很重要的属性，其接收值就是节点的内存地址。由于类的属性必须赋值，因此我们为头节点设置null的默认值，当未使用头节点，默认值就为null。
有时候会求链表的长度，因此我们添加一个size属性。
▼ts复制代码class LinkedList<T> { private head: Node<T> | null = null private size: number = 0 }
到目前为止，节点类与链表类都创建完成，但目前链表类并不完整，因为目前的链表类实际上只等于头节点。缺少了将头节点与链节点和尾节点组合成链表的实例方法。
3.3 链表常见操作方法
接下来我们在链表类中实现将节点组成链表的实例方法。链表的本质是以头节点为主，往后不断追加节点所形成的链条。因此链表的形成实际指追加节点的方法。
- append(value)：向链表尾部添加一个新的项。PS：将节点组成链表的方法，即追加节点方法。
除此之外，我们还需要实现链表身上的一些常见操作方法（实例方法），包括以下8点：
（1）insert(position，value)：向链表的特定位置插入一个新的项。
（2）get(position) ：获取对应位置的元素
（3）indexOf(value)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
（4）update(position，value) ：修改某个位置的元素。
（5）removeAt(position)：从链表的特定位置移除一项。
（6）remove(value)：从链表中移除一项。
（7）isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
（8）size()：返回链表包含的元素个数。与数组的length属性类似。
整体我们发现操作方法和数组非常类似，因为链表本身就是一种可以代替数组的结构。
3.3.1 追加节点方法
缺乏追加节点方法会导致LinkedList类无法使用，无法传入节点，就会令头节点无意义（无法指向第一个链节点），size属性也一直为0无法利用，此时哪怕将head属性与size属性暴露出去，也缺乏使用价值。
▼ts复制代码const linkedList = new LinkedList<string>() // linkedList.xxx() 没有方法调用
因此我们需要立刻实现追加节点方法，后续链表所有常见操作方法都需要建立在有链表的基础上。
追加节点方法实现步骤如下：
（1）创建append()实例方法，能够传入节点参数。
（2）在方法中向链表尾部追加数据。
向链表尾部追加数据可能有两种情况：
（1）若链表本身为空，那此时需要添加头节点。
（2）若链表不为空，则需要向尾节点后面追加节点。
向链表尾部追加数据的第1种情况是需要我们去判断的，而第二种情况则与数组的Array.prototype.push()实例方法类似，只不过不需要返回数据。此时需要注意，我们链表是从零实现，而不是基于数组实现的，因此我们没办法直接往append()实例方法中套壳使用数组的push()实例方法。但这不正是我们所期待的吗？由我们自己来实现，所获得的成就感一定会更让人满足。
现在先来处理情况1，判断链表本身是否为空，决定是否添加头节点。但是，添加头节点是有前置条件的，头节点只有在传入第一个链节点后才有价值，即头节点指向第一个链节点。
所以我们需要第一个链节点，即创建 Node 类的一个实例对象，然后将该Node类的实例对象newNode赋值给头节点，即头节点获得了newNode实例对象的内存地址，头节点指向了newNode实例对象。
▼ts复制代码// 追加节点方法 append(value: T) { const newNode = new Node(value) this.head = newNode }
接下来我们需要添加限定判断，头节点指向第一个链节点只有在链表为空时才进行，否则会导致后续节点不断地赋值给头节点。但我们要如何判断链表为空？当不再以数组为基底，失去数组自带的方法后，我们就需要"赤手空拳"去面对这些情况。
在链表中，我们需要一个类似数组下标的东西来锁定链表的位置。这是一个很好的思路，不过暂时还不需要。判断链表为空是可以通过判断头节点是否为null来操作的。因为链表的唯一入口就是头节点引用。
- 如果head属性为null，说明没有任何节点存在。
- 如果head属性不为null，说明至少存在一个节点。
▼ts复制代码// 追加节点方法 append(value: T) { const newNode = new Node(value) // 判断头节点为空 if (!this.head) this.head = newNode }
接下来处理向链表尾部追加数据（节点）的第2种情况，想做到正确追加数据，我们需要能够拿到链表的最后一个节点的位置。在数组中可以使用Array.prototype.at(-1)或者length-1来实现。如果交由我们来实现，要怎么做？
判断是否为链表的最后一个节点，实际是在判断尾节点，因此需要判断next属性是否为null就行。无论是通过while循环语句还是使用递归来找到尾节点都可以，但这会造成性能的损耗，尤其是递归有栈溢出的风险。
我们暂时使用while循环语句来实现：
使用临时变量current记录头节点指针信息，然后通过while循环语句不断的执行查找下一个节点，直到节点的next属性为null时，说明已经找到最后一个节点。将最后一个节点指向新的节点，完成节点追加。节点追加原理如图3-2所示。
图3-2 节点追加原理
最后，每追加一次节点，我们就将size属性自增1，确保能获取到链表的长度。
▼ts复制代码// 追加链表节点方法 append(value: T) { const newNode = new Node(value) if (!this.head) { this.head = newNode } else { let current = this.head // 寻找链表的最后一个节点 while (current.next) { current = current.next } // 追加节点 current.next = newNode } this.size++ }
追加节点操作是链表最频繁的操作之一，因此我们需要从优化的角度去考虑，维护一个临时的指针就很有必要了。我们维护一个tail指针作为链表的属性，这样在追加节点时就不需要每次遍历整个链表。非空链表时直接通过tail指针操作，时间复杂度从 O(n) 降为 O(1)。每次追加后更新tail指针，确保它始终指向链表尾部。
该优化操作主要分两步：
（1）将尾节点指向新节点，实现节点追加。
（2）更新tail指针，指向新的尾节点。
节点追加优化原理如图3-3所示。
图3-3 节点追加优化原理
▼ts复制代码class Node<T> { value: T next: Node<T> | null = null constructor(value: T) { this.value = value } } class LinkedList<T> { private head: Node<T> | null = null private tail: Node<T> | null = null; // 新增尾指针 private size: number = 0 get length() { return this.size } // 追加节点方法 append(value: T) { const newNode = new Node(value) if (!this.head) { // 空链表：头尾指针都指向新节点 this.head = newNode; this.tail = newNode; } else { // 非空链表：通过尾指针直接追加，无需遍历 this.tail!.next = newNode; // 当前尾节点指向新节点 this.tail = newNode; // 更新尾指针为新节点 } this.size++ } } // 测试代码 const linkedList1 = new LinkedList<string>() linkedList1.append("aaa") linkedList1.append("bbb") linkedList1.append("ccc") export { }
该优化做法完美利用指针特性， this.tail!.next = newNode做到修改当前尾节点的next属性，将null修改为新添节点，实现节点追加。精髓之处在于this.tail = newNode的做法，由于newNode包含一整个节点，即value属性和next属性，因此复杂数据类型存储在堆空间中，赋值给this.tail的是一个内存地址，而不断的替换内存地址并不会实际修改该内存地址所对应的堆空间中的数据，因此替换内存地址的过程与图3-2所示的移动current变量是一样的，区别在于优化做法不需要每次都重新重头遍历而已。
▼ts复制代码执行前： tail → [节点C] (对象地址: 0x1000) [节点C].next = null 执行 this.tail!.next = newNode; 后： tail → [节点C] (地址: 0x1000) [节点C].next → [新节点D] (地址: 0x2000) ← 修改的是节点对象的属性 执行 this.tail = newNode; 后： tail → [新节点D] (地址: 0x2000) ← 修改的是LinkedList类的属性 [节点C].next 仍然指向 [新节点D] (地址: 0x2000)
以上是追加节点的写法以及优化方法，通过追加节点的方法，链表已经成型。接下来我们开始实现链表应该具备的方法吧、
3.3.2 遍历链表方法
在实现追加节点方法后，我们发现了无法查看链表效果，这令我们苦恼，怎么看效果对不对呢？这时候就需要一个遍历链表的方法，遍历的过程中将所有的节点数据打印到控制台中。这个想法不错，并且在刚才的追加节点方法中，我们已经实现过了。
设置临时指针current，起始位置为头节点，沿着链表的next属性指针不断遍历调用，直到尾节点为止，在遍历过程顺便把节点的value属性打印到控制台中。
▼ts复制代码// 遍历链表的方法 traverse() { let current = this.head while (current) { console.log(current.value); current = current.next } }
遍历链表方法效果如图3-4所示。
图3-4 遍历链表方法效果
以上打印效果是一行一个节点数据，当节点数据一多，这种一行打印一节点的效果就不太直观，比较浪费显示的空间。那我们只需要将每次遍历的value属性存入数组中，然后直接打印数组就行，想要其他效果可以使用数组的拼接方式，根据实际情况决定就行。
▼ts复制代码// 遍历链表的方法 traverse() { let current = this.head let arr = [] while (current) { arr.push(current.value) current = current.next } // 数组展示形式 console.log(arr); // 数组拼接形式 console.log(arr.join(', ')); // 其余拼接形式 console.log(arr.join(' -> ')); }
遍历链表效果展示形式如图3-5所示。
图3-5 遍历链表效果展示形式
有了traverse()遍历链表方法，后续就能测试其余链表方法的效果变化，进而去纠正不正确的地方。
3.3.3 插入节点方法
绝大多数的操作数据方式离不开四个字：增删改查。对应了添加新节点、移除已有节点、修改已有节点以及查询节点。每种方式都可延伸出不少方法。例如添加新节点，添加在尾节点后，那是3.3.1实现的追加节点方法，添加在任意地方，是我们即将实现的插入节点方法。而想要添加在任意地方，就需要定位对应的位置。我们能通过size属性或者节点的具体value属性来实现，这对应了两种不同思路。
插入与替换的思路不同，替换直接覆盖原有数据就行。而单向链表的插入需要3步：
（1）找到插入位置的前节点。
（2）新节点指向后节点（newNode.next = prevNode.next）。
（3）前节点指向新节点（prevNode.next = newNode）。
而且如果想要在"任意位置"插入节点，则需要考虑一些边界情况。例如尾节点没后节点。我们采用长度位置的方式来插入节点，那么实现插入节点方法需要两个参数：插入数据，插入位置。以及告诉我们是否插入成功，因此需要返回一个布尔值来提示。
那么开始吧，我们创建insert()方法，设定好参数值以及对应的类型提示，将方法模板搭建出来。
▼js复制代码// 任意位置插入节点 insert(value: T, position: number): boolean { }
接着实现插入的逻辑：
插入节点方法步骤1：判断边界情况，插入位置只能在已有的位置插入，例如第一个链节点至尾节点的范围，超出该返回的插入应该直接返回false或者抛出异常（插入失败）。大家觉得是返回false更好还是抛出异常更好？
抛出异常是更规范的做法，提供的错误信息也更多，但同时由于抛出的是一个异常，如果开发者没有使用try...catch接住异常，那么代码就会报错，进而导致程序崩溃。而JavaScript是一门自由弹性的语言，通常是允许一定范围内的错误存在，不至于因为一些错误而直接导致程序无法运行，因此返回布尔值提醒开发者这里有问题是更好的选择。
▼ts复制代码// 任意位置插入节点 insert(value: T, position: number): boolean { // 1、越界的判断 if (position < 0 || position > this.size) return false }
插入节点方法步骤2：判断插入情况。有以下2种情况：插入到第一个位置，插入到其他位置。
（1）插入到第一个位置。添加到链表的第一个位置，即第一个链节点（PS：头节点是固定的哨兵节点，不会被替换）。该情况很特殊，需要先将插入节点的next指针属性指向原来的第一个链节点，再将头节点的next指针指向新节点。顺序不能反，否则从原有第一个链节点及之后的数据会丢失。插入节点丢失数据情况对比如图3-6所示，当头节点先指向后，从原有的第一个链节点开始到尾节点，成为了一块单独的孤岛。
图3-6 插入节点丢失数据情况
▼ts复制代码head.next = newNode; // 头节点指向新节点 // 造成了数据丢失和循环引用 newNode.next = head.next; // 新节点指向自己（形成环）后续数据丢失
PS：我们学习的是带头节点的链表设计，即头节点是"哨兵节点"，不存储实际数据，第一个实际数据节点是 head.next，头节点只包含指向第一个实际节点的指针。除此之外还有不带头节点的链表，即head属性直接指向第一个包含实际数据的节点，没有专门的"哨兵"头节点，每个节点都包含数据和指针。哨兵节点是数据结构中一个特殊的辅助节点，它不存储实际的有效数据，主要用于简化边界条件的处理和避免空指针异常，我们在操作数据时会直接忽略哨兵节点。
▼ts复制代码insert(value: T, position: number): boolean { // 1、越界的判断 if (position < 0 || position > this.size) return false // 创建节点 const newNode = new Node<T>(value) // 2、插入到第一个链节点 if (position == 0) { // 先将新节点指向第一个链节点 newNode.next = this.head this.head = newNode } return true; } // 测试代码 // 测试代码 const linkedList = new LinkedList<string>() linkedList.append("aaa") linkedList.append("bbb") linkedList.append("ccc") linkedList.insert('coderwhy', 0)
（2）插入到其他位置。如果是添加到其他位置，就需要先找到这个节点位置了。我们通过while循环，一点点向下找。 并且在这个过程中保存上一个节点和下一个节点。找到正确的位置后，将新节点的next属性指向下一个节点，将上一个节点的next属性指向新的节点。
插入到其他位置，我们先采用一个具体的案例来模拟，这有助于我们理解实现。假设我现在要在链表第二个位置插入数据，我传入了两个参数，第一个参数为数据"xiaoyu"，第二个参数为插入的位置。
▼ts复制代码linkedList.insert('xiaoyu', 2)
我需要实现的步骤是：利用第二个参数找到插入位置然后插入数据。
使用了临时指针变量current用于遍历链表。通过类似size属性与开发者传入的position（第二参数）对比判断是否找到正确的插入位置。最后将数据插入即可。由于size属性是用于记录链表长度的，因此我们在插入节点方法中创建一个index变量，在current遍历的过程中，index变量也不断自增，起到与size属性同样的效果，用于记录遍历链表的情况。当index与position一致后，说明找到插入位置了。
▼ts复制代码// 找到插入位置 let index = 0 let current = this.head // 例：position为3。index为2是通过判断的最后数字，实现获取2的下一位3。 while (index++ < position && current) { current = current.next }
此时的current指针已经指向正确的插入位置，然后我们应该插入数据。但插入数据需要将新节点的next属性指向下一个节点，将上一个节点的next属性指向新的节点。我们拿到了下一个节点的位置，但还没拿到上一个节点的位置，所以我们再定义一个节点变量previous用于获取上一节点，变量previous默认为null，因为当我们要插入第一个位置，即position=0时，没有前驱节点。
我们使用previous获取到上一节点（前驱指针）后，再将current变量指向position位置的当前节点（当前指针）。此时就同时获取到两个节点。这里采用的是双指针写法，后续会使用单指针重构。
▼ts复制代码let index = 0 let previous: Node<T> | null = null let current = this.head while (index++ < position && current) { // 前驱指针 previous = current // 当前指针 current = current.next }
当我们拿到前驱节点与当前节点后，我们要用新节点插入当前节点。即前驱指针指向新节点，而新节点的next指针指向原来的当前节点（current），原来的当前节点（current）现在成为新节点的后继节点。
这里插入新节点的指针指向先后顺序是不作要求的，谁先谁后都行。这是因为我们已经保存了前一个节点previous和当前节点current的引用，无论先连接新节点到当前节点，还是先改变前一个节点的指向，都不会造成另一个节点的丢失。
▼ts复制代码let index = 0 let previous: Node<T> | null = null let current = this.head while (index++ < position && current) { previous = current current = current.next } // 插入新节点 previous!.next = newNode newNode.next = current
现在，我们来验证是否能够成功插入数据（位置从0开始）：
- 原数据：coderwhy -> aaa -> bbb -> ccc。
- 输出数据：coderwhy -> aaa -> xiaoyu -> bbb -> ccc。
▼ts复制代码class Node<T> { value: T next: Node<T> | null = null constructor(value: T) { this.value = value } } class LinkedList<T> { private head: Node<T> | null = null private size: number = 0 get length() { return this.size } // 插入节点方法 insert(value: T, position: number): boolean { // 1、越界的判断 if (position < 0 || position > this.size) return false // 创建节点 const newNode = new Node<T>(value) // 2、插入到第一个链节点 if (position == 0) { newNode.next = this.head this.head = newNode } else { let index = 0 let previous: Node<T> | null = null let current = this.head while (index++ < position && current) { // 前驱指针 previous = current // 当前指针 current = current.next } previous!.next = newNode newNode.next = current } this.size++ return true; } } // 测试代码 const linkedList = new LinkedList<string>() linkedList.append("aaa") linkedList.append("bbb") linkedList.append("ccc") linkedList.insert('coderwhy', 0) linkedList.insert('xiaoyu', 2) linkedList.traverse() export { } // 控制台输出：coderwhy -> aaa -> xiaoyu -> bbb -> ccc
如果要插入数据到尾部，previous会指向尾节点，而current会指向null。此时新节点会取代null原先的位置然后指向null，尾节点会指向新节点。此时原先的尾节点的next属性不在为null，而新节点的next属性为null然后成为新的尾节点。插入到尾部就是最后的情况了，如果再往后插入就会触发一开始的越界判断而直接返回false。
▼ts复制代码// 初始状态 previous → 尾节点 → null current → null // 插入操作 previous!.next = newNode // 尾节点指向新节点 newNode.next = current // 新节点指向null（因为current是null）
3.3.4 移除节点方法
假如我们想要移除头节点之外的任意一个节点，我们需要怎么做？怎么插入节点的，就能反着过来怎么移除。
因此移除节点B的方法需要以下步骤（假设有连续节点A、B、C）：
（1）获取前驱节点A与当前节点B。
（2）前驱节点A的next指针指向后续节点C。
移除节点所需步骤图如图3-7所示。
图3-7 移除正常节点示意图
好的，让我们开始实现removeAt()移除节点方法吧！移除节点，我们要和3.3.3小节的以第几个节点为目标的删除还是以数据内容为主的删除？其实都可以，这对应移除数据的两种常见方式：
-
根据位置移除对应的数据。
-
根据数据，先找到对应的位置，再移除数据。
我们根据数据来找到对应数据再移除数据的话，通常需要3个步骤：
（1）遍历链表，通过数据之间的比对判断，找到当前需要移除节点。
（2）在获取当前需要移除的节点之前，先获取前驱节点。
（3）在需要移除的位置，将前驱节点直接指向后继节点，然后return返回，跳出循环。
▼ts复制代码removeAt(value: T) { let current = this.head // 获取前驱节点 let previous: Node<T> | null = null while (current) { // 找到需要移除数据的位置，将前驱节点指向后继节点 if (current.value === value) return previous!.next = current.next // 获取前驱节点 previous = current // 移动current，直到找到需要移除数据的位置 current = current.next } } // 测试代码 const linkedList = new LinkedList<string>() linkedList.append("aaa") linkedList.append("bbb") linkedList.append("ccc") // 移除bbb linkedList.removeAt('bbb')
以上是最精简的模式，没有考虑各种边界判断，接下来，我们根据位置移除对应数据再实现一次，并且附加各种边界判断。
越界判断：移除数据需要在链表范围内的数据，开发者传入的位置不能超出链表范围，即位置范围为第一个链节点到尾节点，超出范围直接返回null。
▼ts复制代码removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null }
移除节点利用位置信息，则需要一个"临时索引"。与3.3.1小节使用current遍历链表一致，在遍历链表的过程中使临时索引从0开始自增，当索引与开发者传递的位置信息一致时，说明移除元素的位置找到了。
▼ts复制代码// 移除节点方法 removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null // 创建临时索引 let index = 0 // 创建遍历指针 let current = this.head // 前驱节点 let previous: Node<T> | null = null while (index++ < position && current) { // 找到位置 } }
然后获取前驱节点和当前节点，将前驱节点的next指针指向后续节点就完成移除当前节点。后继节点需要考虑尾节点的情况，即尾节点没有后继节点的话就置为null。
▼ts复制代码// 移除节点方法 removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null // 创建临时索引 let index = 0 // 创建遍历指针 let current = this.head // 前驱节点 let previous: Node<T> | null = null while (index++ < position && current) { // 获取前驱节点 previous = current // 获取当前节点 current = current.next } // 前驱节点指向后继节点 previous!.next = current?.next ?? null return current?.value ?? null }
接着，我们来处理头节点的特殊情况，如果我们想移除第一个链节点（position等于0）。只需要直接头节点指针指向第二个链节点，使第二个链节点成为新的第一链节点。那么原来的第一个链节点没有引用指向后，就在链表中不再有效，后面会被回收掉。
▼ts复制代码// 删除方法 removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null let current = this.head if (position === 0) { // 处理头节点的特殊情况 this.head = this.head?.next ?? null // 头节点指针指向由第一个链节点转为第二个链节点 } else { let index = 0 let previous: Node<T> | null = null while (index++ < position && current) { previous = current current = current.next } previous!.next = current?.next ?? null } // 最后确定删除一个节点之后，将链表长度-1 this.size-- return current?.value ?? null }
头节点的特殊情况，即移除第一个链节点的原理图如图3-8所示。
图3-8 移除第一个链节点的原理图
因此删除节点实际是令要被删除的节点（假设节点B）处于没有任何活跃的引用指向它，哪怕节点B仍然存在。此时从链表的头节点开始遍历，无法到达节点B，在支持垃圾回收的JavaScript或者TypeScript语言中，节点B会被自动回收，就相当于删除了。
3.3.5 查找与更新方法
接着实现链表的查找方法，即查找节点位于链表中的位置来获取数据。这个过程类似于通过数组的下标获取数组对应位置的数据，即数组索引：arr[下标]。当然，数组除了能通过下标之外，还可以通过其他方式（变量、表达式、函数调用、常量）获取信息，有兴趣的可以课外尝试。
查找方法需要我们传入位置参数，通过current遍历链表，获取要查找的节点后，返回节点的数据。该思路与3.3.4小节中的移除节点前半部分思路一致，不再重复赘述。
▼ts复制代码// 查找节点数据方法 get(position: number): T | null { if (position < 0 || position >= this.size) return null let index = 0 let current = this.head while (index++ < position && current) { current = current.next } return current?.value ?? null } // 测试代码 const linkedList = new LinkedList<string>() linkedList.append("aaa") linkedList.append("coderwhy") linkedList.append("ccc") console.log(linkedList.get(1)); // coderwhy
3.3.6 重构方法
插入节点、移除节点、查找节点方法都用到了current遍历节点的做法，这是有共通之处的，即通过一个索引和遍历去获取链表中的某一样内容（数据或者指针）。因此我们可以将遍历节点的重复代码抽离为一个单独的方法getNode()，然后在插入节点、移除节点、查找节点方以及后续更多的方法中调用getNode()方法就行。
▼ts复制代码// 插入节点方法 let index = 0 let previous: Node<T> | null = null let current = this.head while (index++ < position && current) { previous = current current = current.next } // 移除节点方法 let index = 0 let current = this.head let previous: Node<T> | null = null while (index++ < position && current) { previous = current current = current.next } // 查找节点数据方法 let index = 0 let current = this.head while (index++ < position && current) { current = current.next }
getNode()方法是一个私有的方法，只允许链表内部的方法调用，不允许外部调用。防止外部直接操作节点，从而破坏链表的结构。如果外部可以获取到节点，那么他们就可以修改节点的next指针，这可能会造成链表断裂或循环。
对于这类抽离的公共方法，一般放于类中的最上层或者最下层，与其他正常方法区分开。通常放于类中的最上层会更好，因为后续添置方法或者其余内容往往从最下层代码继续往下写，每次书写代码都需要顾及抽离的公共方法，以免将公共方法夹到正常方法的中间去。
getNode()方法需要实现的是根据position（开发者传递的位置信息）获取到当前的节点本身。获取节点本身可以得到最多的信息量，开发者可以根据更多的信息量去选择自己所需的部分。
▼ts复制代码private getNode(position: number): Node<T> | null { let index = 0 let current = this.head while (index++ < position && current) { current = current.next } return current }
此时我们就可以重构插入节点、移除节点、查找节点数据方法这三个方法，查找节点数据方法对应操作如下：
▼ts复制代码// 查找节点数据方法 get(position: number): T | null { if (position < 0 || position >= this.size) return null // 遍历节点 查找节点 return this.getNode(position)?.value ?? null }
移除节点稍有不同，除了获取到当前节点，还需要获取到当前节点的前驱节点。但这一点并不困难，我们只需要将position-1，然后基于该位置调用一次获取节点的getNode()方法就能拿到前驱节点。
▼ts复制代码// 移除节点方法 removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null let current = this.head if (position === 0) { this.head = this.head?.next ?? null } else { // 获取前驱节点 const previous = this.getNode(position - 1) current = previous!.next previous!.next = current?.next ?? null } this.size-- return current?.value ?? null }
插入节点方法同样需要用到前驱节点，因此也是通过position - 1获取当前节点的前驱节点。
▼ts复制代码// 插入节点方法 insert(value: T, position: number): boolean { // 1、越界的判断 if (position < 0 || position > this.size) return false // 创建节点 const newNode = new Node<T>(value) // 2、插入到第一个链节点 if (position == 0) { newNode.next = this.head this.head = newNode } else { const previous = this.getNode(position - 1) newNode.next = previous!.next previous!.next = newNode } this.size++ return true; }
通过重构代码，我们三个方法的代码质量与代码精简度都得以提升，但什么时候我们需重构代码呢？重构代码不是一开始就要重构的，尤其是当我们对代码还没那么了解熟悉的时候。随着所写的代码越来越多，你会察觉到，这段代码的出现频率是不是有点高了，那这时候就可以将其抽离出来进行复用。编写代码与重构代码是一个螺旋上升的过程，两者谁都无法取代谁，优美且模块化程度极高的代码也是从毛胚开始的。当我们有经验之后，下一次编写代码的起点就会更高，这次的终点有可能就是下一次的起点，哪怕是Vue.js框架也避免不了整体重构代码，我们此刻所见的很多代码，背后都凝聚了很多次的思考，如果我们也经历过，那么也能感受到这份代码背后的开发者都在想什么。
3.3.7 其他工具方法
接着我们还实现了update()方法、indexOf()方法、remove()方法以及isEmpty()方法。
- update(position，element) ：修改某个位置的元素。
update()方法接收两个参数：位置信息，替换位置数据的新数据。首先我们匹配开发者传递的位置信息和链表的节点位置，找到位置之后，直接把节点中的数据赋值新数据，就完成替换掉的工作了。
▼ts复制代码// 更新元素方法 update(value: T, position: number) { if (position < 0 || position >= this.size) return const current = this.getNode(position) if (current) { current.value = value } }
- indexOf(value)：获取某个元素的位置。
indexOf()方法与Array.prototype.indexOf()类似，会返回链表中第一次出现给定元素的位置信息，如果不存在则返回 -1。依旧使用current临时指针，遍历链表，将链表中的value与开发者传递的value对应匹配，直到匹配上或者遍历链表结束还未找到返回-1。
▼ts复制代码// 获取元素的位置 indexOf(value: T): number { let index = 0 let current = this.head while (current) { if (current.value === value) return index index++ current = current.next } return -1 }
- remove(value)：通过节点数据移除链表中具体的节点。
有了上面的indexOf()方法，我们可以非常方便实现根据value数据来获取对应的节点信息位置，然后根据信息位置调用之前实现的removeAt()方法移除节点。
▼ts复制代码// 根据元素删除 remove(value: T): T | null { const index = this.indexOf(value) return this.removeAt(index) }
- isEmpty()：判断单链表是否为空。
▼ts复制代码isEmpty() { return this.size === 0 }
好的，到目前位置，我们就完成了一整个链表的从零实现，以下提供完整的最终链表实现方案以及测试案例，大家可以将其中的测试案例运行在自己实现的链表中，用于检测自己的链表代码是否有错误的地方。、
▼ts复制代码class Node<T> { value: T next: Node<T> | null = null constructor(value: T) { this.value = value } } class LinkedList<T> { private head: Node<T> | null = null private size: number = 0 get length() { return this.size } // 私有方法 private getNode(position: number): Node<T> | null { let index = 0 let current = this.head while (index++ < position && current) { current = current.next } return current } // 追加节点方法 append(value: T) { const newNode = new Node(value) if (!this.head) { this.head = newNode } else { let current = this.head // 寻找链表的最后一个节点 while (current.next) { current = current.next } // 追加节点 current.next = newNode } this.size++ } // 遍历链表方法 traverse() { let current = this.head let arr = [] while (current) { arr.push(current.value) current = current.next } // 其余拼接形式 console.log(arr.join(' -> ')); } // 插入节点方法 insert(value: T, position: number): boolean { // 1、越界的判断 if (position < 0 || position > this.size) return false // 创建节点 const newNode = new Node<T>(value) // 2、插入到第一个链节点 if (position == 0) { newNode.next = this.head this.head = newNode } else { const previous = this.getNode(position - 1) newNode.next = previous!.next previous!.next = newNode } this.size++ return true; } // 移除节点方法 removeAt(position: number): T | null { if (position < 0 || position >= this.size) return null let current = this.head if (position === 0) { this.head = this.head?.next ?? null } else { // 获取前驱节点 const previous = this.getNode(position - 1) current = previous!.next previous!.next = current?.next ?? null } this.size-- return current?.value ?? null } // 查找节点数据方法 get(position: number): T | null { if (position < 0 || position >= this.size) return null // 遍历节点 查找节点 return this.getNode(position)?.value ?? null } // 更新元素方法 update(value: T, position: number) { if (position < 0 || position >= this.size) return const current = this.getNode(position) if (current) { current.value = value } } // 获取元素的位置 indexOf(value: T): number { let index = 0 let current = this.head while (current) { if (current.value === value) return index index++ current = current.next } return -1 } // 根据元素删除 remove(value: T): T | null { const index = this.indexOf(value) return this.removeAt(index) } isEmpty() { return this.size === 0 } } // 测试代码 function testLinkedList() { console.log("=== 链表功能测试 ===\n"); const linkedList = new LinkedList<string>(); // 1. 测试初始状态 console.log("1. 初始状态测试:"); console.log("长度:", linkedList.length); // 期望: 0 console.log("是否为空:", linkedList.isEmpty()); // 期望: true console.log(""); // 2. 测试 append 方法 console.log("2. append 方法测试:"); linkedList.append("A"); linkedList.append("B"); linkedList.append("C"); console.log("追加 A, B, C 后:"); linkedList.traverse(); // 期望: A -> B -> C console.log("长度:", linkedList.length); // 期望: 3 console.log(""); // 3. 测试 insert 方法 console.log("3. insert 方法测试:"); // 在头部插入 console.log("在位置 0 插入 HEAD:"); linkedList.insert("HEAD", 0); linkedList.traverse(); // 期望: HEAD -> A -> B -> C // 在中间插入 console.log("在位置 2 插入 MIDDLE:"); linkedList.insert("MIDDLE", 2); linkedList.traverse(); // 期望: HEAD -> A -> MIDDLE -> B -> C // 在尾部插入 console.log("在末尾插入 TAIL:"); linkedList.insert("TAIL", linkedList.length); linkedList.traverse(); // 期望: HEAD -> A -> MIDDLE -> B -> C -> TAIL // 测试越界插入 console.log("测试越界插入:"); const result1 = linkedList.insert("INVALID", -1); const result2 = linkedList.insert("INVALID", linkedList.length + 1); console.log("位置 -1 插入结果:", result1); // 期望: false console.log("位置 size+1 插入结果:", result2); // 期望: false linkedList.traverse(); // 链表应该不变 console.log(""); // 4. 测试 get 方法 console.log("4. get 方法测试:"); console.log("位置 0:", linkedList.get(0)); // 期望: HEAD console.log("位置 2:", linkedList.get(2)); // 期望: MIDDLE console.log("位置 5:", linkedList.get(5)); // 期望: TAIL console.log("位置 -1:", linkedList.get(-1)); // 期望: null console.log("位置 10:", linkedList.get(10)); // 期望: null console.log(""); // 5. 测试 removeAt 方法 console.log("5. removeAt 方法测试:"); // 删除头部 console.log("删除位置 0:"); const removed1 = linkedList.removeAt(0); console.log("删除的元素:", removed1); // 期望: HEAD linkedList.traverse(); // 期望: A -> MIDDLE -> B -> C -> TAIL // 删除中间 console.log("删除位置 2:"); const removed2 = linkedList.removeAt(2); console.log("删除的元素:", removed2); // 期望: B linkedList.traverse(); // 期望: A -> MIDDLE -> C -> TAIL // 删除尾部 console.log("删除最后一个位置:"); const removed3 = linkedList.removeAt(linkedList.length - 1); console.log("删除的元素:", removed3); // 期望: TAIL linkedList.traverse(); // 期望: A -> MIDDLE -> C // 测试越界删除 console.log("测试越界删除:"); const removed4 = linkedList.removeAt(-1); const removed5 = linkedList.removeAt(linkedList.length); console.log("位置 -1 删除结果:", removed4); // 期望: null console.log("位置 size 删除结果:", removed5); // 期望: null linkedList.traverse(); // 链表应该不变 console.log(""); // 6. 测试 update 方法 console.log("6. update 方法测试:"); console.log("更新前:"); linkedList.traverse(); // A -> MIDDLE -> C console.log("更新位置 1 为 UPDATED:"); linkedList.update("UPDATED", 1); linkedList.traverse(); // 期望: A -> UPDATED -> C console.log("测试越界更新:"); linkedList.update("INVALID", -1); // 应该无效果 linkedList.update("INVALID", 10); // 应该无效果 linkedList.traverse(); // 应该不变 console.log(""); // 7. 测试 indexOf 方法 console.log("7. indexOf 方法测试:"); console.log("A 的位置:", linkedList.indexOf("A")); // 期望: 0 console.log("UPDATED 的位置:", linkedList.indexOf("UPDATED")); // 期望: 1 console.log("C 的位置:", linkedList.indexOf("C")); // 期望: 2 console.log("不存在的元素位置:", linkedList.indexOf("NOT_EXIST")); // 期望: -1 console.log(""); // 8. 测试 remove 方法（根据值删除） console.log("8. remove 方法测试:"); console.log("删除 UPDATED:"); const removedByValue = linkedList.remove("UPDATED"); console.log("删除的元素:", removedByValue); // 期望: UPDATED linkedList.traverse(); // 期望: A -> C console.log("删除不存在的元素:"); const removedInvalid = linkedList.remove("NOT_EXIST"); console.log("删除结果:", removedInvalid); // 期望: null linkedList.traverse(); // 应该不变 console.log("删除 A:"); linkedList.remove("A"); linkedList.traverse(); // 期望: C console.log("删除 C:"); linkedList.remove("C"); linkedList.traverse(); // 期望: (空) console.log("长度:", linkedList.length); // 期望: 0 console.log("是否为空:", linkedList.isEmpty()); // 期望: true console.log(""); // 9. 测试边界情况 console.log("9. 边界情况测试:"); // 空链表操作 console.log("空链表时删除:", linkedList.removeAt(0)); // 期望: null console.log("空链表时获取:", linkedList.get(0)); // 期望: null console.log("空链表时更新:", linkedList.update("TEST", 0)); // 应该无效果 // 单元素链表操作 linkedList.append("SOLO"); console.log("单元素链表:"); linkedList.traverse(); // 期望: SOLO console.log("删除单元素:"); linkedList.removeAt(0); linkedList.traverse(); // 期望: (空) console.log("最终长度:", linkedList.length); // 期望: 0 console.log("最终是否为空:", linkedList.isEmpty()); // 期望: true console.log("\n=== 所有测试完成 ==="); } // 运行测试 testLinkedList(); export { }
3.4 链表常见面试题
3.4.1 LeetCode 707：设计链表
设计链表实际和3.2与3.3小节所手写的链表是一致的，我们所实现的链表比题目更为全面。
题目：设计链表的实现。可以选择使用单链表或双链表，单链表中的节点应该具有两个属性：val和next。val是当前节点的值，next是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性prev以指示链表中的上一个节点。假设链表中的所有节点都是0-index 的。
在链表类中实现以下5个功能：
（1）get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。
（2）addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。
（3）addAtTail(val)：将值为val的节点追加到链表的最后一个元素。
（4）addAtIndex(index,val)：在链表中的第index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
（5）deleteAtIndex(index)：如果索引index有效，则删除链表中的第index个节点。
内容不再重复编写，可以参考3.3小节之中的方法案例，已包含以上5个功能的实现思路，可结合LeetCode的题解去具体分析。
3.4.2 LeetCode 237：删除链表中的节点
题目：有一个单链表的 head，我们想删除它其中的一个节点 node。给你一个需要删除的节点 node 。你将无法访问第一个节点 head。链表的所有值都是唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
- node 前面的所有值顺序相同。
- node 后面的所有值顺序相同。
自定义测试：对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。我们将构建链表，并将节点传递给你的函数。输出将是调用你函数后的整个链表。
以下是两个示例：
图3-9 LeetCode237.删除链表中的节点示例图
LeetCode237.删除链表中的节点示例如图3-9所示。对应输出如下所示。
示例A：
输入：head = [4,5,1,9], node = 5。 输出：[4,1,9]。 解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9。
示例B：
输入：head = [4,5,1,9], node = 1。 输出：[4,5,9]。 解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9。
这道题是什么意思？假如我们想要删掉图3-10所示中的数字1，只需要拿到头节点this.head，然后数一下数字1在哪一个节点，然后this.head.next.next就找到目标节点，紧接着前驱节点直接指向目标节点的后继节点就结束了。
所有的题目都需要先理清思路再去做法，思路清晰则代码清晰，LeetCode 237题的分析如下4点：
（1）题目不让我们访问this.head（头节点），也是题目的难点所在，即如何在不访问头节点的情况下去删除目标节点。
（2）题目中的所有值都是唯一的，配合后续所说的删除节点并不是指从内存中删除，要么题目不建议这么做，要么我们在无法访问头节点的情况下无法真正做到删除节点，那么我们需要摒弃传统的做法。
（3）目标节点的前后所有值顺序不变，即删除操作后，在给定节点之前或者之后的所有节点保持原有的连接顺序不变。
（4）给定的节点node不是链表中的最后一个节点，即只存在链节点的情况，因此不需要额外处理边界情况。
（5）节点数量少1，所以一定需要删除一个节点。
如果我们将LeetCode中的代码直接拿到VS Code中，会报错。因为我们没有ListNode节点类型，但好在LeetCode在注释中有提供，我们只需要一并拿出来使用就行。
▼ts复制代码// ListNode文件 class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; } } export default ListNode
这道题很有意思，因为链表访问任何一个位置的元素时，都需要从头开始访问。假如没有了头节点，我们就无法实现访问链表的操作。但这道题目直接给予了我们需要删除的目标节点，因此对于我们来说，只是没办法访问到目标节点的前驱节点。因此以删除目标节点为目标的传统做法：将前驱节点指向目标节点的后继节点，确实是无法实现的。
如何根据已知的信息（目标节点以及后继节点）完成删除的效果？这需要我们有一定的联想能力，题目要求一定要删一个节点，但又说给定节点的值不应该存在于链表中。这两句话听起来有点重复的意思，要么就是这两句话想表达的不是同一个意思，即一定要删除的节点与给定节点不一定要求是同一个。
那么，如果我一定要删除一个节点，目标节点无法删除，因为我无法访问目标节点的前驱节点。我能删的只有目标节点之后的节点，因为可以使用原来的目标节点为新的前驱节点，原来的后继节点为新的目标节点。排除掉不可能的情况，能删除的节点就原来目标节点的后续节点。
以图3-9的示例A为例，假如4->5->1->9，我想删5，但却只能删1，从而变成4->5->9，而题目要求答案是4->1->9。顺序对了，我能不能把原来要删除的目标节点的值（5）直接覆盖成被迫删除的节点的值（1）呢？
显然是可以的，在删除节点数据为1的节点之前，先将其赋值给节点数据为5的节点。从而使链表变为4->1->1->9，此时删除的1是第二个1，删除结果是4->1->9，从而符合题目需求。也就链表是无序的，在内存中的表达非连续性，因此对删除的位置并不敏感。
思考结束，我们需要实现的步骤有两步：
（1）题目提供要删除的目标节点的数据覆盖上目标节点的后继节点的数据。
（2）原来的目标节点的指针指向后继节点的后继节点，实现删除目标节点的后继节点（实际上删除的是目标节点的下一个节点）。
▼ts复制代码import ListNode from "./ListNode" function deleteNode(node: ListNode | null): void { node!.val = node!.next!.val node!.next = node!.next!.next };
总结：这是一道考验做题者阅读解析信息能力的题目，一旦真正理解题目之后，想要实现就非常简单。所有的难度和提示都集中在固有思路转变以及思考层面，考察准确识别关键约束然后从约束推导出可行方案的工程思维，更类似于脑筋急转弯：我杀不了自己，那我就变成别人，然后把别人杀了，这样这个世界就不存在我了（LeetCode题解的调侃想法）。
3.4.3 LeetCode 206：反转链表（迭代与递归）
假如要你将眼前的一个链表前后翻转一下，你会怎么做？让我们来做这一道反转链表的题吧！
题目：给你单链表的头节点head ，请你反转链表，并返回反转后的链表。反转链表实现效果展示图如图3-10所示。
图3-10 LeetCode206.反转链表实现效果展示图
看起来这一道题目有点像要实现链表版本的Array.prototype.reverse()实例方法，即链表的第一个链节点会变成最后一个，数组的最后一个尾节点变成第一个链节点。换句话说，链表中的节点顺序将被翻转，变为与之前相反的方向。图中没有展示头节点，但这很可能意味着this.head（头节点）的指针要指向尾节点了，头节点是作为哨兵存在，不参与反转。
在完成这一题目后，还有进阶写法，链表可以选用迭代或递归方式完成反转，你能否用两种方法解决这道题。我们先从非递归开始，再去实现进阶写法。
实现A（栈写法）：一想到反转，最容易想到的是通过栈结构的先进后出，让我们来实现一下。
通常在实现需求时，需要先想清楚需求，而想清楚需求主要分为：边界情况以及实现思路步骤。在前期处理好边界情况，可以避免代码返工次数频发；想好实现思路步骤再动手能更顺畅的完成功能，避免写到一半来回修改。
边界情况：
（1）链表在为空的情况下无需反转处理，直接返回null。
（2）链表为空有两种情况，即开发者直接传递进来一个null（this.head本身为null）或者只有头节点的链表。
（3）只有头节点的链表意味着只有一个链节点（头节点指针指向第一个链节点），那么反转是没有意义的（第一个链节点反转后还是第一个链节点），我们直接返回头节点本身即可。至少需要两个链节点才达到反转链表的基本条件（如果是采用头节点存储数据的链表，也至少需要一个链节点）。
实现思路：
（1）创建一个栈结构。
（2）将链表节点按顺序推入栈结构中，直到尾节点结束。
（3）从栈结构中按顺序取出链表节点，每个节点的next指针指向下一个取出的节点，直到获取最后一个节点，将原先的第一个链节点，如今的尾节点next指针置为null（否则会进入循环引用的死循环中）。
（4）返回反转后的新链表。
▼ts复制代码// 面试题_ListNode class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; } } export default ListNode
▼ts复制代码import ListNode from "./面试题_ListNode" function reverseList(head: ListNode | null): ListNode | null { // 什么情况下链表不需要处理? // 1.head本身为null的情况 if (head === null) return null // 2.只有head一个节点 if (head.next === null) return head // 数组模拟栈结构 const stack: ListNode[] = [] let current: ListNode | null = head while (current) { stack.push(current) current = current.next } // 以此从栈结构中取出元素, 放到一个新的链表中 const newHead: ListNode = stack.pop()! let newHeadCurrent = newHead while (stack.length) { const node = stack.pop()! newHeadCurrent.next = node newHeadCurrent = newHeadCurrent.next } // 注意: 获取到最后一个节点时, 一定要将节点的next置为null newHeadCurrent.next = null return newHead }; // 模拟数据进行测试 const node1 = new ListNode(1) node1.next = new ListNode(2) node1.next.next = new ListNode(3) const newHead = reverseList(node1) let current = newHead while (current) { console.log(current.val) current = current.next } export {}
以上使用栈结构实现的反转链表，是没有哨兵（不含数据只有指针的头节点）节点的链表，因此链表可以完全反转。如果链表存在哨兵节点（头节点），我们就需要跳过哨兵节点开始压栈。然后将哨兵节点作为新链表的头，清空哨兵节点的指针，设置指向新的反转链表的第一个链节点。
▼ts复制代码function reverseListWithSentinel(head: ListNode | null): ListNode | null { // 处理空链表或只有哨兵节点的情况 if (head === null || head.next === null) return head const stack: ListNode[] = [] // 跳过哨兵节点，从第一个实际数据节点开始压栈 let current: ListNode | null = head.next while (current) { stack.push(current) current = current.next } // 重新构建链表，保留原来的哨兵节点 let newCurrent = head // 哨兵节点作为新链表的头 newCurrent.next = null // 清空哨兵节点的next // 从栈中弹出节点并连接到哨兵节点后面 while (stack.length) { const node = stack.pop()! newCurrent.next = node newCurrent = newCurrent.next } // 将最后一个节点的next置为null newCurrent.next = null return head // 返回原来的哨兵节点 }
但LeetCode的这类题目中，往往是不考虑哨兵节点的情况的，但有无哨兵节点的情况处理方式并没有差太多。206题反转链表的其他做法中，我们还是采用无哨兵节点，即头节点存储数据的条件。
采用栈结构来实现反转链表其实不是一个好方法，因为栈结构的空间复杂度是O(n)，而且在反转链表中多使用了一个栈结构，也会使代码更复杂。
实现B（循环）：循环做法的边界判断思路与栈结构做法是一致的。
▼ts复制代码import ListNode from "./面试题_ListNode" function reverseList(head: ListNode | null): ListNode | null { // 1.判断节点为null, 或者只要一个节点, 那么直接返回即可 if (head === null || head.next === null) return head };
如果使用循环来反转链表，要怎么做？通过以下3步骤实现：
（1）首先我们需要创建一个新的头节点（携带数据的），指向尾节点。
（2）从第一个链节点开始，指针指向全部反转。
（3）原来的头节点置为null。
反转链表的循环做法如图3-11所示。
图3-11 反转链表（循环）
在指针反转的过程中，有一个注意事项需要注意。由于链表访问必须从头节点开始，假如我找到第一个链节点直接改next指针，那么第一个链节点之后的所有节点就会直接丢失，这个问题在插入第一个链节点的时候我们也有遇到过。那遇到这种问题，我们要怎么处理解决？
可以参考之前的解决方式，只需要先改当前节点的前驱节点指针（前驱指针与当前节点的位置都不会丢失），那么后续节点就不会出现丢失问题。这可以延伸出一个很好的思路，我们通过current临时指针先找到第二个链节点，然后去修改第一个链节点的next指针，直到current临时指针找到null为止（说明找到尾节点了，null的前一个节点为尾节点）。
有了想法之后，要如何实现呢？大家在入门编程语言（例如JavaScript）的时候，一定做过一个经典的案例：如何交换两个元素。我在第一次学习JavaScript时也苦恼过这一个问题，如果我将A赋值给B，那B的内容就没了，反之A的内容就没了。对此有一个经典的做法：用临时变量C保存好变量A，那么B就能赋值给A，再让临时变量C保存的变量A赋值给变量B。其次的进阶做法可以采用解构赋值[a,b] = [b,a]，但底层原理都是相同的，都需要有额外存放数据的地方，给数据交换提供腾转的空间。
那么在循环链表中，所需要面对的问题是： 如何在不丢失节点访问能力的情况下安全地修改指针关系。因此可以借鉴变量交换的思想，在修改前保存必要的引用，确保每个操作都不会破坏链表的完整性，特别处理头尾节点的连接以保持循环特性，这种"先保存，后修改"的策略是处理指针操作时的通用最佳实践。所以我们必然是需要一个新节点用于保存必要节点，以及一个新的头节点。
产生实践思路如下：
（1）使用临时节点（current）记录原链表的下一个节点，以防丢失原链表的后续部分。
（2）将当前节点（head）的next指向新链表的头节点（newHead），这样当前节点就连接上了已经反转的部分链表。
（3）更新新链表的头节点为当前节点，因为当前节点现在已经成为了新链表的最前端。
（4）将原链表的头节点指向临时节点（current），也就是原链表的下一个节点，继续处理后续节点。
新节点保存必要节点可通过current这一用于遍历的节点保存，创建新的头节点newHead，初始值为null。
因此我们需要以下4步操作：
（1）让current节点（用于遍历链表的节点）的指针指向下一节点，用于保存当前节点的下一个节点，防止链表断开。
（2）此时需要将第一个链节点指向null，形成反转链表的尾节点。但此时第一个链节点的指针我们不直接指向null，而是指向newHead。
（3）让newHead指向head节点，目的是下一次遍历时，第二步操作可以让下一个节点指向第一个节点。
（4）让head移向下一个节点指向current。
newHead初始值也是null，效果没有区别，那是基于什么原因让我们不选择直接指向null而是newHead？最核心的原因在于保持操作的一致性，在第一次循环时，确实看起来没有区别，但问题在于后续循环。从第二次循环开始，如果还让第二个链节点指向null就会破坏已经建立的反转关系，此时原链表的第二个链节点应该要"裁切"到新链表身上去指向新链表的第一个链节点了。通过上一次循环的newHead = head，可以将当前节点裁切下来，在本次循环中通过head.next = newHead将当前处理的节点设置为新的头节点。
▼ts复制代码import ListNode from "./面试题_ListNode" function reverseList(head: ListNode | null): ListNode | null { // 1.判断节点为null, 或者只要一个节点, 那么直接返回即可 if (head === null || head.next === null) return head // 2.反转链表结构 // 创建新的头节点 let newHead: ListNode | null = null while (head) { // 1）保存当前节点的下一个节点，防止链表断开 const current: ListNode | null = head.next // 2）反转指针：当前节点指向新链表的头节点 head.next = newHead // 3）更新新链表的头节点为当前节点 newHead = head // 4）移动到原链表的下一个节点 head = current } return newHead }; // 模拟数据进行测试 const node1 = new ListNode(1) node1.next = new ListNode(2) node1.next.next = new ListNode(3) const newHead = reverseList(node1) let current = newHead while (current) { console.log(current.val) current = current.next } export { }
总的来说，反转链表的循环做法，是通过一个额外节点暂时保存住原链表的相关信息（防链表断开），然后将原链表的节点一个个的裁切到新链表上作为头节点，直到将原链表的节点裁切结束，则原链表的尾节点就会成为新链表最终的头节点。我们也可以用搭积木来比喻：记住下一块积木的位置（临时指针），从原塔拆下当前积木（断开原链接），把积木放到新塔的顶部（更新头节点），准备拆下一块积木（推进指针）。
循环链表做法图示如图3-12所示。
图3-12 循环链表做法图示
实现C：递归。如果使用的是递归, 那么递归必须有结束条件，否则会无限递归，直到爆栈终止。
▼ts复制代码import ListNode from "./面试题_ListNode" function reverseList(head: ListNode | null): ListNode | null { // 如果使用的是递归, 那么递归必须有结束条件 if (head === null || head.next === null) return head };
递归要如何实现反转链表？这需要利用上递归的特点，递归它会连续调用到我们终止条件的位置，然后从终止位置开始往前执行。这就很有意思了，意味着我们可以从一个链表的尾节点开始执行，那我直接在一开始递归执行的尾节点处直接让头节点指向尾节点，然后获取每个目标节点的前驱节点，然后将目标节点指向前驱节点，直到前驱节点为null。
现在我有两个位置，分别是位置A与位置B。我们如果要编写反转指针的代码，需要写在哪个位置？
应该把反转指针的代码写在位置B。这是因为递归函数会像"潜水"一样一直深入到链表的最后一个节点（尾节点）。当到达尾节点时，递归就会停止不再继续深入。如果我们把反转代码写在位置A，就像在"潜水"的过程中就急着要反转，但此时我们还没有看到整个链表的结构，而且最后一个节点由于已经满足终止条件，根本不会执行位置A的代码。而写在位置B，就像"潜水"到底后开始慢慢上浮，在返回的过程中逐个处理每个节点。这时候我们已经知道了链表的结构，可以从尾节点开始，安全地逐个反转指针方向，直到回到链表头部。
▼ts复制代码import ListNode from "./面试题_ListNode" let count = 1 function reverseList(head: ListNode | null): ListNode | null { // 如果使用的是递归, 那么递归必须有结束条件 if (head === null || head.next === null) return head // 位置A // 递归 const newHead = reverseList(head?.next ?? null) // 位置B return newHead };
那么，我们要递归的"深度"是要在哪里？尾节点吗？不是的，我们不应该停留在尾节点的地方，而且也无法停留在尾节点，由于我们设置的递归结束条件head.next === null，导致递归无法到达尾节点。但这不是什么问题，我们只需要到达倒数第二个链节点之后，多next一层就能找到尾节点。
在编写链表的插入方法的时候，我们都知道要获取目标节点的前驱节点，而如果我要反转节点的指针，那么我也应该获取到目标节点的前驱节点，然后将目标节点的next指向前驱节点本身，即head.next（目标节点） = head（前驱节点）。而由于我们只到达倒数第二个链节点，为保证尾节点不丢失，需要多next一层，因此代码需要为head.next.next = head。
▼ts复制代码import ListNode from "./面试题_ListNode" let count = 1 function reverseList(head: ListNode | null): ListNode | null { // 如果使用的是递归, 那么递归必须有结束条件 if (head === null || head.next === null) return head const newHead = reverseList(head?.next ?? null) // 完成想要做的操作是在这个位置 // 第一次来到这里的时候, 是倒数第二个节点 head.next.next = head head.next = null return newHead }; // 模拟数据进行测试 const node1 = new ListNode(1) node1.next = new ListNode(2) node1.next.next = new ListNode(3) const newHead = reverseList(node1) let current = newHead while (current) { console.log(current.val) current = current.next } export {}
以上LeetCode的三道题，即题号为707、237、206的题目都是基于有数据的头节点（非哨兵节点），思路需要稍有转变。文字表述还是较为抽象一些，如果难以理解，可以观看coderwhy老师的阶段十七-数据结构与算法一的第三天开头部分。
3.4.4 链表接口设计
在我们实现的链表中有很多方法，可以将这些方法放入到对应的接口里面。那这种做法有什么好处？将链表方法定义在接口中，是一种面向接口编程的重要实践。这种做法最大的好处在于定义契约与实现分离。接口就像一份合同，明确规定了链表必须提供哪些功能，但不关心这些功能具体如何实现。任何实现了这个接口的类都必须遵守这个契约，确保具备所有必要的方法。
这种方式极大地提升了代码的灵活性和可维护性。当我们需要更换链表实现时，比如从单向链表改为双向链表，只要遵循相同的接口，不用我们再点开之前具体实现的单向链表去找一个个需要实现的链表方法规范。甚至可以直接让双向链表继承单向链表，重写其中不同的部分。
▼ts复制代码import IList from "../types/IList" interface ILinkedList<T> extends IList<T> { append(value: T): void traverse(): void insert(value: T, position: number): boolean removeAt(position: number): T | null get(positon: number): T | null update(value: T, position: number): boolean indexOf(value: T): number remove(value: T): T | null } export default ILinkedList // class LinkedList<T> implements ILinkedList<T>
3.5 算法复杂度分析
在第1章，我们已经解释了什么是算法？其实就是解决问题的一系列步骤操作、逻辑。对于同一个问题，我们往往其实有多种解决它的思路和方法，也就是可以采用不同的算法。但是不同的算法，其实效率是不一样的。举个例子（现实的例子）：在一个庞大的图书馆中，我们需要找一本书。在图书已经按照某种方式摆好的情况下（数据结构是固定的）。
方式一：顺序查找。一本本找，直到找到想要的书；（累死） 方式二：先找分类，分类中找这本书。先找到分类，在分类中再顺序或者某种方式查找； 方式三：找到一台电脑，查找书的位置，直接找到；图书馆通常有自己的图书管理系统；利用图书管理系统先找到书的位置，再直接过去找到；
3.5.1 算法复杂度简介与现实案例
什么是算法复杂度？算法复杂度是衡量一个算法在处理不同规模的数据时，所需消耗的“时间”和“空间”（内存）资源的量度。它不关注具体的运行时间（秒数），而是关注随着输入数据规模的增大，算法效率的变化趋势。通常，我们更关注时间复杂度，因为时间（速度）往往是更稀缺的资源。
我们举一个程序中的案例：让我们来比较两种不同算法在查找数组中（数组有序）给定元素的时间复杂度。一个数组内有100w个元素，元素有序排列，我们要如何查找在这数组中的某一个我们所需的元素？
两个经典的方法：顺序查找与二分查找。
（1）顺序查找。这种算法从头到尾遍历整个数组，依次比较每个元素和给定元素的值。如果找到相等的元素，则返回下标；如果遍历完整个数组都没找到，则返回-1。
（2）二分查找。这种算法假设数组是有序的，每次选择数组中间的元素与给定元素进行比较。如果相等，则返回下标；如果给定元素比中间元素小，则在数组的左半部分继续查找；如果给定元素比中间元素大，则在数组的右半部分继续查找；这样每次查找都会将查找范围减半，直到找到相等的元素或者查找范围为空。二分查找如图3-13所示。
图3-13 二分查找
对于一个拥有100万个元素的数组来说，顺序查找在最坏的情况下，我们需要遍历整个数组，即100万次比较。二分查找每次比较后都将搜索范围减半。最坏情况是直到范围为空，即需要比较log₂(1000000)次。假设每次查找耗费时间为0.00001秒，那么顺序查找最多耗时10秒，而二分查找最多只需要查找20次，即0.0002 秒，两种查找算法之间的效率差了5万倍，并且随着数据量级的增长，查找效率还会进一步的拉大。
时间复杂度是衡量算法运行时间随输入规模增长的变化趋势，即当数据量（n）翻倍时，算法的运行时间会如何变化？。顺序查找最好的情况是第一次就找到，但我们一般不考虑这种情况（参考价值低）。我们通常参考最坏时间复杂度（查找100万次，n次）以及平均时间复杂度（查找50万次，n/2次）。二分查找的时间复杂度为log₂n。
在一个有 n 个元素的数组中查找一个特定的值，常见的时间复杂度等级如下表3-1所示。
表3-1 常见时间复杂度等级
| 复杂度 | 名称 | 举例（查找） | 当 n 翻倍时... | 形象比喻 |
|---|---|---|---|---|
| O(1) | 常数时间 | 通过索引直接访问数组元素 | 时间不变 | 无论图书馆多大，都知道某本书在固定位置。 |
| O(log n) | 对数时间 | 在已排序的数组中进行二分查找 | 时间只增加一点点 | 每次翻书都能排除一半的区域，非常高效。 |
| O(n) | 线性时间 | 在未排序的数组中逐个遍历查找 | 时间也翻倍 | 一页一页地翻通讯录，最坏情况要翻完。 |
| O(n log n) | 线性对数时间 | 高效的排序算法，如快速排序、归并排序 | 时间比翻倍多一点 | 一种比较高效的整理书籍的方式。 |
| O(n²) | 平方时间 | 低效的排序算法，如冒泡排序、选择排序 | 时间变为4倍 | 检查每本书与其他所有书是否按顺序排好。 |
| O(2ⁿ) | 指数时间 | 解决暴力破解密码、汉诺塔问题 | 时间急剧膨胀 | 每多一本书，整理方案的数量就爆炸性增长。 |
| O(n!) | 阶乘时间 | 旅行商问题的暴力解法 | 时间无法承受 | 尝试所有可能的排列组合，完全不可行。 |
3.5.2 顺序查找与二分查找对比
接下来我们通过代码的展示来对比顺序查找与二分查找。
如果我们要实现顺序查找或者二分查找，我们要使用函数还是类来实现？这是一个很有意思的问题，在之前实现链表的时候，我们是通过类实现的，但现在如果要实现这两个查找方法，最好使用函数。因为搜索算法本质上是无状态的纯操作（固定的输入一定会产生固定的输出），是我们所说的纯函数。并且函数更简单、直接、易于测试。只有在算法需要维护状态、配置或复杂的行为时，才考虑使用类实现，例如一口气实现七八种甚至更多的同系列算法。对于基本的顺序查找和二分查找，函数实现是更优雅和实用的选择。
通过函数实现顺序查找，需要接受两个参数：数据和需要查找的目标数据。返回一个结果，即查找的目标数据位置或者没找到。在我们这个案例中，以数组作为数据承载的载体，数据类型统一为整数。通过查找整数的数据，获取数据的索引位置。PS：对于一个完善的查找算法，会考虑各种类型的边界情况，这里只讨论算法实现本身。
▼ts复制代码/** * 顺序查找的算法 * @param array 查找的数组 * @param num 查找的元素 * @returns 查找到的索引, 未找到返回-1 */ function sequentSearch(array: number[], num: number) { } export default sequentSearch
顺序查找通过遍历数组，挨个比对要查找的目标顺序，那么遍历数组我们要使用for循环还是while循环？在之前有说明，编写算法大多数都使用while循环，但我们的顺序查找最好使用for循环。主要原因是for循环将初始化、条件判断、索引递增三个操作集中在一行。数组不像我们手写实现的链表，数组它有长度有索引的，这些都是已知的信息，并且初始化index和递增可以直接在for循环中实现，这不会泄露到外界作用域中，更加稳定。因此for循环的做法在这里会比while (index++ < position && current) 类似的做法更好。
▼ts复制代码/** * 顺序查找的算法 * @param array 查找的数组 * @param num 查找的元素 * @returns 查找到的索引, 未找到返回-1 */ function sequentSearch(array: number[], num: number) { for (let i = 0; i < array.length; i++) { const item = array[i] if (item === num) { return i } } // 没找到目标数据 return -1 } const index = sequentSearch([1, 3, 5, 10, 100, 222, 333], 222) console.log(index) export default sequentSearch
同时在熟悉编程语言以及数据结构与算法后，我们也可以采用高阶函数来精简代码，一行代码就能解决，但底层所表达的含义是一致的。
▼ts复制代码const sequentSearch = (arr: number[], target: number) => arr.findIndex(item => item === target);
二分查找所需要接收的参数和返回结果规则与顺序查找一致。但使用二分查找时，我们需要定义"边界"，即最左侧的索引（起点）和最右侧的索引（终点），有了"边界"才能确定初始查找的中间值。当中间值大于目标数据时，说明目标数据在左侧，那么中间值会成为新的右侧边界；当中间值小于目标数据时，说明目标数据在右侧，那么中间值会成为新的左侧边界。这一循环会持续到找到目标数据或者找遍了也没找到然后返回-1。
对于二分查找而言，使用while循环更好，因为二分查找不需要初始化索引，也不需要递增，唯一需要的就是重复的"对折"。这里可以注意到，每次重新界定边界时，左侧边界会加1（目标数据在右边），右侧边界则会减1（目标数据在左边），是因为mid位置的元素已经被检查过了，不需要再次检查。加1减1的操作目的是排除已检查的元素。
▼ts复制代码function binarySearch(array: number[], num: number) { // 1.定义左边的索引 let left = 0 // 2.定义右边的索引 let right = array.length - 1 // 3.开始查找 while (left <= right) { let mid = Math.floor((left + right) / 2) const midNum = array[mid] if (midNum === num) { return mid } else if (midNum < num) { left = mid + 1 } else { right = mid - 1 } } return -1 } const index = binarySearch([1, 3, 5, 10, 100, 222, 333], 222) console.log(index) export default binarySearch
在完成顺序查找与二分查找的算法之后，我们创建一个函数方法，使用测试数组，存放极多元素，来测试两种算法的消耗时间。
首先new Array(10_000_000)创建一千万由个undefined组成的稀疏数组，然后将所有元素填充为数字0之后，最后利用索引按顺序将每个元素替换为索引值，形成一个由一千万个数字元素组成的有序密集数组。使用高阶函数配合链式调用可以快速完成这一需求，但需要注意创建稀疏数组之后，必须先使用Array.prototype.fill()实例方法将所有元素填充为0，从而形成密集数组，因为Array.prototype.map()实例方法只会遍历已经赋值的元素，不处理稀疏数组。MDN文档中的Array.prototype.map()实例方法处理稀疏数组情况如图3-14所示。
图3-14 Array.prototype.map()实例方法处理稀疏数组情况
▼ts复制代码const MAX_LENGTH = 10_000_000 const nums = new Array(MAX_LENGTH).fill(0).map((_, index) => index)
然而先填充再map替换虽然可行，但需要两次遍历。我们可以使用Array.from()静态方法创建数组，因为Array.from()静态方法绝不会创建稀疏数组。如果arrayLike对象缺少一些索引属性，那么这些属性在新数组中将是undefined。Array.from() 有一个可选的参数mapFn，该参数允许你在创建数组时为每个元素执行一个函数，类似于map()。更明确地说，Array.from(obj, mapFn, thisArg) 和Array.from(obj).map(mapFn, thisArg)具有相同的结果，只是它不会创建中间数组，并且mapFn仅接受两个参数（element、index），不接受数组，因为数组仍然在构建中。
这完美符合我们测试数组的需求。
▼ts复制代码// Array.from(arrayLike, mapFn, thisArg) const nums = Array.from({ length: 10_000_000 }, (_, i) => i);
我们要如何测算出两种查找算法所耗费的时间？利用Date.prototype.getTime()获取开始查找和查找结束之后的格林威治时间数值差是一个方法。但Performance.now()的精度会更高，和 JavaScript 中其他可用的时间类函数（比如Date.now）不同的是，window.performance.now()返回的时间戳没有被限制在一毫秒的精确度内，相反，它们以浮点数的形式表示时间，精度最高可达微秒级。另外一个不同点是，window.performance.now()是以一个恒定的速率慢慢增加的，它不会受到系统时间的影响（系统时钟可能会被手动调整或被 NTP 等软件篡改），这是一个很有意思的细节。
▼ts复制代码import sequentSearch from "./01_查找算法-顺序查找"; import binarySearch from "./02_查找算法-二分查找"; const MAX_LENGTH = 10_000_000 const nums = Array.from({ length: MAX_LENGTH }, (_, i) => i); const num = MAX_LENGTH / 2 const startTime = performance.now() // const index = sequentSearch(nums, num) const index = binarySearch(nums, num) const endTime = performance.now() console.log('索引的位置:', index, '消耗的时间:', (endTime - startTime)) // console.log(performance.now()) export {}
根据测算的结果，索引的中间位置: 5_000_000所消耗的时间是0.10109999999997399。
除了以上的测试方法，我们还可以利用一些第三方库来更快捷的测试，通常第三方库会考虑更多的边界情况，拥有更完善的测试规则，这能够方便我们。
第三方库hy-algokit的代码地址：hy-algokit - npm，由coderwhy老师实现的npm工具包，我们后续还会在很多地方使用到。
根据第三方库hy-algokit的测试结果，一千万数据的测试时间效率差距大概是334.213倍，也是一个很大的效率差了。在不同的电脑中的不同时间下，这效率差也会有所不同，这一点和力扣提交代码的运行效率波动一样，需要辩证看待。
▼ts复制代码import { testOrderSearchEfficiency } from 'hy-algokit' import sequentSearch from "./01_查找算法-顺序查找"; import binarySearch from "./02_查找算法-二分查找"; testOrderSearchEfficiency(sequentSearch) // 数组长度:10000000 - sequentSearch 消耗时间: 5.0131999999999834 testOrderSearchEfficiency(binarySearch) // 组长度:10000000 - binarySearch 消耗时间: 0.014999999999986358 export { }
对于顺序查找与二分查找的时间复杂度，我们通常用O(n)和O(log n)级别来表示，而不用具体时间来说明。因为具体时间不好表示，哪怕代码一致，每个人的电脑资源不同，网速不同，各种额外因素不同，都会导致具体时间发生偏移，哪怕自己连续两次运行，两次运行的时间也不会一样。因此固定的输入并不会产生固定的输出，这种不稳定的说明方式是不可使用的。那么是什么时候将大O表示法运用到算法分析这一领域的呢？这是我们接下来要探讨的问题。
3.5.3 大O表示法
大O表示法的历史渊源可以追溯到19世纪末的数学研究领域。1894年，德国数学家保罗·巴赫曼在其著作《解析数论》中首次引入了这一概念，他使用字母"O"来表示"Ordnung"（德语中的"阶"或"顺序"），旨在简化复杂函数的渐近行为分析。
这一数学工具随后得到了另一位德国数学家埃德蒙·兰道的进一步发展和推广。在1909年及随后的工作中，兰道系统地使用并完善了大O表示法，建立了更加形式化的数学定义体系，以至于这一符号系统后来常被称为"兰道符号"。兰道的贡献使得大O表示法从巴赫曼的初步构想发展成为一个成熟的数学分析工具，为后续在计算机科学中的应用奠定了坚实的理论基础。
大O表示法从纯粹的数学领域过渡到计算机科学发生在20世纪中期，这一转变主要由计算机科学的先驱者们推动。随着电子计算机的出现和发展，科学家们开始面临一个全新的挑战：如何评估和比较不同算法的效率。在计算机资源极为有限的早期阶段，理解算法性能变得至关重要。正是在这样的背景下，计算机科学家们发现了大O表示法的潜力——它能够提供一种与具体机器无关的方法来描述算法性能。唐纳德·克努特在1960年代至1970年代的工作对这一过渡起到了关键作用，他在其里程碑式的著作《计算机程序设计艺术》中系统地将大O表示法引入算法分析领域，使其成为评估算法效率的标准工具。这解释了我们刚才大O表示法是什么时候运用到算法分析领域的疑惑。
大O表示法之所以能够在计算机科学中取得如此重要的地位，是因为它完美地解决了算法分析中的几个核心问题。首先，它提供了一种机器无关的性能度量方式，使得算法比较不再受特定硬件性能的影响。其次，它通过忽略常数因子和低阶项，让分析者能够专注于算法随输入规模增长的主要趋势，这正是评估算法可扩展性的关键。此外，大O表示法强调最坏情况分析，为算法性能提供了可靠的保证底线。这些特性使得大O表示法成为算法设计、系统架构和技术决策中不可或缺的工具，从简单的排序算法到复杂的分布式系统设计，都能看到它的应用价值。
随着计算机科学的不断发展，大O表示法也在持续演进和完善。它不仅催生了包括大Ω、大Θ、小o和小ω在内的完整渐近符号家族，还不断适应新的计算范式，如分布式计算、大数据处理和量子计算等。从巴赫曼最初的数学洞察到如今成为计算机科学教育的基石，大O表示法的历史轨迹展示了抽象数学概念如何转化为解决实际工程问题的强大工具，这一历程本身也体现了理论与应用之间富有成效的互动关系。
大O表示法和大学数学中的极限概念很相似，当我们说一个算法的时间复杂度是O(n²)时，我们实际上是在描述当输入规模n趋向于无穷大时，算法运行时间的增长趋势将被n²函数所主导。这直接对应到数学分析中的极限思想——我们关心的是函数在自变量趋于无穷时的渐近行为，而不是在某个具体点的精确值。
举个例子，解决一个规模为n的问题所花费的时间（或者所需步骤的数目）可以表示为如图3-15所示的二次表达式。当n增大时，n²项开始占据主导地位，其他各项可以被忽略。当n=500时，4n²项是2n项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。通常为了更好理解，我们可以假设n等于无限（∞），在极端的情况下，应该被忽略的因素就会变得极其明显。
图3-15 一个二次表达式
大O表示法的O代表order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。O可以理解为一种"Order"（阶）的概念，每一阶层都是独立的性质，代表了截然不同的增长特性。因此进一步看，如果我们与任一其他级的表达式比较，n²的系数也是无关紧要的。在图3-15所示的情况下，我们就说该算法具有n²阶（平方阶）的时间复杂度，表示为O(n²)。
从了解大O表示法的历史中，我们其实能看到数据结构与算法和数学之间的联系是息息相关的。但学习基础的数据结构与算法的时候，并不要求对数学有太高深的要求，最大的共通之处在于对逻辑的追求是一致的。
大O表示法通过"阶"的概念来建立了清晰的分层结构，当我们说一个算法是O(1)时，意味着它处于常数阶——无论输入规模如何增长，执行时间都保持稳定。这是最高效的层级，代表着算法的理想状态。而O(log n)属于对数阶，其特点是随着输入规模翻倍，所需资源仅增加一个固定量，这种"减速增长"的特性使其在处理大规模数据时表现出色。除此之外，还都有哪些常见的阶层？在表3-1所示的常见时间复杂度等级中已经得以管中窥豹。随着阶层的抬升，效率之间的对比优势如何的呢？大O表示法复杂度阶层表如表3-2所示。除此之外还有一些迭代对数阶、反阿克曼函数，线性迭代对数的特殊复杂度阶层。
表3-2 大O表示法复杂度阶层表
| 复杂度阶 | 名称 | 描述 | 示例算法 | 数据量翻倍时的变化 |
|---|---|---|---|---|
| O(1) | 常数阶 | 执行时间不随输入规模变化 | 数组按索引访问、哈希表查找 | 时间不变 |
| O(log log n) | 双对数阶 | 极缓慢的增长 | 插值搜索的某些变体、Van Emde Boas树 | 几乎不变 |
| O(log n) | 对数阶 | 每次操作将问题规模减半 | 二分查找、平衡二叉搜索树操作 | 时间增加常数 |
| O(√n) | 平方根阶 | 比线性慢但比多项式快 | 质数检测(试除法)、某些图算法 | 时间增加约1.4倍 |
| O(n) | 线性阶 | 执行时间与输入规模成正比 | 顺序查找、遍历数组 | 时间翻倍 |
| O(n log n) | 线性对数阶 | 高效排序算法的典型复杂度 | 快速排序、归并排序、堆排序 | 时间略多于翻倍 |
| O(n²) | 平方阶 | 执行时间与输入规模平方成正比 | 冒泡排序、选择排序、简单图遍历 | 时间变为4倍 |
| O(n³) | 立方阶 | 三维数据处理典型复杂度 | 矩阵乘法(朴素)、Floyd-Warshall算法 | 时间变为8倍 |
| O(2ⁿ) | 指数阶 | 组合爆炸问题 | 旅行商问题(暴力)、子集枚举 | 时间急剧增加 |
| O(n!) | 阶乘阶 | 排列组合问题 | 旅行商问题(全排列)、图同构(暴力) | 时间无法承受 |
3.5.4 空间复杂度
空间复杂度是算法分析中与时间复杂度同等重要的概念，它衡量的是算法在运行过程中所需的存储空间资源。空间复杂度表示算法在运行过程中临时占用的存储空间大小与输入规模之间的关系，通常需要分析程序中需要额外分配的内存空间，如数组、变量、对象、递归调用等，同样使用大O表示法来描述。
在学习LeetCode的第206题反转链表的过程中，我们使用过栈结构的先进后出特性来实现反转。那时候我们说这种做法不是非常好，因为它的空间复杂度较高，即相较其他的循环和递归方法来说，多了一个栈结构，也就需要在运行过程中使用更多的存储空间。
举例如下：对于一个简单的递归算法来说，每次调用都会在内存中分配新的栈帧，这些栈帧占用了额外的空间，并且递归结束之前，栈帧不会被释放。因此，该算法的空间复杂度是O(n)，其中n是递归深度。而对于迭代算法来说，在每次迭代中不需要分配额外的空间，因此其空间复杂度为O(1)。当空间复杂度很大时，可能会导致内存不足，程序崩溃，比如无限递归导致的爆栈（栈溢出较常见）。
而空间复杂度的实际计算规则主要有3点：
（1）忽略输入数据本身占用的空间。
（2）只考虑算法运行所需的额外空间。
（3）考虑最坏情况下的空间需求。
在平时进行算法优化时，我们通常会进行如下3点考虑： （1）使用尽量少的空间（优化空间复杂度）。 （2）使用尽量少的时间（优化时间复杂度）。 （3）特定情况下：使用空间换时间或使用时间换空间。
空间复杂度不需要总结表格，常见的表现就常数、对数以及线性的表现，正如3.5.1小节开头说的一样，通常，我们更关注时间复杂度，因为时间（速度）往往是更稀缺的资源。但为什么这么认为呢？主要的原因是内存增长快于处理器性能提升（因此内存的使用余地更多），空间可以通过扩展解决，时间不行，并且用户对延迟的容忍度很低，我在App Store中看见很多低星打分和评价，往往是在延迟加载以及bug闪退上，因此速度直接影响收入和用户留存。
这就是为什么在算法设计和系统架构中，我们通常优先优化时间复杂度，在必要时才用空间换时间。当然，优秀的工程师会在两者之间找到最佳平衡点。在后续学到其他数据结构的时候，我们还会涉及到空间复杂度。
3.6 数组与链表的复杂度对比
接下来，我们使用大O表示法来对比一下数组和链表的时间复杂度，如表3-3所示。
表3-3 数组和链表的时间复杂度比对
| 数据结构 | 访问 (Access) | 搜索 (Search) | 插入 (Insertion) | 删除 (Deletion) |
|---|---|---|---|---|
| 数组 | O(1) | O(N) | O(N) | O(N) |
| 链表 | O(N) | O(N) | O(1) | O(1) |
数组是一种连续的存储结构，通过下标可以直接访问数组中的任意元素。
数组的四种情况下的时间复杂度分析如下：
（1）访问 O(1)：通过索引直接访问任意元素，计算内存地址：base_address + index * element_size。
（2）搜索 O(N)：需要遍历数组直到找到目标元素（最坏情况）。
（3）插入 O(N)：在最坏情况下（在开头插入）需要移动所有后续元素。
（4）删除 O(N)：在最坏情况下（删除开头元素）需要移动所有后续元素。
链表的四种情况下的时间复杂度分析如下：
（1）访问 O(N)：必须从头节点开始遍历到目标位置。
（2）搜索 O(N)：需要遍历链表直到找到目标元素。
（3）插入 O(1)：在已知位置插入只需修改指针引用。
（4）删除 O(1)：在已知位置删除只需修改指针引用。
以上对数组和链表的时间复杂度分析更类似一种总结，在第2章线性结构与第3章（本章）的3.3小节手写链表中，我们已经详细学习过了，我觉得理解这些总结内容对我们而言是较为轻松的。
在实际开发中，选择使用数组还是链表需要根据具体应用场景来决定。如果数据量不大，对内存使用效率有追求，且需要频繁随机访问元素，使用数组可能会更好。如果数据量大，内存分配不确定，或者需要频繁插入和删除元素，使用链表可能会更好。
