>

>
1x
go to beginning previous frame pause play next frame go to end

链表是一种由一组顶点(节点)组成的数据结构,这些顶点共同表示一个序列。在最简单的形式下,每个顶点由一个数据和一个引用(链接)组成,该引用指向序列中的下一个顶点。尝试点击 Search(77) 查看在(单向)链表中搜索值的示例动画。


链表及其变体被用作实现列表,堆栈,队列和双端队列 ADTs 的底层数据结构(如果你不熟悉这个术语,可以阅读这篇关于 ADT 的维基百科文章)。


在这个可视化中,我们讨论(单向)链表(LL) - 带有一个下一个指针 - 及其两个变体:堆栈和队列,以及双向链表(DLL) - 带有下一个和前一个指针 - 及其变体:双端队列。


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章节后才可解锁):
  1. https://visualgo.net/zh/ll,
  2. https://visualgo.net/zh/stack,
  3. https://visualgo.net/zh/queue,
  4. https://visualgo.net/zh/dll,
  5. https://visualgo.net/zh/deque.

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.

🕑
计算机科学本科专业经常会教链表数据结构。原因如下:
  1. 它是一个简单的线性数据结构。
  2. 做为一个抽象数据类型,它有很广泛的应用。比如,学生名单,活动清单,约会清单等(尽管还有其他更高级的数据结构可以更好地完成相同的应用程序),也可以用来实现堆栈/队列/ 双端队列。
  3. 有些比较特殊的情况来说明为什么需要选择一个合适的数据结构去实现你的目的。
  4. 它具有各种定制的方式,因此通常在面向对象编程(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.

🕑

列表是一个项目/数据的序列,其中位置顺序很重要 {a0, a1, ..., aN-2, aN-1}。
常见的列表ADT操作包括:

  1. get(i) — 可能是一个微不足道的操作,返回 ai (0-based indexing),
  2. search(v) — 判断项目/数据 v 是否存在(并报告其位置/索引)
    或者不存在(通常报告一个不存在的索引 -1)在列表中,
  3. insert(i, v) — 在列表中的位置/索引 i 处插入项目/数据 v,可能会将前面的项目:[i..N-1] 向右移动一个位置以腾出空间,
  4. remove(i) — 移除列表中位置/索引 i 处的项目,可能会将前面的项目:[i+1..N-1] 向左移动一个位置以填补空白。

讨论1:如果我们想从列表中移除具有特定值 v 的项目怎么办?

讨论2:一个列表ADT可以包含重复的项目吗,即,ai = aj 其中 i ≠ j?


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]被列表的项目占据。


get(i),只需返回A[i]
如果数组紧凑,这个简单的操作将变得不必要地复杂。


search(v),我们逐一检查索引i ∈ [0..N-1],看看A[i] == v是否成立。
这是因为v(如果存在)可以在索引[0..N-1]的任何位置。
由于这个可视化只接受不同的项目,v最多只能找到一次。
在一般的List ADT中,我们可能希望search(v)返回一个索引列表。


insert(i, v),我们将项目 ∈ [i..N-1]移动到[i+1..N](从后向前)并设置A[i] = v
这样做是为了在索引i处正确插入v并保持紧凑性。


remove(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::vectorPython listJava VectorJava ArrayList都实现了这种可变大小的数组。请注意,Python的list和Java的ArrayList不是链表,而实际上是可变大小的数组。


然而,经典的基于数组的空间浪费和复制/移动项目开销仍然是问题。

🕑

对于已知最大项目数量上限的固定大小集合,即M的最大大小,数组已经是List ADT实现的一个相当好的数据结构。


对于大小未知的M和常见的动态操作如插入/删除的可变大小集合,简单的数组实际上是数据结构的一个糟糕选择。


对于这样的应用,有更好的数据结构。让我们继续阅读...

🕑

我们现在介绍链表数据结构。它使用指针/引用使项目/数据在内存中非连续(这是与简单数组的主要区别)。通过指针将项目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 (尾)] 进行说明,我们有:
a0 其中的 item = 22 和它的 next = a1
a1 其中的 item = 2 和它的 next = a2
...
a6 其中的 item = 89 和它的 next = null


