S15-03 算法-链表、算法复杂度
[TOC]
链表结构 LinkedList
API
链表的操作方法和数组非常类似，因为链表本身就是一种可以代替数组的结构。
- append()：
(el)，向链表尾部添加一个新的元素。 - traverse()：
()，遍历打印链表中的每一个元素。 - insert()：
(el,pos)，向链表的特定位置插入一个新的元素。可以是头部、尾部和中间位置。 - removeAt()：
(pos)，从链表的特定位置移除一项。 - get()：
(pos)，获取对应位置的元素。 - update()：
(el,pos)，修改某个位置的元素。 - indexOf()：
(el)，返回元素在链表中的索引。如果链表中没有该元素则返回-1。 - remove()：
(el)，从链表中移除一项。 - isEmpty()：
()，如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false。 - size()：
()，返回链表包含的元素个数。与数组的length属性类似。
链表概述
什么是链表
链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。
引用 记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。
其实上面我们已经简单的提过了链表的结构，我们这里更加详细的分析一下。
链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客(类似于数据)，并且这个节点会连接下一个节点，以此类推。
链表的火车结构：
对比数组
对比数组：链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。
这一章中，我们就来学习一下另外一种非常常见的用于存储数据的线性结构：链表。
数组：
- 要存储多个元素，数组（或选择链表）可能是最常用的数据结构。
- 我们之前说过，几乎每一种编程语言都有默认实现数组结构。
数组的缺点：
- 数组的创建通常需要申请一段连续的内存空间(一整块的内存)，并且大小是固定的(大多数编程语言数组都是固定的)，所以当当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如2倍。 然后将原数组中的元素复制过去)
- 而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。
- 尽管JavaScript的Array底层可以帮我们做这些事，但背后的原理依然是这样。
链表：
要存储多个元素，另外一个选择就是链表。
但不同于数组，链表中的元素在内存中不必是连续的空间。
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成。
链表对比数组的优点：
- 内存空间不是必须连续的。可以充分利用计算机的内存，实现灵活的内存动态管理。
- 链表不必在创建时就确定大小，并且大小可以无限的延伸下去。
- 链表在插入和删除数据时，时间复杂度可以达到O(1)。相对数组效率高很多。
链表对比数组的缺点：
- 链表访问任何一个位置的元素时，都需要从头开始访问。无法跳过第一个元素访问任何一个元素。
- 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素。
封装链表
封装-链表结构
我们先来创建一个链表类
代码解析：
- 封装一个Node类，用于封装每一个节点上的信息（包括值和指向下一个节点的引用），它是一个泛型类。
- 封装一个LinkedList类，用于表示我们的链表结构。 (和Java中的链表同名，不同Java中的这个类是一个双向链表，在第二阶段中我们也会实现双向链表结构)。
- 链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点。
- 当然，还有很多链表的操作方法。 我们放在下一节中学习。
封装-链表接口
1、定义接口
2、实现接口
3、继承List接口
注意： 需要修改一下length属性，再额外实现一个peek()方法。
封装-append()
append()：(el)，向链表尾部添加一个新的元素。
思路：向链表尾部追加数据可能有两种情况：
- 链表本身为空，新添加的数据时唯一的节点。
- 链表不为空，需要向其他节点后面追加节点。
图解：
实现代码：
测试：
封装-traverse()
traverse()：()，遍历链表中的每一个元素。
思路：
为了可以方便的看到链表上的每一个元素，我们实现一个遍历链表每一个元素的方法：
- 这个方法首先将当前结点设置为链表的头结点。
- 然后，在while循环中，我们遍历链表并打印当前结点的数据。
- 在每次迭代中，我们将当前结点设置为其下一个结点，直到遍历完整个链表。
代码实现：
测试：
封装-insert()
insert()：(el,pos)，向链表的特定位置插入一个新的元素。
思路图解：
接下来实现另外一个添加数据的方法：在任意位置插入数据。
情况一：添加到第一个位置：
- 添加到第一个位置，表示新添加的节点是头，就需要将原来的头节点，作为新节点的next
- 另外这个时候的head应该指向新节点。
情况二：添加到其他位置：
- 如果是添加到其他位置，就需要先找到这个节点位置了。
- 我们通过while循环，一点点向下找。 并且在这个过程中保存上一个节点和下一个节点。
- 找到正确的位置后，将新节点的next指向下一个节点，将上一个节点的next指向新的节点。
代码实现：
测试：
封装-removeAt()
removeAt()：(pos)，从链表的特定位置移除一项。
思路图解：
移除数据有两种常见的方式：
- 根据位置移除对应的数据
- 根据元素，先找到对应的位置，再移除元素
情况一：移除第一项的信息：
- 移除第一项时，直接让head指向第二项信息就可以啦。
- 那么第一项信息没有引用指向，就在链表中不再有效，后面会被回收掉。
情况二：移除其他项的信息：
- 移除其他项的信息操作方式是相同的。
- 首先，我们需要通过while循环，找到正确的位置。
- 找到正确位置后，就可以直接将上一项的next指向current项的next，这样中间的项就没有引用指向它，也就不再存在于链表后，会面会被回收掉。
代码实现：
测试：
封装-get()
get()：(pos)，获取对应位置的元素。
思路图解：
代码实现：
测试：
重构方法 getNode()
封装getNode()
getNode()：(pos)，根据pos获取到当前的节点(不是节点value)。
因为遍历节点的操作我们需要经常来做，所以可以进行如下的封装：
重构-get()：
重构-removeAt()：
问题：返回的删除项不对
解决：给current重新赋值
重构-insert()：
封装-update()
update()：(el,pos)，修改某个位置的元素。
代码实现：
测试：
封装-indexOf()
indexOf()：(el)，返回元素在链表中的索引。如果链表中没有该元素则返回-1。
我们来完成另一个功能：根据元素获取它在链表中的位置
代码实现：
测试：
封装-remove()
remove()：(el)，从链表中移除一项。
代码实现：
有了上面的indexOf方法，我们可以非常方便实现根据元素来删除信息
测试：
封装-isEmpty()
isEmpty()：()，如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
代码实现：
测试：
面试题
设计链表
设计链表的实现。
- 您可以选择使用单链表或双链表。
- 单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。
- 如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
解答： 见封装链表
删除链表中的节点
有一个单链表的 head，我们想删除它其中的一个节点 node。
- 给你一个需要删除的节点 node 。
- 你将无法访问第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
- node 前面的所有值顺序相同。
- node 后面的所有值顺序相同。
思路： 删除5节点：将1的值赋值给5，并通过5.next = 5.next.next删除1节点。本质上其实是删除1节点
解答：
反转链表
题目：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
▸ 解答：反转链表-栈
▸ 解答：反转链表-非递归
▸ 解答：反转链表-递归
算法复杂度
现实案例
前面我们已经解释了什么是算法？其实就是解决问题的一系列步骤操作、逻辑。
对于同一个问题，我们往往其实有多种解决它的思路和方法，也就是可以采用不同的算法。
- 但是不同的算法，其实效率是不一样的。
举个例子（现实的例子）：在一个庞大的图书馆中，我们需要找一本书。
在图书已经按照某种方式摆好的情况下（数据结构是固定的）
方式一：顺序查找
- 一本本找，直到找到想要的书；（累死）
方式二：分类查找
- 先找到分类，在分类中再顺序或者某种方式查找；
方式三：找到一台电脑，查找书的位置，直接找到；
图书馆通常有自己的图书管理系统；
利用图书管理系统先找到书的位置，再直接过去找到；
程序案例
再举一个程序中的案例：让我们来比较两种不同算法在查找数组中（数组有序）给定元素的时间复杂度。
方式一: 顺序查找
- 这种算法从头到尾遍历整个数组，依次比较每个元素和给定元素的值。
- 如果找到相等的元素，则返回下标；如果遍历完整个数组都没找到，则返回-1。
方式二：二分查找
- 这种算法假设数组是有序的，每次选择数组中间的元素与给定元素进行比较。
- 如果相等，则返回下标；如果给定元素比中间元素小，则在数组的左半部分继续查找；
- 如果给定元素比中间元素大，则在数组的右半部分继续查找；
- 这样每次查找都会将查找范围减半，直到找到相等的元素或者查找范围为空；
查找算法
顺序查找
顺序查找：是最简单的查找方法，逐一检查数组中的每个元素，直到找到目标元素或遍历完所有元素。
思路：
- 从数组的第一个元素开始，依次与目标元素进行比较。
- 如果当前元素等于目标元素，则返回该元素的索引。
- 如果遍历完整个数组都没有找到目标元素，则返回一个表示“未找到”的标志（通常是 -1）。
代码实现：
时间复杂度：
- 最坏情况时间复杂度：O(n)：在最坏的情况下，目标元素可能位于数组的最后一个位置，或者根本不存在。
- 最佳情况时间复杂度：O(1)：如果目标元素是数组的第一个元素，则只需一次比较。
优缺点：
- 优点：实现简单，适用于无序数组。
- 缺点：查找效率较低，对于大数组，尤其是目标元素在数组末尾时，效率较差。
二分查找
二分查找：是一种高效的查找算法，通常用于已排序的数组。它通过每次将查找区间对半分，迅速缩小查找范围，从而提高查找效率。
思路：
- 首先，确定数组的中间元素。
- 如果中间元素是目标元素，查找成功，返回该元素的索引。
- 如果目标元素小于中间元素，则继续在左半部分查找。
- 如果目标元素大于中间元素，则继续在右半部分查找。
- 重复以上步骤，直到找到目标元素或查找区间为空。
图解：
代码实现：
时间复杂度：
- 时间复杂度：O(log n)：每次查找将数组分成两部分，因此查找效率是对数级别。
- 空间复杂度：O(1)：二分查找只需要常数级别的额外空间。
优缺点：
- 优点：查找效率高，适用于已排序的数组。特别是在大规模数据中，性能优势显著。
- 缺点：必须要求数组是已排序的。如果数组未排序，需要先对其进行排序，这可能会影响整体效率。
对比顺序查找：
| 特性 | 顺序查找 (Linear Search) | 二分查找 (Binary Search) |
|---|---|---|
| 适用条件 | 无序数组 | 已排序数组 |
| 时间复杂度 | O(n)（最坏情况） | O(log n)（最坏情况） |
| 空间复杂度 | O(1) | O(1) |
| 查找效率 | 低（尤其是数据量大时） | 高，适用于大规模数据 |
| 优点 | 简单实现，适用于无序数据 | 高效，适用于已排序的数据 |
| 缺点 | 查找效率低，特别是数据量大时 | 必须要求数据预先排序 |
测试效率
顺序查找：
顺序查找算法的时间复杂度是O(n)
二分查找：
二分查找算法的时间复杂度是O(log n)
大O表示法
概念
大O表示法（Big O Notation） 是计算机科学中用于描述算法性能的一种数学符号，特别是用来描述算法的 时间复杂度 和 空间复杂度。它提供了一个简洁的方式来分析和比较不同算法在不同规模输入下的效率。
O 这个记号则是在德国数论学家爱德蒙·兰道的著作中才推广的，因此它有时又称为兰道符号（Landau symbols）。
由来：代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。
作用：大O符号在分析算法效率的时候非常有用。
举个例子，解决一个规模为n的问题所花费的时间（或者所需步骤的数目）可以表示为：T(n) = 4n² - 2n + 2
当n增大时，n²项开始占据主导地位，其他各项可以被忽略；
举例说明：当n=500。4n²项是2n项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
进一步看，如果我们与任一其他级的表达式比较，n²的系数也是无关紧要的。
我们就说该算法具有n²阶（平方阶）的时间复杂度，表示为O(n²)。
常见对数阶
常用的对数阶
空间复杂度
空间复杂度：指的是程序运行过程中所需要的额外存储空间。
空间复杂度也可以用大O表示法来表示；
空间复杂度的计算方法与时间复杂度类似，通常需要分析程序中需要额外分配的内存空间，如数组、变量、对象、递归调用等。
举个栗子：递归算法
对于一个简单的递归算法来说，每次调用都会在内存中分配新的栈帧，这些栈帧占用了额外的空间。
因此，该算法的空间复杂度是O(n)，其中n是递归深度。
举个栗子：迭代算法
而对于迭代算法来说，在每次迭代中不需要分配额外的空间，因此其空间复杂度为O(1)。
算法优化：
当空间复杂度很大时，可能会导致内存不足，程序崩溃。
在平时进行算法优化时，我们通常会进行如下的考虑：
- 使用尽量少的空间（优化空间复杂度）
- 使用尽量少的时间（优化时间复杂度）；
- 特定情况下：使用空间换时间或使用时间换空间
对比数组、链表
接下来，我们使用大O表示法来对比一下数组和链表的时间复杂度：
数组 是一种连续的存储结构，通过下标可以直接访问数组中的任意元素。
- 时间复杂度：对于数组，随机访问时间复杂度为O(1)，插入和删除操作时间复杂度为O(n)。
- 空间复杂度：数组需要连续的存储空间，空间复杂度为O(n)。
链表 是一种链式存储结构，通过指针链接起来的节点组成，访问链表中元素需要从头结点开 始遍历。
- 时间复杂度：对于链表，随机访问时间复杂度为O(n)，插入和删除操作时间复杂度为O(1)。
- 空间复杂度：链表需要为每个节点分配存储空间，空间复杂度为O(n)。 数组和链表的复杂度对比
实际开发中，选择使用数组还是链表 需要根据具体应用场景来决定。
- 如果数据量不大，且需要频繁随机 访问元素，使用数组可能会更好。
- 如果数据量大，或者需要频繁插入 和删除元素，使用链表可能会更好。
循环链表
概述
前面我们已经从零去封装了一个链表结构，其实我们还可以封装更灵活的链表结构：循环链表和双向链表。
循环链表(Circular LinkedList) 是一种特殊的链表数据结构。在普通链表的基础上，最后一个节点的下一个节点不再是null，而是指向链表的第一个节点。这样形成一个环，使得链表能够被无限遍历。
我们可以在单向循环链表中从任意一个节点出发，不断地遍历下一个节点，直到回到起点。
实现方式：单向循环链表我们有两种实现方式：
- 方式一：从零实现一个新的链表，包括其中所有的属性和方法。
- 方式二：继承之前封装的LinkedList，只实现差异化的部分。
循环链表实现
封装-CircularLinkedList
重构-LinkedList
导出LinkedList类，并将属性有private修改为protected
继承-LinkedList
重构-新增-tail
tail：Node | null，默认：null，指向链表尾部的属性。
新增tail属性，让其总是指向链表的尾部，默认指向null
重构-append()
图解：
代码实现：
重构-insert()
图解：
代码实现：
重构-removeAt()
图解：
情况一：删除时表中只有一个节点，让rail指向null
情况二：删除的是最后一个节点，让tail指向previous
代码实现：
重构-新增-isTail()
isTail()：(node)，判断是否是最后一个节点。
实现-append()
append()：(el)，向链表尾部添加一个新的元素。并让尾部节点的next指向第一个节点。
图解：
代码实现：
测试：
重构-traverse()
traverse()：()，遍历链表中的每一个元素。
实现-insert()
insert()：(el,pos)，向链表的特定位置插入一个新的元素。
图解：
当新增节点到尾部时，要将它的next指向第一个节点
当新增节点到第一个节点时，要将尾部节点的next指向新增节点
代码实现：
测试：
实现-removeAt()
removeAt()：(pos)，从链表的特定位置移除一项。
图解：
如果删除的是第一个节点，需要将尾部的next指向新的头部
如果删除的是尾部，需要将新尾部的next指向头部
如果删除的节点是仅剩的节点，不要指定next
代码实现：
测试：
重构-indexOf()
indexOf()：(el)，返回元素在链表中的索引。如果链表中没有该元素则返回-1。
代码实现：
测试：
双向链表
概述
双向链表(Doubly Linked List) 是一种常用的链表数据结构，其中每个节点不仅有指向下一个节点的引用（next），还有指向上一个节点的引用（prev）。相比于单向链表，双向链表提供了双向的遍历能力，可以更灵活地进行数据的插入、删除操作。
优点：
- 双向访问：双向链表可以从两端遍历，支持从头到尾和从尾到头的操作，操作更加灵活。
- 高效的删除操作：在已知节点的情况下，删除操作可以在常数时间内完成。只需要修改相邻节点的指针，不需要遍历整个链表。
缺点：
- 实现复杂度高：每次在插入或删除某个节点时, 需要处理四个引用, 而不是两个，实现起来要困难一些。
- 空间开销较大：并且相当于单向链表, 必然占用内存空间更大一些。
结构图解：
双向链表的实现
双向链表中添加、删除方法的实现和单向链表有较大的区别，所以我们可以对其方法进行重新实现：
- append()：
(el)，向链表尾部添加一个新的元素。 - insert()：
(el,pos)，向链表的特定索引位置插入一个新的元素。可以是头部、尾部和中间位置。 - removeAt()：
(pos)，从链表的特定索引位置移除一项。 - 额外的API：
- prepend()：
()，在头部添加元素。 - postTraverse()：
()，从尾部遍历所有节点。
那么接下来我们就一个个实现这些方法，其他方法都是可以继承的。
封装-DoublyNode
双向链表的节点，需要进一步添加一个prev属性，用于指向前一个节点：
1、导出之前的Node类，该类中有value和next属性
2、封装DoublyNode继承Node类，并添加prev属性、重写next属性
3、测试
封装-DoublyLinkedList
封装DoublyLinkedList类，并继承自LinkedList类，并重写head和tail属性的类型
上述重写head和tail属性的类型，可以解决以下的问题：
封装-append()
append()：(el)，向链表尾部添加一个新的元素。
图解：
如果链表中一开始没有节点，添加后head、tail指向新节点
如果链表中一开始有节点
代码实现：
测试：
封装-prepend()
prepend()：()，在头部添加元素。
图解：
如果链表中一开始没有节点，添加后head、tail指向新节点
如果链表中一开始有节点
代码实现：
测试：
封装-postTranverse()
postTraverse()：()，从尾部遍历所有节点。
图解：
代码实现：
测试：
封装-insert()
insert()：(el,pos)，向链表的特定索引位置插入一个新的元素。可以是头部、尾部和中间位置。
图解：
如果插入到头部，直接调用prepend()方法
如果插入到尾部，直接调用apend()方法
如果插入到中间：
代码实现：
思考： 如果将getNode()方法在子类中通过super.getNode()执行一遍，返回的类型是不是就变成了DoublyNode？
TODO:
测试：
封装-removeAt()
removeAt()：(pos)，从链表的特定索引位置移除一项。
图解：
如果删除头部
如果只有一个节点
如果有多个节点
如果删除尾部
如果只有一个节点，和第一种情况一样
如果有多个节点
如果删除中间
代码实现：
测试：
