链表（单向，双向），堆栈，队列，双端队列

链表是一种由一群结点组成顺序的数据结构。在最简单的情况下，每个结点由一个数据和一个指向在顺序中下一个结点的指针（即连接）而组成。点击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）的底层数据结构。

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

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

→

🕑

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

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

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

←

→

🕑

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

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

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

←

→

🕑

列表的顺序是非常重要的。其中位置顺序{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，我们要如何做？

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

←

→

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

←

→

🕑

让紧凑数组名称为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]。这是为了保持紧凑。

←

→

🕑

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）。

←

→

🕑

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

←

→

🕑

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

←

→

🕑

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

←

→

🕑

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

←

→

🕑

在其基本形式中，链表中的单个顶点（节点）具有这种结构：
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呢？

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

在这个链表数据结构中，我们也有一些额外的数据，我们记得在这个链表数据结构。我们使用上面的默认示例链表[22 (head)->2->77->6->43->76->89 (tail)]进行说明。

头指针指向a₀ , 它的项22，没有任何元素指向头项，
尾指针指向a_N-1，它的项a₆＝89，尾部之后没有任何东西。

我们只需要在数据结构中增加了两个额外的变量即可。

←

→

🕑

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

←

→

🕑

因为我们只保留头和尾指针，所以需要一个遍历列表的子程序来寻找到除了头部（索引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）

←

→

🕑

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

←

→

🕑

由于链表的特性，它比简单数组有更多的情况。
大多数第一次学习链表的CS学生通常不知道所有的情况，直到他们发现他们自己的链接列表代码失败时。在这个电子讲课中，我们直接阐述所有的案例。
对于插入（i，v），有四个（有效）可能性，即v项被添加到：

头节点（在当前第一个项目之前），i＝0，
空链表（与先前的情况类似）
当前链表的尾部，i＝n，
链表的其他位置，i＝〔1…n-1〕。

←

→

🕑

在头节点插入代码(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)。
讨论：如果我们使用简单数组实现来插入列表的头，会发生什么？

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

←

→

🕑

通过遍历链表 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）。

←

→

🕑

如果我们还记得尾部指针在这个电子讲座中的实现（这是可取的，因为它只是一个附加的指针变量），我们可以有效地在 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) 则超出尾部。

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

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

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

←

→

🕑

这种情况很简单：

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

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

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

delete temp; // 删除旧指针

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

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

通过遍历链表获取（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）是在尾部移除，要求我们更新尾部指针，见下一个案例。

←

→

🕑

我们可以实现链表尾部的移除，假设链表有超过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已经是空的我们不会执行，因为它是无效的。

←

→

🕑

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

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

pre->next = null;

delete tail;

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

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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）。

←

→

🕑

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

←

→

🕑

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

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

←

→

🕑

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

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

←

→

🕑

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

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

←

→

🕑

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

←

→

🕑

另一种可能的数组（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。

←

→

🕑

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

←

→

🕑

然而，这并不能解决数组实现的主要问题：数组的项以连续的方式存储在计算机内存中。
稍后再进行几个入列操作，我们可能有[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)。

←

→

🕑

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

←

→

🕑

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

←

→

🕑

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

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

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

←

→

🕑

在单链表中删除尾元素的主要问题是我们必须更新尾部指针，以便在删除后尾部指针能指向一个项目(即使我们可以通过尾指针直接访问尾项)。
双链表的可以从后面向前移动，我们可以找到尾部指针前的一个项目通过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）]。

←

→

🕑

由于每个顶点都有一个指针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。

←

→

🕑

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

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

←

→

🕑

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

←

→

🕑

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

←

→

🕑

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

←

→

🕑

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

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

←

→

🕑

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

←

→

🕑

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

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

←

→

🕑

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

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

←

→

🕑

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

←

→

🕑

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

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

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

←

🕑

创建

搜索

插入

移除

关于团队使用条款隐私政策

关于

VisuAlgo于2011年由Steven Halim博士创建，是一个允许学生以自己的速度自学基础知识，从而更好地学习数据结构与算法的工具。
VisuAlgo包含许多高级算法，这些算法在Steven Halim博士的书（“Competitive Programming”，与他的兄弟Felix Halim博士合作）和其他书中有讨论。今天，一些高级算法的可视化/动画只能在VisuAlgo中找到。
虽然本网站是专门为新加坡国立大学（NUS）学生学习各种数据结构和算法类（例如CS1010，CS2040，CS3230，CS3233，CS4234）而设，但我们作为在线学习的倡导者，我们非常希望世界各地的好奇的头脑能发现这些非常有用的算法可视化。
VisuAlgo不是从一开始就设计为在小触摸屏（例如智能手机）上工作良好，因为为了满足许多复杂算法可视化，需要大量的像素和点击并拖动手势进行交互。为得到良好的用户体验，最低屏幕分辨率应为1024x768，并且本网站只有首页相对适合移动设备。但是，我们正在测试一个准备在2022年4月发布的移动版本。
VisuAlgo是一个正在进行的项目，更复杂的可视化仍在开发中。
最令人兴奋的发展是自动问题生成器和验证器（在线测验系统），允许学生测试他们的基本数据结构和算法的知识。这些问题是通过一些随机生成的规则，学生的答案会在提交给我们的评分服务器后立即自动分级。这个在线测验系统，当它被更多的世界各地的CS教师采用，应该能从技术上消除许多大学的典型计算机科学考试手动基本数据结构和算法问题。通过在通过在线测验时设置小（但非零）的重量，CS教练可以（显着地）增加他/她的学生掌握这些基本问题，因为学生具有几乎无限数量的可以立即被验证的训练问题他们参加在线测验。培训模式目前包含12个可视化模块的问题。我们将很快添加剩余的12个可视化模块，以便VisuAlgo中的每个可视化模块都有在线测验组件。

VisuAlgo支持三种语言：英语，中文，印尼语。目前，我们还以各种语言写了有关VisuAlgo的公共注释：

id, kr, vn, th.

团队

项目领导和顾问（2011年7月至今）
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

最后一年项目/ UROP学生 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

最后一年项目/ UROP学生 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

最后一年项目/ UROP学生 5 (Aug 2021-Dec 2022)
Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

List of translators who have contributed ≥100 translations can be found at statistics page.

致谢
本项目运营资金是由NUS教学与学习发展中心（CDTL）的教学增进款慷慨提供的。

使用条款

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitter/Instagram/TikTok posts, course webpages, blog reviews, emails, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (https://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS.

List of Publications

This work has been presented briefly at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

This work is done mostly by my past students.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

隐私政策

Version 1.1 (Updated Fri, 14 Jan 2022).

Disclosure to all visitors: We currently use Google Analytics to get an overview understanding of our site visitors. We now give option for user to Accept or Reject this tracker.

Since Wed, 22 Dec 2021, only National University of Singapore (NUS) staffs/students and approved CS lecturers outside of NUS who have written a request to Steven can login to VisuAlgo, anyone else in the world will have to use VisuAlgo as an anonymous user that is not really trackable other than what are tracked by Google Analytics.

For NUS students enrolled in modules that uses VisuAlgo: By using a VisuAlgo account (a tuple of NUS official email address, NUS official student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your module lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the module smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the module unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Steven himself.

For other NUS students, you can self-register a VisuAlgo account by yourself (OPT-IN).

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will be tracked similarly as a normal NUS student account above but it will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.