讨论:对于C++实现的链表来说,struct还是class更好?Python或Java实现呢?

🕑

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.

🕑

我们还在这个链表数据结构中记住了一些额外的数据。我们使用默认示例链表 [22 (头)->2->77->6->43->76->89 (尾)] 进行说明。

  1. 指针指向 a0 — 它是 22,没有东西指向头部项,
  2. 链表中元素的当前数量 NN = 7 个元素。
  3. 指针指向 aN-1 — 它是 a6 = 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)。
🕑

由于链表的性质,比数组版本有更多的情况。


大多数第一次学习链表的计算机科学学生通常在他们的链表代码失败时才意识到所有的情况。


在这个电子讲座中,我们直接详细说明所有的情况。


对于insert(i, v),有四种可能性,即,项目v被添加到:

  1. 链表的头部(在当前第一项之前),i = 0
  2. 一个空的链表(幸运的是,这与前一种情况相似),
  3. 链表的最后一项(当前尾部)之后的位置,i = N
  4. 链表的其他位置,i = [1..N-1]
🕑

在头部插入的 (C++) 代码既简单又高效,时间复杂度为 O(1):

Vertex* vtx = new Vertex(); // 从项 v 创建新顶点 vtx
vtx->item = v;
vtx->next = head; // 将这个新顶点链接到(旧的)头顶点
head = vtx; // 新顶点成为新的头部

尝试 InsertHead(50),即 insert(0, 50),在示例链表 [22 (head)->2->77->6->43->76->89 (tail)] 上。


讨论:如果我们使用数组实现来在列表的头部插入,会发生什么?

🕑

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.

🕑

空的数据结构是一个常见的角落/特殊情况,如果没有适当的测试,往往会导致意外的崩溃。在当前为空的列表中插入新项是合法的,即在索引 i = 0 处。幸运的是,插入头部的同样的伪代码也适用于空列表,所以我们可以像在这个幻灯片中一样使用相同的代码(有一个小改动,我们还需要设置 tail = head)。


尝试 InsertHead(50),即 insert(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)。
🕑

如果我们也记住尾指针,就像在这个电子讲座中的实现一样(这是建议的,因为它只是一个额外的指针变量),我们可以在尾部项目之后(在i = N)有效地执行插入,时间复杂度为O(1):

Vertex* vtx = new Vertex(); // 这也是一个 C++ 代码
vtx->item = v; // 从项目 v 创建新的顶点 vtx
tail->next = vtx; // 只需链接这个,因为尾部是 i = (N-1)-th 项目
tail = vtx; // 现在更新尾指针

尝试 InsertTail(10),即 insert(7, 10),在示例链表 [22 (head)->2->77->6->43->76->89 (tail)] 上。一个常见的误解是说这是在尾部插入。在尾部元素插入是 insert(N-1, v)。在尾部之后插入是 insert(N, v)


讨论:如果我们使用数组实现对列表尾部之后的插入会发生什么?

🕑

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.

🕑

对于 remove(i),有三种(合法)可能性,即,索引 i 是:

  1. 链表的头部(当前的第一项),i = 0,它会影响头指针
  2. 链表的尾部,i = N-1,它会影响尾指针
  3. 链表的其他位置,i = [1..N-2]

讨论:将此幻灯片与插入情况幻灯片进行比较,以了解微妙的差异。从已经为空的链表中删除任何东西是否被认为是'合法'的?

🕑

这个案例很直接(用C++编写):

if (head == NULL) return; // 当 SLL 为空时避免崩溃
Vertex* tmp = head; // 这样我们可以稍后删除它
head = head->next; // 记账,更新头指针
delete tmp; // 这是旧的头部

尝试在链表 [22 (head)->2->77->6 (tail)] 上反复使用 RemoveHead()。它将一直正确工作,直到链表只包含一个项目,即头部 = 尾部项目。如果 LL 已经为空,我们将阻止执行,因为这是一个非法的情况。


