链表

1. Introduction

链表是一种由一群结点组成顺序的数据结构。在最简单的情况下，每个结点由一个数据和一个指向在顺序中下一个结点的指针（即连接）而组成。点击Search(77)来观看在一个（单项）链表中搜索一个值的可视化。链表以及它的变种可以作为实现堆栈，队列，和双向队列抽象数据类型（如果你不熟悉这个词，可以阅读这篇维基百科：https://zh.wikipedia.org/zh-cn/%E6%8A%BD%E8%B1%A1%E8%B3%87%E6%96%99%E5%9E%8B%E5%88%A5）的底层数据结构。

在这个可视化中，我们会讨论单向链表（只有下指针）及它的两个变种：堆栈和队列，以及双向链表（有下指针和上指针）和它的变量：双端队列。

1-1. 5种模式

这里我们将把五种不同的数据结构包括链表（Linked List），栈（Stack)，队列（Queue），双向链表（Double LinkedList)，双端队列（Double Ended Queue)全部放在链表的环节下。为了多样性，当加载https://visualgo.net/zh/list 时我们会随机选择一种模式。

但是，您可以直接使用以下URL快捷方式访问单个模式（已登陆的用户只有看完3章节后才可解锁）：

2. 动机

计算机科学本科专业经常会教链表数据结构。原因如下：

它是一个简单的线性数据结构。
做为一个抽象数据类型，它有很广泛的应用。比如，学生名单，活动清单，约会清单等（尽管还有其他更高级的数据结构可以更好地完成相同的应用程序），也可以用来实现堆栈/队列/ 双端队列。
有些比较特殊的情况来说明为什么需要选择一个合适的数据结构去实现你的目的。
它具有各种定制的方式，因此通常在面向对象编程（OOP）中来教这种链表数据结构。

2-1. 列表抽象数据类型

列表的顺序是非常重要的。其中位置顺序{a₀, a₁, ..., a_N-2, a_N-1 }。常见列表ADT操作为：

获取（i）- 也许是一个微不足道的操作，返回a_i的值（基于0的索引），
搜索（v ）-决定是否存在项/数据v（并报告其位置）或不存在（并且通常在列表中报告不存在的索引-1），
插入（i，v）-插入项目/数据v，在列表中的位置/索引 i，这个操作会有一个可能的问题在与他需要把索引i后面的所有数据都向后移动一位。
删除（i）- 删除列表中特定位置/索引i的项，这可能会让这个数据i后面的数据全部向前移动一位。

讨论：如果我们想要在列表中移除一个具体的值v，我们要如何做？

2-2. 结果

[This is a hidden slide]

2-3. 数组实现 - 第一部分

（紧凑）数组是实现列表ADT（抽象数据类型）的一个很好的候选对象，因为它是处理项目集合的简单结构。
当我们说密集数组（compact array) 时，我们指的是一个没有间隙的数组，即如果数组中有n个项（数组大小m，m>=n），那么只有索引[0…n-1 ]的空间被占用，其他索引[n.M.1]应该保持空。

2-4. 数组实现 - 第二部分

让紧凑数组名称为A，它的索引是[0..N-1] 的。

获取（i），返回A[i]。如果数组不紧凑，这个简单的操作将会不必要地复杂化。
搜索（v），我们逐一检查每个索引i∈ [0…n-1 ]，看看是否A[i]==v。这是因为v（如果存在）可以在索引[0…n-1 ]中的任何地方。
插入（i，v），我们将项[i，N-1 ]移到[i+1...N]（从最后面往后移动），并设置一个A[i]＝v。这使得v在索引i中被正确插入并依旧保持紧凑性。
删除（i），我们将项 ∈ [i+1…N-1 ]移到[i, N-2]，重写旧A[i]。这是为了保持紧凑。

2-5. 时间复杂性小结

get(i), 非常快：只需要访问一次，O（1）。另一个CS模块：“计算机架构”会讨论了这个数组索引操作的O（1）性能的细节。
search(v), 在最佳情况下，v在第一位置O（1）中找到。在最坏的情况下，在列表中没有发现V，并且我们需要O（n）扫描来确定。
insert(i, v), 在最佳情况下插入（i，v），在i＝n处插入，没有元素的移位，O（1）。在最坏的情况下，在i＝0处插入，我们移动所有n个元素，O（n）。
remove(i), 在最佳情况下，在i＝n-1处移除，没有元素的移位，O（1）。在最坏的情况下，在i＝0处移除，我们移动所有n个元素，O（n）。

