# 链表

# 背景

要存储多个元素，数组（或列表）可能是最常用的数据结构。它非常方便，提供了[]语法来访问其元素。但它有个缺点：（在大多数语言中）数组的大小是固定的，并且从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（尽管有来自 Array 类方法可以帮助我们做这些事，但背后的情况同样如此）——《学习 JavaScript 数据结构与算法》 (opens new window)

# 链表数据结构

链表(LinkedList)是一个数据元素按照链式存储结构进行存储的并且逻辑结构上符合一般线性表特性的数据结构。它的数据元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针）组成的（因此形成了元素之间的一对一的关系，也就是线性结构特性）。

它相对于数组的好处是，添加或移除元素的时候不需要移动其他元素。但是链表需要使用指针，并且访问链表中的元素需要从起点（链表首部）开始迭代至你需要的元素。

# 栈、队列与链表的区别

在逻辑结构上，他们都具有线性结构也就是线性表的特性（有唯一的前驱和后继），栈和队列属于受限线性表（受限表示对结点的操作受限制），而链表属于一般线性表（也就是不受限）。
在存储结构上，栈和队列是顺序存储结构，也就是用一组地址连续的存储单元依次存储线性表中的数据元素；而链表就不一样了，它是链式存储结构，也就是用一组任意的存储单元存储线性表中的数据元素（可连续也可不连续）。

# 链表的实现

链表的实现代码细节：linked-list.ts (opens new window)

1.需要准备一个助手类Node (opens new window)，这个助手类有两个属性，一个是本身的值，另一个是指向下一个 Node 的指针。

2.声明一个 protected 级别的变量 head，用于追踪首部元素；声明一个 count 用于记录链表的大小；声明一个 equalsFn，保存实例化时传来的“比较函数”。

3.返回链表中特定位置的元素 getElementAt：
从 head 首部元素开始向后遍历，直到遍历到指定位置就返回这个位置的项，当然如果当前项是空的自然就中断遍历返回空结果。

4.返回元素在链表中的索引 indexOf：
从 head 首部元素开始向后遍历，直到当前项与目标项通过 equalsFn 对比结果为相同时结束遍历并返回当前项的索引，遍历完都没找到相同的话就返回-1，当然如果当前项是空的自然就中断遍历返回-1。

5.往链表尾部添加元素 push：
链表为空时，添加的新元素就是 head 首部元素；链表不为空时，需要将新元素追加到尾部，用迭代的方式（getElementAt 方法）拿到尾部元素（node.next 为空时代表 node 就是尾部元素）。最后记得更新 count 的值。

    6.从链表中移除元素 removeAt：
        和 push 类似，当链表只有一个元素时只需把 head 清空；当链表元素多于一个时，需要迭代（getElementAt 方法）到指定位置再将其移除，移除后还要把它的 next 与它的上一个位置连接起来，保证移除一个元素后链表是完整的。
        扩展：用 indexOf 和 removeAt 配合可以组成新的移除方法，就是移除与指定项相同的元素（目前只能移除一个）。

7.往链表首部添加元素 unshift：
链表为空时，添加的新元素就是 head 首部元素；链表不为空时，需要将新元素的 next 指向 head，然后再把新元素赋给 head 以完成新元素与链表的连接。最后记得更新 count 的值。

8.往链表中特定位置插入一个新元素 insert：
要放到第一个位置时，其实就是调用 unshift；其他情况，需要拿到指定位置的前一个位置的元素，并把这个元素的 next 赋给新元素，再让这个元素的 next 指向新元素，以完成链表的连接。最后记得更新 count 的值。

9.链表的其他方法 isEmpty、size、clear、toString 很好实现。

# 双向链表数据结构

双向链表(DoublyLinkedList)是一个特殊的链表。区别就是它的数据元素由一个存储元素本身的节点、一个指向下一个元素的引用、一个指向上一个元素的引用组成的。也就是说双向链表拥有双向的引用，而链表拥有单向的引用。

# 双向链表的实现

双向链表的实现代码细节：doubly-linked-list.ts (opens new window)

1.我们需要准备一个跟 Node 不一样的助手类DoublyNode (opens new window)，这个助手类有三个属性，一个是本身的值，另一个是指向下一个 DoublyNode 的指针，最后一个是指向上一个 DoublyNode 的指针。

2.我们让 DoublyLinkedList 继承 LinkedList，可以使用父类的方法和属性。声明两个属性，head 指向首部元素（第一个），tail 指向尾部元素（最后一个），记得类型得是 DoublyNode，其他的同 LinkedList。

3.往双向链表尾部添加元素 push：
链表为空时，将新元素赋给 head 和 tail；链表不为空时，需要将新元素追加到尾部，也就是将新元素的 next 指向 tail 的 next，新元素的 prev 指向 tail，但此时的链表还没指向新元素，那么就让 tail 的 next 指向新元素，最后把 tail 更新也就是把新元素赋给 tail（这四个步骤要仔细理清楚）。最后记得更新 count 的值。