讨论:如果我们使用数组实现来移除列表的头部会发生什么?

🕑

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.

🕑
通过遍历链表获取(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个项目(在C++中):

Vertex* pre = head;
tmp = head->next;
while (tmp->next != null) // 当邻居不是尾部时
pre = pre->next, tmp = tmp->next;
pre->next = null;
delete tmp; // tmp = (旧) 尾部
tail = pre; // 更新尾部指针

尝试在链表 [22 (头部)->2->77->6 (尾部)] 上反复使用 RemoveTail()。它将一直正确工作,直到链表只包含一个项目,头部 = 尾部项目,我们切换到头部移除的情况。如果链表已经为空,我们将阻止执行,因为这是一个非法的情况。

🕑
实际上,如果我们要保持链表的大小N不变(与这个幻灯片比较),我们可以遍历这个链表,Get(i)来实现链表尾部的这种移除(以下为C++代码):
Vertex* pre = Get(N-2); // 到尾部前的一个索引,O(n)
pre->next = null;
delete tail;
tail = pre; // 我们可以访问旧尾
请注意,这个操作是缓慢的,O(N),仅仅是因为需要将尾部指针从项目N-1从后往前更新一个单元到项目N-2,以便之后的未来插入能保持正确…这种不足将在双端链表 变体中得到解决。
讨论:如果我们使用简单数组实现来移除列表尾部会发生什么?
🕑

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.

🕑
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)数据结构,例如,下面的书堆。


栈示例
🕑

在大多数实现中,以及在这个可视化中,栈基本上是一个受保护的(单向)链表,我们只能查看头部项目,只能向头部推送新项目(在头部插入),例如,尝试 InsertHead(6),并且只能从头部弹出现有项目(从头部移除),例如,尝试 RemoveHead()。所有操作都是 O(1)。


在这个可视化中,我们将(单)链表从上到下定向,头/尾项目分别在顶部/底部。在示例中,我们有 [2 (顶部/头部)->7->5->3->1->9 (底部/尾部)]。由于垂直屏幕大小限制(在横向模式下),我们在这个可视化中只允许最多7个项目的栈。


讨论:我们能否使用向量,一个可调整大小的数组,来有效地实现栈ADT?

🕑

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.

🕑

栈有一些受欢迎的教科书应用程序。一些例子:

  1. 括号匹配,
  2. 后缀计算器,
  3. 一些其他有趣的应用程序,出于教学目的没有显示。
🕑

数学表达式可能会变得相当复杂,例如,{[x+2]^(2+5)-2}*(y+5)


括号匹配问题是检查给定输入中的所有括号是否正确匹配的问题,即,( 与 ),[ 与 ] 和 { 与 },等等。


括号匹配对于检查源代码的合法性同样有用。


讨论:事实证明,我们可以使用栈的LIFO行为来解决这个问题。
问题是如何做到这一点?

🕑

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.

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

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.

🕑
队列是另一种特殊的抽象数据结构或者组合,其中的元素遵守一定的顺序。其主要的(仅有的)操作为在表的后端进行插入操作,称之为入队(Enqueue),以及在表的前端进行删除操作,称之为出队(Dequeue)。
队列又称为先进先出(FIFO-first in first out) 的数据结构。这就意味着最先加入到队列的数据也会是最先出列的数据。
Queue Illustration
🕑
如果我们简单地使用紧凑数组实现这个队列ADT是a0是队列的前面,an-1是队列的后端,我们将遇到与dequeue(出列)操作相关的主要性能问题。
这是因为在紧凑数组后面的插入速度很快,O(1),但是由于需要移位项目,所以在紧凑数组前面的移除是慢的,请查看此幻灯片
🕑

另一种可能的数组实现方法是通过使用两个索引来避免在出队操作中的项目移动:front(队列最前面的项目的索引,在出队操作后增加)和back(队列最后面的项目的索引,在入队操作后也增加)。