2-6. 固定空间问题

密集阵列(compact array)的大小是M且不是无限的，而是有限的数。这带来了一个问题，因为在许多应用中，你可能事先不知道数组的大小。
如果M太大，那么闲置的空间就会被浪费掉。如果M太小，那么我们很容易耗尽空间。

2-7. 变量空间

解决方案：使M成为变量。因此，当数组满时，我们创建一个更大的数组（通常是两倍大），并将元素从旧数组移动到新数组。因此，除了（通常很大的）物理计算机存储器大小之外，没有更多的限制。
C++ STL std::vector, Python list, Java Vector, 或者 Java ArrayList 实现所有可变大小的数组列表。
然而，经典的基于数组的空间浪费和复制/转移项目的浪费仍然是有问题的。

2-8. 观察

对于固定大小的集合，如果我们知道它最多有多少个元素，比如最多是M个元素，那么简单数组（array)可以被考虑去实现你的需要。
对于具有未知大小m的可变大小的集合，以及诸如插入/移除之类的动态操作是常见的，简单数组(array)会是一个糟糕的选择。
对于这样的应用，有更好的数据结构。让我们阅读…

3. 链表（LL）

现在我们介绍链表数据结构。它使用指针来允许条目/数据在内存中不连续（这是一个简单数组的主要区别）。通过将项目i与其相邻项i+1通过指针相关联，将项目从索引0排序为索引N-1。

3-1. 链表的顶点C++实现

在其基本形式中，链表中的单个顶点（节点）具有这种结构：
struct Vertex { //我们可以使用C struct 或C++/python/java class

int item;//数据存储在这里，在这个例子中是一个整数
Vertex* next;//这个指针告诉我们下一个顶点在哪里
}；
使用以上示例的默认示例链接列表[22 (头)->2->77->6->43->76->89 (尾)] ，我们具有：a₀，其项＝22，它的next＝a₁，其项＝2，它的next＝a₂，…a₆，其项＝89，它的next＝null。
讨论：结构和类，哪一个更适合用C++实现链表？Python和Java呢？

3-2. 答案

[This is a hidden slide]

3-3. 链表，其他数据元素

We also have a few additional data that we remember in this Linked List data structure. We use the default example Linked List [22 (head)->2->77->6->43->76->89 (tail)] for illustration.

The head pointer points to a₀ — it is 22, nothing points to the head item,
The current number of elements N in the Linked List — N = 7 elements.
The tail pointer points to a_N-1 — it is a₆ = 89, nothing is after the tail item.

That's it, we only add three more extra variables in data structure.

3-4. 变化

请注意，在许多计算机科学教科书中关于如何实现一个（单）链表有这各种细微差别，例如（使用尾指针或不使用，循环或否，使用虚设头项），请参阅此幻灯片。
我们在这个可视化中的版本（有尾部指针，不是循环的，没有虚设头项）可能与你在课堂上学习的不大相同，但是基本的想法应该不变。
在这个可视化中，每个顶点都有整数项，但是根据需要可以很容易地将其更改为任何其他数据类型。

3-5. 获取（i）- 比数组慢很多

因为我们只保留头和尾指针，所以需要一个遍历列表的子程序来寻找到除了头部（索引0）和尾部（索引N-1）之外的位置。

由于这个子程序是如此频繁使用，所以我们将把它抽象为一个函数。下面的代码是用C++编写的。

Vertex* Get(int i) { // 返回所需顶点
  Vertex* ptr = head; // 我们只能从头部开始
  for (int k = 0; k < i; ++k) // 循环 i 次
    ptr = ptr->next; // 将指针移向更靠后的索引
  return ptr;
}

它在O（N）中运行，因为 i 可能和 N-2 一样大。将此与简单数组进行比较（我们可以在O（1）时间内访问索引 i）

3-6. 搜索（v）-不优于数组