4.往双向链表首部添加元素 unshift：
链表为空时，将新元素赋给 head 和 tail；链表不为空时，需要将新元素追加到首部，也就是将新元素的 prev 指向 head 的 prev，新元素的 next 指向 head，但此时的链表还没指向新元素，那么就让 head 的 prev 指向新元素，最后把 head 更新也就是把新元素赋给 head（这四个步骤有个别顺序不能打乱，自己理一理）。最后记得更新 count 的值。

5.在双向链表的任意位置插入新元素 insert：
当要插入的位置是第一个位置或者最后一个位置，相当于调用 unshift 或 push 方法；其他场景，需要拿到指定位置的前一个位置的元素，然后把新元素连接到刚刚这元素后面，再更新一些引用（指针），例如：新元素的 next 要指向刚刚这元素的 next，新元素的 next 的 prev 要指向新元素，新元素的 prev 要指向刚刚这元素，刚刚这元素的 next 要指向新元素（比起 unshift 和 push 要复杂，理清楚就好了）。最后记得更新 count 的值。

    6.从双向链表中移除元素 removeAt：
        当链表只有一个元素时只需把 head 和 tail 清空；当移除的是首部元素时，需要将 head 指向 head 的 next，再把 head 的 prev 置空即可；当移除的是尾部元素时，需要将 tail 指向 tail 的 prev，再把 tail 的 next 置空即可；需要迭代（getElementAt 方法）到指定位置，再把这个位置的 prev 的 next 指向这个位置的 next，再把这个位置的 next 的 prev 指向这个位置的 prev，这样就可以把这个位置上的元素从双向链表中移除。
        扩展：用 indexOf 和 removeAt 配合可以组成新的移除方法，就是移除与指定项相同的元素（目前只能移除一个）。

7.双向链表的其他方法 isEmpty 和 size 继承父类即可，clear 需要先调父类的 clear 然后再清空 tail，toString 逻辑跟父类一样只是里面用的是 DoublyNode，inverseToString 跟 toString 类似，只需要将 head 换成 tail 然后 next 换成 prev 即可。

# 循环链表数据结构

在链表的基础上，将尾部元素的 next 指向首部元素而不是置空，以此形成循环。

# 循环链表的实现

循环链表代码细节：circular-linked-list.ts (opens new window)

循环链表是基于链表的，那么让 CircularLinkedList 继承 LinkedList，再重写 push、unshift、removeAt 方法。很简单，先 super 调用父类的同名方法，再调一下固定方法 formingCycle 以此形成循环。formingCycle 方法其实就是遍历链表找到尾部元素，然后将尾部元素的 next 指向 head 即可。

# 双向循环链表数据结构

在双向链表的基础上，将尾部元素的 next 指向首部元素，将首部元素的 prev 指向尾部元素，以此形成循环。

# 双向循环链表的实现

双向循环链表代码细节：doubly-circular-linked-list.ts (opens new window)

双向循环链表是基于双向链表的那么让 DoublyCircularLinkedList 继承 DoublyLinkedList，再重写 push、unshift、removeAt 方法。很简单，先 super 调用父类的同名方法，再调一下固定方法 formingCycle 以此形成循环。formingCycle 方法其实就是将 tail 的 next 指向 head 再将 head 的 prev 指向 tail。

# 有序链表数据结构

保证元素按照一定规则顺序插入的链表结构。（这个顺序指的是元素的值的顺序，而链表本身因为指针也是有顺序的，要区别开这两个“顺序”）

# 有序链表的实现

有序链表代码细节：sorted-linked-list.ts (opens new window)

有序链表是基于单向链表的，也可以用双向的，这里实现的是单向的有序链表。让 SortedLinkedList 继承 LinkedList，声明一个 compareFn 属性（初始化时默认传的是升序比较函数）。
push、unshift 其实相当于调用 insert，因为插入都要走统一的比较方法。在插入时，要比较新元素与链表里元素的值，这里因为是升序，所以必选找到比新元素的大的位置，这个位置将会由新元素插入，当然旧元素会补到这个新元素的 next 上，以此形成升序；如果找不到比新元素的大的位置，那么新元素会放到尾部元素的 next 上，因为它最大。

# 基于双向链表的栈数据结构

实现栈时，我们也可以选用双向链表，当然你选单向链表也是可以的（要稍微调整一下代码）。

# 基于双向链表的栈的实现

基于双向链表的栈代码细节：stack-linked-list.ts (opens new window)

声明一个私有变量_items，类型为 DoublyLinkedList，入栈时就调用双向链表的 push 方法，而出栈时就调用双向链表的 removeAt(this.size() - 1)，查看栈顶元素就调用双向链表的 getTail 方法，其他的功能很好实现。

← 3.队列 5.集合 →