假设我们使用一个大小为M = 8的数组,我们的队列内容如下:[(2,4,1,7),-,-,-,-],其中front = 0(下划线)back = 3(斜体)。当前活动的队列元素用(绿色)高亮显示。


如果我们调用 dequeue(),我们得到[-,(4,1,7),-,-,-,-]front = 0+1 = 1,和back = 3


如果我们调用 enqueue(5),我们得到[-,(4,1,7,5),-,-,-]front = 1,和back = 3+1 = 4

🕑

然而,经过许多出队和入队操作后,我们可能会有[-,-,-,-,-,6,2,3]front = 5,和back = 7。到现在为止,尽管数组前面有许多空位,但我们不能再入队任何其他元素。


如果我们允许frontback索引在达到索引M-1时“回绕”到索引0,我们实际上使数组“环形”,并且我们可以使用空位。


例如,如果我们接下来调用 enqueue(8),我们会有[8),-,-,-,-,(6,2,3]front = 5,和back = (7+1)%8 = 0

🕑

然而,这并没有解决固定大小数组实现的主要问题。再进行几次入队操作后,我们可能会得到[8,10,11,12,13),(6,2,3]front = 5,和 back = 4。在这一点上(front = (back+1) % M)),我们不能再入队任何其他东西。


请注意,如果我们知道我们的队列大小永远不会超过固定数组大小M,那么循环数组的想法实际上已经是实现队列ADT的好方法。


然而,如果我们不知道队列大小的上限,我们可以扩大(加倍)数组的大小,例如,使M = 2*8 = 16(两倍大),但这将需要重新复制索引frontback的项目,这是一个(但罕见)的O(N)过程,得到[(6,2,3,8,10,11,12,13),-,-,-,-,-,-,-,-,]front = 0,和 back = 7


PS1:如果你理解摊销分析,这个在循环数组满时的重大O(N)成本实际上可以分摊出来,使得每个入队在摊销意义上仍然是O(1)。


PS2:有一种使用两个栈来实现高效队列的替代方法。怎么做呢?

🕑

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.

🕑

如果我们真的不知道队列大小的上限,那么单链表(SLL)可以是实现队列ADT的一个好的数据结构。


回想一下,在队列中,我们只需要列表的两个极端端点,一个只用于插入(入队),一个只用于移除(出队)。


如果我们回顾这张幻灯片,我们会看到在单链表中在尾部插入从头部移除都很快,即,O(1)。因此,我们将单链表的头/尾指定为队列的前/后。然后,由于链表中的项目是在计算机内存中连续存储的,我们的链表可以根据需要进行增长和缩小。


在我们的可视化中,队列基本上是一个受保护的单链表,我们只能查看头部项目,将新项目入队到当前尾部之后的一个位置,例如,尝试 Enqueue(random-integer),并从头部出队现有项目,例如,尝试 RemoveHead()(这本质上是一个出队操作)。所有操作都是O(1)。

🕑
队列ADT通常用于模拟实际队列。
队列ADT的一个非常重要的应用是在 广度优先搜索图遍历算法中。
🕑
双向链表几乎和单向列表一样。唯一的不同是每一个节点都要两个指针。与单向列表相同的是他的继承点都指向下一个节点(如果存在)。但是每个节点有一个额外的指针指向前面的一个节点(如果存在)。
使用这个额外的指针能够让我们从链表的末尾开始向前迭代,但是这样会使用两倍的内存。但是他的好处是我们会很容易的搜索,插入或者 删除比较靠后的节点,其时间复杂度是O(1)。如果用单向列表做那么时间复杂度为O(n)。
在这个可视化的课件中,请注意双向链表的边(edge)是无向(其实也就是双向)边。
🕑

在单链表中,即使我们通过尾指针直接访问尾元素,删除尾元素的主要问题是,我们必须在此类删除后更新尾指针,使其指向尾部之前的一个元素。


有了双链表向移动的能力,我们可以通过tail->prev找到尾部之前的这个元素...因此,我们可以这样实现尾部的删除(在C++中):