由于我们只能够直接引用第一个头部项目和最后一个尾部项目，再加上指针指向右边（更高的位置/索引），我们只能从头部项目开始并通过下一个指针跳转来访问其余部分。在示例[22 (head)->2->77->6->43->76->89 (tail)]上,：
Search(77) - 在上面的的例子中找到位置/索引2（基于0的索引）。
Search(7) - 在上面的示例中检查完所有的N项之后，我们发现没有找到。因此在最坏情况下search(v)的时间复杂度O(n)。

3-7. 插入 - 四种情况

There are more cases than array version due to the nature of Linked List.

Most CS students who learn Linked List for the first time usually are not aware of all cases until they figure it out themselves when their Linked List code fail.

In this e-Lecture, we directly elaborate all cases.

For insert(i, v), there are four (legal) possibilities, i.e., item v is added to:

The head (before the current first item) of the linked list, i = 0,
An empty linked list (which fortunately similar to the previous case),
The position beyond the last (the current tail) item of the linked list, i = N,
The other positions of the linked list, i = [1..N-1].

3-8. 插入（i, v) - 在头节点插入（i=0)

在头节点插入代码(C++)简单而有效，O（1）：

Vertex* vtx = new Vertex(); // 创建新节点vtx

vtx->item = v;

vtx->next = head; // vtx指向(旧）的头节点

head = vtx; // vtx变成新的头节点

尝试一下InsertHead(50)，在示例链表[22 (head)->2->77->6->43->76->89 (tail)]上insert(0, 50)。
讨论：如果我们使用简单数组实现来插入列表的头，会发生什么？

3-9. 答案

[This is a hidden slide]

3-10. 插入(i, v) - 插入v到一个空的链表

空数据结构是一个常见的极端/特殊情况，如果没有正确测试，常常会导致意外的崩溃。将新项目插入到当前空列表中，即在索引i＝0中是有效的。幸运的是，插入头部的伪代码也适用于空列表，在这里我们使用与此幻灯片.中相同的代码（小小的不同在于我们还需要设置 tail = head）。
尝试InsertHead(50)（insert(0, 50)），它在空链表 [] 上插入 (0, 50)。

3-11. 插入（i, v) - 在[1, N-1] 种插入

通过遍历链表 Get(i) 子例程，我们现在可以实现链表中间的插入如下（C++）：

Vertex* pre = Get(i-1);/ /遍历到第（i-1）个节点，O（n）
aft = pre.next//aft不能为null

Vertex vtx = new Vertex(); // 创建新节点

vtx->item = v;

vtx->next = aft; //vtx的下一个指针设置为aft

pre->next = vtx; // pre的下一个指针设置为vtx

点击Insert(3, 44)在示例链表[22 (head)->2->77->6->43->76->89 (tail)]上尝试以上步骤。
也尝试一下Insert(6, 55)，这一个极端情况：插入尾部的位置，把尾部指针移到右边的一个位置。由于需要遍历列表（例如，如果i接近n-1），这个操作很缓慢的，O（n）。

3-12. 插入(i, v) -

如果我们还记得尾部指针在这个电子讲座中的实现（这是可取的，因为它只是一个附加的指针变量），我们可以有效地在 O(1) 在尾部项目（i = N）上进行插入：

Vertex* vtx = new Vertex(); // C++
vtx->item = v; // 用 v 创建一个新的节点 vtx
tail->next = vtx; // 把尾部和 vtx 连起来
tail = vtx; // 现在更新尾部指针

在上面的示例链表上尝试InsertTail(10)，即insert(7, 10)。一种常见的误解是说这是尾部插入。在尾部元素插入是插入（N-1，v）。插入（N, v) 则超出尾部。

讨论：如果我们用数组来实现超过尾部的插入会怎么样呢？

3-13. 答案

[This is a hidden slide]

3-14. 移除 - 三种情况

对于 remove(i)，有三种可能性：

链表的头（当前第一项），i＝0，它影响头指针。
链表的尾部，i＝N-1，它影响尾部指针
链表的其他位置，i＝ [1…N-2]。

讨论：将该幻灯片与插入幻灯片进行比较，以实现细微差别。从一个空链接列表中删除任何东西是有效的操作吗？

3-15. 移除（i）- 在头节点移除(i = 0)