Vertex* tmp = tail; // 记住尾部项
tail = tail->prev; // 实现 O(1) 性能的关键步骤 :O
tail->next = null; // 删除这个悬空的引用
delete tmp; // 删除旧的尾部

现在这个操作是 O(1)。尝试在示例 DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)] 上使用 RemoveTail()

🕑
由于每个顶点都有一个指针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的加权图最短的路径,滑动窗口技术。
🕑

创建操作对所有五种模式都是相同的。


然而,五种模式之间的搜索/插入/删除操作有些微小的差异。


对于栈,您只能从顶部/头部进行 peek/限制搜索,push/限制插入,和 pop/限制删除。


对于队列,您只能从前端(或有时是后端)进行 peek/限制搜索,从后端 push/限制插入,和从前端 pop/限制删除。


对于双端队列,您可以从前端/后端进行 peek/限制搜索,enqueue/限制插入,dequeue/限制删除,但不能从中间进行。


单向(单链)和双向链表没有这样的限制。

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

以下是关于链表的更高级的见解:

  1. 如果我们不存储尾指针会发生什么?
  2. 如果我们使用虚拟头部会怎样?
  3. 如果最后一个尾部项指回头部项会怎样?
  4. 需要做什么改变以允许重复项(更通用的列表ADT)?
🕑

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.

🕑
  • C++ STL:forward_list (单链表),堆栈 队列 (双链表),deque(实际上不使用双向链表,但另一种技术,看cppreference)
Java API:链表(已经是双链表)堆栈 队列(实际上是一个接口,通常使用链表)双端队列(实际上是一个接口,通常使用LinkedList类)
🕑
Python:用list来实现链表/堆栈/队列/双向队列
OCaml:List Stack Queue (没有双向队列的原生支持)
🕑

关于这个数据结构的一些更有趣的问题,请在链表培训模块上练习。

🕑

我们还有一些编程问题,这些问题在一定程度上需要使用链表,栈,队列或双端队列这些数据结构:
UVa 11988 - Broken Keyboard (又名 Beiju Text)
Kattis - backspace,和
Kattis - integerlists


尝试它们以巩固和提高你对这种数据结构的理解。如果这可以简化你的实现,你可以使用 C++ STL,Python 标准库,或 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.

🕑

新建(A)

插入

移除

>

清空

用户自定义列表

N =

随机

随机排序

i = 0 (头部),v =

i = N (在尾部之后),v = 

在i(1…n-1)和v=中同时指定i

移除 i = 0 头部

移除  i = N-1 尾部

在[ 1…N-2 ]中指定i

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

关于

VisuAlgo最初由副教授Steven Halim于2011年构思,旨在通过提供自学、互动式学习平台,帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年,VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

虽然VisuAlgo主要面向新加坡国立大学(NUS)的学生,包括各种数据结构和算法课程(例如CS1010/等价课程,CS2040/等价课程(包括IT5003),CS3230,CS3233和CS4234),但它也是全球好奇心的宝贵资源,促进在线学习。

最初,VisuAlgo并不适用于智能手机等小触摸屏,因为复杂的算法可视化需要大量的像素空间和点击拖动交互。为了获得最佳用户体验,建议使用最低分辨率为1366x768的屏幕。然而,自2022年4月以来,VisuAlgo的移动(精简)版本已经推出,使得在智能手机屏幕上使用VisuAlgo的部分功能成为可能。

VisuAlgo仍然在不断发展中,正在开发更复杂的可视化。目前,该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器,其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成,并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统,它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重,计算机科学教师可以显著提高学生对这些基本概念的掌握程度,因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言:英语、中文和印尼语。此外,我们还用各种语言撰写了关于VisuAlgo的公开笔记,包括印尼语、韩语、越南语和泰语:

id, kr, vn, th.

团队

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

本科生研究人员 1
CDTL TEG 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
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2
CDTL TEG 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学生 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

本科生研究人员 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