这种情况很简单：

if (head == NULL) return; // 避免当SLL为空时崩溃

Vertex* temp = head; // 之后我们可以删除它

head = head->next; // 更新头部指针

delete temp; // 删除旧指针

在上面的（较短）示例链表 [22 (head)->2->77->6 (tail)] 上反复尝试RemoveHead()。它将继续正确地工作直到链表包含一个项目，其中头=尾部项目。如果LL已经是空的，因为它是无效的，我们阻止执行。

讨论：如果我们使用简单数组实现来移除列表的头，会发生什么？

3-16. 答案

[This is a hidden slide]

3-17. 移除（i）- 在[1, N-2]种移除

通过遍历链表获取（i）子例程（之前讨论过），我们现在可以实现链表的中间项的移除（一下为C++代码）：
Vertex* pre = Get(i-1);/ /遍历到第（i-1）节点，O（n）
Vertex* del = pre->next, aft = del->next;

pre->next = aft; // 忽略del

delete del;

尝试Remove(5)，索引N-2处的元素（在示例[22 (head)->2->77->6->43->76->89 (tail)] 中，N = 7。这是上面例子中最坏的O(N) 情况。

注意，删除（N-1）是在尾部移除，要求我们更新尾部指针，见下一个案例。

3-18. Remove(i) - At Tail (i = N-1) - 第一部分

我们可以实现链表尾部的移除，假设链表有超过1项：

Vertex* pre = head;
temp = head->next;
while (temp->next != null) // 当下一个指针不是空
  pre = pre->next, temp = temp->next;
pre->next = null; // 或者 pre = Get(N-2), temp = Get(N-1)
delete temp; // temp = 旧的尾部指针
tail = pre; // 更新尾部指针

在（较短的）示例链接列表 [22 (head)->2->77->6 (tail)] 上重复尝试RemoveTail()。它将一直工作下去直到链表的头项和尾项是同一项，并且我们切换到移除头部情况下。如果LL已经是空的我们不会执行，因为它是无效的。

3-19. Remove(i) - At Tail (i = N-1) - 第二部分

实际上，如果我们要保持链表的大小N不变（与这个幻灯片比较），我们可以遍历这个链表，Get（i）来实现链表尾部的这种移除(以下为C++代码)：

Vertex* pre = Get(N-2); // 到尾部前的一个索引，O（n）

pre->next = null;

delete tail;

tail = pre; // 我们可以访问旧尾

请注意，这个操作是缓慢的，O(N)，仅仅是因为需要将尾部指针从项目N-1从后往前更新一个单元到项目N-2，以便之后的未来插入能保持正确…这种不足将在双端链表变体中得到解决。
讨论：如果我们使用简单数组实现来移除列表尾部会发生什么？

3-20. 答案

[This is a hidden slide]

3-21. 时间复杂度小结

get（i）是慢的：O（n）。在链表中，我们需要执行从头部元素的顺序访问。
search（v）在最佳情况下，v在第一位置中找到, O(1)。在最坏的情况下，在列表中没有发现v，并且我们需要O（n）扫描来确定。

insert(i, v)在最佳情况下，插入i＝0或i＝n，在头和尾指针帮助，O（1）。在最坏的情况下，在i＝n-1处插入，我们需要在找到项n-2（在尾部前的一项），O（N）。

删除（i）在最佳情况下，删除i＝0，头指针帮助，O（1）。在最坏的情况下，在i＝n-1处删除，因为需要更新尾指针O（n）。

3-22. 链表的应用

将链表与紧凑数组进行比较，纯（单列）链表应用程序是罕见的，因为更简单的可缩放紧凑数组（vector）可以更好地完成工作。
然而，允许顶点在内存中不连续的链表的基本概念，让堆栈和队列.的可以成为一个极好的可调整大小的数据结构。

4. 堆栈

堆栈是一种特殊的抽象数据结构或者组合，其主要的操作为将元素从头部加入栈中，称为进栈和将头部元素移除，称为出栈。

如下图所示，堆栈是一种后进先出(LIFO-Last-In-First-Out) 的数据结构。

4-1. 设计选择

在大多数实现中，也在这个可视化中，堆栈基本上是一个受保护的（单）链表，在这里我们只能查看头部项目，将新项目推到头部（插入到头部），例如尝试 InsertHead(6)，然后从头部（从头部移除)）移除现有项，例如尝试 RemoveHead()。所有的运算都是O（1）的。
在这个可视化中，单链表是自上而下，头部/尾部项目分别在顶部/底部。在该示例中，我们有 [2 (top/head)->7->5->3->1->9 (bottom/tail)].
讨论：我们可以使用向量，一个大小可变的数组，来实现一个效率更高的堆栈ADT吗？

4-2. 结果

[This is a hidden slide]

4-3. 栈的应用

Stack（堆栈）在教科书中有一些非常经典的应用，例如：

括号匹配，
后缀计算器，
其他一些没有用作教学目的的有趣应用

4-4. 括号匹配问题

数学表达式可以变得相当复杂，例如 {[x+2]^(2+5)-2}*(y+5).
括号匹配问题是检查给定输入中所有括号是否正确匹配的问题，如 (with) 、[with] 和 {with} 等。
括号匹配对于检查源代码的合法性同样有用。
讨论：我们可以使用堆栈的后进先出 (LIFO) 行为来解决这个问题。那么如何解决呢？

4-5. 时间复杂度为O(n)的解法（用栈）

[This is a hidden slide]

4-6. 计算后缀表达式

后缀表达式是一个数学表达式：operand1，operand2，operator格式，不同于我们一般使用的表达式: operand1 operator operand2.
例如，表达式2 3 + 4 *是（2 +3）*4的后缀版本。
在后缀表达式中，我们不需要括号。
讨论：我们还可以使用堆栈来有效地解决这个问题。那如何呢？

4-7. 时间复杂度为O(n)的解法（用栈）

[This is a hidden slide]

5. 队列

队列是另一种特殊的抽象数据结构或者组合，其中的元素遵守一定的顺序。其主要的（仅有的）操作为在表的后端进行插入操作，称之为入队（Enqueue)，以及在表的前端进行删除操作，称之为出队(Dequeue)。

队列又称为先进先出(FIFO-first in first out) 的数据结构。这就意味着最先加入到队列的数据也会是最先出列的数据。

5-1. 数组实现问题 - 第一部分