最后一年项目/ UROP学生 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

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

致谢
NUS教学与学习发展中心(CDTL)授予拨款以启动这个项目。在2023/24学年,Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

使用条款

VisuAlgo慷慨地向全球计算机科学界提供免费服务。如果您喜欢VisuAlgo,我们恳请您向其他计算机科学学生和教师宣传它的存在。您可以通过社交媒体平台(如Facebook、YouTube、Instagram、TikTok、Twitter等)、课程网页、博客评论、电子邮件等方式分享VisuAlgo。

数据结构与算法(DSA)的学生和教师可以直接在课堂上使用本网站。如果您从本网站截取屏幕截图或视频,可以在其他地方使用,但请引用本网站的URL(https://visualgo.net)和/或下面的出版物列表作为参考。但请不要下载VisuAlgo的客户端文件并将其托管在您的网站上,因为这构成了抄袭行为。目前,我们不允许他人分叉此项目或创建VisuAlgo的变体。个人使用离线副本的客户端VisuAlgo是可以接受的。

请注意,VisuAlgo的在线测验组件具有重要的服务器端元素,保存服务器端脚本和数据库并不容易。目前,普通公众只能通过“培训模式”访问在线测验系统。“测试模式”提供了一个更受控制的环境,用于在新加坡国立大学的真实考试中使用随机生成的问题和自动验证。


出版物列表

这项工作曾在2012年国际大学生程序设计竞赛(波兰,华沙)的CLI研讨会上和2012年国际信息学奥林匹克竞赛(意大利,锡尔米奥内-蒙蒂基亚里)的IOI会议上展示过。您可以点击此链接阅读我们2012年关于该系统的论文(当时还没有称为VisuAlgo),以及此链接阅读2015年的简短更新(将VisuAlgo与之前的项目关联起来)。


错误报告或新功能请求

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误,或者您想要请求新功能,请联系Steven Halim副教授。他的联系方式是将他的名字连接起来,然后加上gmail dot com。

隐私政策

版本 1.2 (更新于2023年8月18日星期五)。

自2023年8月18日(星期五)起,我们不再使用 Google Analytics。因此,我们现在使用的所有 cookies 仅用于此网站的运营。即使是首次访问的用户,烦人的 cookie 同意弹窗现在也已关闭。

自2023年6月7日(星期五)起,由于 Optiver 的慷慨捐赠,全世界的任何人都可以自行创建一个 VisuAlgo 账户,以存储一些自定义设置(例如,布局模式,默认语言,播放速度等)。

此外,对于 NUS 学生,通过使用 VisuAlgo 账户(一个 NUS 官方电子邮件地址,课堂名册中的学生姓名,以及在服务器端加密的密码 - 不存储其他个人数据),您同意您的课程讲师跟踪您的电子讲义阅读和在线测验培训进度,这是顺利进行课程所必需的。您的 VisuAlgo 账户也将用于参加 NUS 官方的 VisuAlgo 在线测验,因此,将您的账户凭据传递给他人代您进行在线测验构成学术违规。课程结束后,您的用户账户将被清除,除非您选择保留您的账户(OPT-IN)。访问完整的 VisuAlgo 数据库(包含加密密码)的权限仅限于 Halim 教授本人。

对于全球其他已经给 Steven 写过信的 CS 讲师,需要一个 VisuAlgo 账户(您的(非 NUS)电子邮件地址,您可以使用任何显示名称,以及加密密码)来区分您的在线凭据与世界其他地方。您的账户将具有 CS 讲师特定的功能,即能够查看隐藏的幻灯片,这些幻灯片包含了在隐藏幻灯片之前的幻灯片中提出的问题的(有趣的)答案。您还可以访问 VisuAlgo 在线测验的 Hard 设置。您可以自由地使用这些材料来增强您的数据结构和算法课程。请注意,未来可能会有其他 CS 讲师特定的功能。

对于任何拥有 VisuAlgo 账户的人,如果您希望不再与 VisuAlgo 工具有关联,您可以自行删除您的账户。