如果我们简单地使用紧凑数组实现这个队列ADT是a₀是队列的前面，a_n-1是队列的后端，我们将遇到与dequeue(出列）操作相关的主要性能问题。
这是因为在紧凑数组后面的插入速度很快，O（1），但是由于需要移位项目，所以在紧凑数组前面的移除是慢的，请查看此幻灯片。

5-2. 数组实现问题 - 第二部分

另一种可能的数组（Array）实现是通过两个索引来避免在出列操作期间的项目转移：front（队列前端最项目）和back（队列最尾端的项目）。
假设我们使用大小为m＝8项的数组，并且我们的队列的内容如下：[2,4,1,7,-,-,-,-] 具有前面＝0和后面＝3。
如果我们调用dequeue，我们有[-, 4, 1, 1, 7, -，-，-，-]，front = 0＋1＝1，back＝3。
如果我们调用enque(5)，我们有[-,4,1,7,5,-,-,-]，front＝1，back＝3＋1＝4。

5-3. 数组实现问题 - 第三部分

然而，许多出列和如列操作，我们可能有[-,-,-,-,-,6,2,3], front = 5, and back = 7。到目前为止，我们不能插队任何东西，尽管我们在数组的前面有很多空的空间。
如果我们允许前索引和后索引在索引M-1到达索引0时“回滚”到索引，则有效地使数组“循环”，并且我们可以使用空的空间。
例如，如果我们调用 enqueue（8），我们有[8，-，-，-，-，6，2，3]，前面＝5，后面＝（7＋1）% 8＝0。

5-4. 数组实现问题 - 第四部分

然而，这并不能解决数组实现的主要问题：数组的项以连续的方式存储在计算机内存中。
稍后再进行几个入列操作，我们可能有[8，10，11，12，13，6，2，3]，front＝5，back＝4。在这个时候，我们不能将任何其他东西插入队列中。

我们可以放大阵列，例如使 M＝2×8＝16，但是这将需要O（N）的时间把从前（front）到后（back）的所有项再复制一遍，才能得到[6，2，3，8，10，11，12，13，-，-，-，-，-，-，-]，前（front）＝0，后（back）＝7。

备注：如果你理解均摊分析 (amortized analysis)，在环形数组已满的时候，这个繁重的 O(N) 时间开支其实可以被平摊，这样每次入列 (enqueue) 操作仍然保持 O(1)。

5-5. 这个时候就需要用到链表了

回想一下，在队列中，我们只需要列表的两个极端，一个只用于插入（入队），一个用于删除（出列）。
如果我们回顾这个幻灯片，我们看到在单链接列表中尾部中插入和在头部中移除的是非常快的，即O（1）。因此，我们将单链表的头/尾分别指定为队列的前/后。然后，因为链表中的项目没有连续存储在计算机内存中，所以链表的大小可以根据需要增加和缩小。
在我们的可视化中，队列基本上是一个受保护的单链表，在这里我们只能查看头部项目，将一个新的项目排队到在当前尾之后的一个位置，如 Enqueue(random-integer)，并从头部中删除现有的项目，如 RemoveHead()（这也是出列操作）。所有的运算都是O（1）。

5-6. 队列的应用

队列ADT通常用于模拟实际队列。
队列ADT的一个非常重要的应用是在广度优先搜索图遍历算法中。

6. 双向链表（DLL）

双向链表几乎和单向列表一样。唯一的不同是每一个节点都要两个指针。与单向列表相同的是他的继承点都指向下一个节点（如果存在）。但是每个节点有一个额外的指针指向前面的一个节点（如果存在）。

使用这个额外的指针能够让我们从链表的末尾开始向前迭代，但是这样会使用两倍的内存。但是他的好处是我们会很容易的搜索，插入或者删除比较靠后的节点，其时间复杂度是O（1）。如果用单向列表做那么时间复杂度为O（n）。

在这个可视化的课件中，请注意双向链表的边(edge)是无向（其实也就是双向）边。

6-1. Remove(i) - At Tail (i = N-1), 重新访问

在单链表中删除尾元素的主要问题是我们必须更新尾部指针，以便在删除后尾部指针能指向一个项目(即使我们可以通过尾指针直接访问尾项)。
双链表的可以从后面向前移动，我们可以找到尾部指针前的一个项目通过tail->prev…因此，我们可以通过这种方式实现尾部的移除：
Vertex* temp = tail; / /记住尾部项目
tail = tail->prev; //实现O（1）性能的关键步骤
tail->next = null; //删除这个悬空引用

delete temp; // 删除旧的尾部指针；
现在这个操作是O（1）。尝试RemoveTail()示例DLL [22（head）< - > 2 < - > 77 < - > 6 < - > 43 < - > 76 < - > 89（tail）]。

6-2. 固定常数额外的步骤

由于每个顶点都有一个指针PREV，所以在每次插入或删除时，它们的值也需要更新。

在示例DLL上尝试所有这些操作[22（head）< - > 2 < - > 77 < - > 6 < - > 43 < - > 76 < - > 89（tail）]。
尝试InsertHead(50) -附加步骤：22的PREV指针指向新的头50。
尝试InsertTail(10) -附加步骤：10的PREV指针指向旧的尾部89。
尝试Insert(3, 44) -附加步骤：6 / 44的PREV指针分别指向44/77。
尝试RemoveHead() -将新的头2的PREV指针设置为NULL。
尝试Remove(5) -将89的PREV指针设置为43。

7. 双端队列（Deque）

双端队列是一种抽象的数据结构，它是队列的拓展，它可以在队列的两端（头或尾）将元素加入或移除。

在我们的可视化中，双端队列基本上是受保护的双链表。我们仅能搜索头/尾的元素（读取头/尾），在头/尾插入新的元素（从头/尾推进），将现有头/尾元素移除（删除头/尾）。所有的操作复杂度为O(1)。

7-1. 出列的应用

双端队列一般用来比较高级的应用，例如在宽度优先搜素算法中找到0/1的加权图最短的路径，滑动窗口技术。

8. 总结

创建操作对于所有五种模式都是相同的。
然而，在五种模式之间的搜索/插入/移除操作存在细微差别。
对于堆栈，您只能从顶部/顶部查看/限制搜索，推/限制插入和弹出/限制删除。
对于队列，您只能从前面窥视/限制搜索，从后面推/限制插入，以及从前面弹出/限制删除。
对于双端队列，您可以从前/后，但不能从中间偷看/限制搜索，入队/限制插入，出队/限制删除。
单链表和双链表不具有这样的限制。

9. 更多

我们已经结束了这个电子讲座。
但是你可以提前阅读一些额外的挑战。

9-1. 潜在的讨论话题

以下是关于链表的更深入的讨论：

如果我们不存储尾部指针，会发生什么？
如果我们使用仿真头怎么办？
如果最后一个尾部项目指向头部项目呢？

9-2. 我们现在的答案

[This is a hidden slide]

9-3. C++ STL 和 Java API 的实现

C++ STL：forward_list （单链表），堆栈，队列（双链表），deque（实际上不使用双向链表，但另一种技术，看cppreference）

Java API：链表（已经是双链表）堆栈队列（实际上是一个接口，通常使用链表）双端队列（实际上是一个接口，通常使用LinkedList类）

9-4. Python和Ocaml标准库

Python：用list来实现链表/堆栈/队列/双向队列

OCaml：List Stack Queue （没有双向队列的原生支持）

9-5. 在线测试

有关这一数据结构的一些更有趣的问题，您可以在链表训练模块上练习。

9-6.
在线评判练习

我们也有一些编程问题，在某种程度上需要使用链表、堆栈、队列或双端队列等数据结构：UVA 11988 - 破键盘（又名北菊文本）, Kattis-退格, and Kattis-整数列表.

尝试这些问题能巩固和提高你对这些数据结构的理解。你也可以使用C++， STL或Java API来简化你的实现。

链表

1. Introduction

1-1. 5种模式

2. 动机

2-1. 列表抽象数据类型

2-2. 结果

2-3. 数组实现 - 第一部分

2-4. 数组实现 - 第二部分

2-5. 时间复杂性小结

2-6. 固定空间问题

2-7. 变量空间

2-8. 观察

3. 链表（LL）

3-1. 链表的顶点C++实现

3-2. 答案

3-3. 链表，其他数据元素

3-4. 变化

3-5. 获取（i）- 比数组慢很多

3-6. 搜索（v）-不优于数组

3-7. 插入 - 四种情况

3-8. 插入（i, v) - 在头节点插入（i=0)

3-9. 答案

3-10. 插入(i, v) - 插入v到一个空的链表

3-11. 插入（i, v) - 在[1, N-1] 种插入

3-12. 插入(i, v) -

3-13. 答案

3-14. 移除 - 三种情况

3-15. 移除（i）- 在头节点移除(i = 0)

3-16. 答案

3-17. 移除（i）- 在[1, N-2]种移除

3-18. Remove(i) - At Tail (i = N-1) - 第一部分

3-19. Remove(i) - At Tail (i = N-1) - 第二部分

3-20. 答案

3-21. 时间复杂度小结

3-22. 链表的应用

4. 堆栈

4-1. 设计选择

4-2. 结果

4-3. 栈的应用

4-4. 括号匹配问题

4-5. 时间复杂度为O(n)的解法（用 栈）

4-6. 计算后缀表达式

4-7. 时间复杂度为O(n)的解法（用 栈）

5. 队列

5-1. 数组实现问题 - 第一部分

5-2. 数组实现问题 - 第二部分

5-3. 数组实现问题 - 第三部分

5-4. 数组实现问题 - 第四部分

5-5. 这个时候就需要用到链表了

5-6. 队列的应用

6. 双向链表（DLL）

6-1. Remove(i) - At Tail (i = N-1), 重新访问

6-2. 固定常数额外的步骤

7. 双端队列（Deque）

7-1. 出列的应用

8. 总结

9. 更多

9-1. 潜在的讨论话题

9-2. 我们现在的答案

9-3. C++ STL 和 Java API 的实现

9-4. Python和Ocaml标准库

9-5. 在线测试

9-6. 在线评判练习

4-5. 时间复杂度为O(n)的解法（用栈）

4-7. 时间复杂度为O(n)的解法（用栈）

9-6.
在线评判练习