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.
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.
- 获取（i）- 也许是一个微不足道的操作，返回ai的值（基于0的索引），
- 搜索（v ）-决定是否存在项/数据v（并报告其位置）或不存在（并且通常在列表中报告不存在的索引-1），
- 插入（i，v）-插入项目/数据v，在列表中的位置/索引 i，这个操作会有一个可能的问题在与他需要把索引i后面的所有数据都向后移动一位。
- 删除（i）- 删除列表中特定位置/索引i的项，这可能会让这个数据i后面的数据全部向前移动一位。
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.
当我们说密集数组（compact array) 时，我们指的是一个没有间隙的数组，即如果数组中有n个项（数组大小m，m>=n），那么只有索引[0…n-1 ]的空间被占用，其他索引[n.M.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]。这是为了保持紧凑。
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）。
如果M太大，那么闲置的空间就会被浪费掉。如果M太小，那么我们很容易耗尽空间。
C++ STL std::vector, Python list, Java Vector, 或者 Java ArrayList 实现所有可变大小的数组列表。
然而，经典的基于数组的空间浪费和复制/转移项目的浪费仍然是有问题的。
对于具有未知大小m的可变大小的集合，以及诸如插入/移除之类的动态操作是常见的，简单数组(array)会是一个糟糕的选择。
对于这样的应用，有更好的数据结构。让我们阅读…
struct Vertex { //我们可以使用C struct 或C++/python/java class
Vertex* next;//这个指针告诉我们下一个顶点在哪里
}；
使用以上示例的默认示例链接列表[22 (头)->2->77->6->43->76->89 (尾)] ，我们具有：a0，其项＝22，它的next＝a1，其项＝2，它的next＝a2，…a6，其项＝89，它的next＝null。
讨论：结构和类，哪一个更适合用C++实现链表？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.
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 a0 — 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 aN-1 — it is a6 = 89, nothing is after the tail item.
That's it, we only add three more extra variables in data structure.
我们在这个可视化中的版本（有尾部指针，不是循环的，没有虚设头项）可能与你在课堂上学习的不大相同，但是基本的想法应该不变。
在这个可视化中，每个顶点都有整数项，但是根据需要可以很容易地将其更改为任何其他数据类型。
因为我们只保留头和尾指针，所以需要一个遍历列表的子程序来寻找到除了头部（索引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）
- 在上面的的例子中找到位置/索引2（基于0的索引）。
- 在上面的示例中检查完所有的N项之后，我们发现没有找到。因此在最坏情况下search(v)的时间复杂度O(n)。
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].
讨论：如果我们使用简单数组实现来插入列表的头，会发生什么？
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.
尝试（insert(0, 50)），它在空链表 [] 上插入 (0, 50)。
Vertex* pre = Get(i-1);/ /遍历到第（i-1）个节点，O（n）
aft = pre.next//aft不能为null
也尝试一下，这一个极端情况：插入尾部的位置，把尾部指针移到右边的一个位置。由于需要遍历列表（例如，如果i接近n-1），这个操作很缓慢的，O（n）。
Vertex* vtx = new Vertex(); // C++
vtx->item = v; // 用 v 创建一个新的节点 vtx
tail->next = vtx; // 把尾部和 vtx 连起来
tail = vtx; // 现在更新尾部指针
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，它影响头指针。
- 链表的尾部，i＝N-1，它影响尾部指针
- 链表的其他位置，i＝ [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.
Vertex* pre = Get(i-1);/ /遍历到第（i-1）节点，O（n）
Vertex* del = pre->next, aft = del->next;
Vertex* pre = head;在（较短的）示例链接列表 [22 (head)->2->77->6 (tail)] 上重复尝试。它将一直工作下去直到链表的头项和尾项是同一项，并且我们切换到移除头部情况下。如果LL已经是空的我们不会执行，因为它是无效的。
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; // 更新尾部指针
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.
search（v）在最佳情况下，v在第一位置中找到, O(1)。在最坏的情况下，在列表中没有发现v，并且我们需要O（n）扫描来确定。
删除（i）在最佳情况下，删除i＝0，头指针帮助，O（1）。在最坏的情况下，在i＝n-1处删除，因为需要更新尾指针O（n）。
然而，允许顶点在内存中不连续的链表的基本概念，让堆栈 和 队列.的可以成为一个极好的可调整大小的数据结构。
在这个可视化中，单链表是自上而下，头部/尾部项目分别在顶部/底部。在该示例中，我们有 [2 (top/head)->7->5->3->1->9 (bottom/tail)].
讨论：我们可以使用向量，一个大小可变的数组，来实现一个效率更高的堆栈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.
- 括号匹配，
- 后缀计算器，
- 其他一些没有用作教学目的的有趣应用
括号匹配问题是检查给定输入中所有括号是否正确匹配的问题，如 (with) 、[with] 和 {with} 等。
括号匹配对于检查源代码的合法性同样有用。
讨论：我们可以使用堆栈的后进先出 (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.
例如，表达式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.
这是因为在紧凑数组后面的插入速度很快，O（1），但是由于需要移位项目，所以在紧凑数组前面的移除是慢的，请查看此幻灯片。
假设我们使用大小为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。
如果我们允许前索引和后索引在索引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。在这个时候，我们不能将任何其他东西插入队列中。
如果我们回顾这个幻灯片，我们看到在单链接列表中尾部中插入和在头部中移除的是非常快的，即O（1）。因此，我们将单链表的头/尾分别指定为队列的前/后。然后，因为链表中的项目没有连续存储在计算机内存中，所以链表的大小可以根据需要增加和缩小。
在我们的可视化中，队列基本上是一个受保护的单链表，在这里我们只能查看头部项目，将一个新的项目排队到在当前尾之后的一个位置，如 ，并从头部中删除现有的项目，如 （这也是出列操作）。所有的运算都是O（1）。
双链表的可以从后面向前移动，我们可以找到尾部指针前的一个项目通过tail->prev…因此，我们可以通过这种方式实现尾部的移除：
Vertex* temp = tail; / /记住尾部项目
tail = tail->prev; //实现O（1）性能的关键步骤
tail->next = null; //删除这个悬空引用
现在这个操作是O（1）。尝试示例DLL [22（head）< - > 2 < - > 77 < - > 6 < - > 43 < - > 76 < - > 89（tail）]。
尝试 -附加步骤：22的PREV指针指向新的头50。
尝试 -附加步骤：10的PREV指针指向旧的尾部89。
尝试 -附加步骤：6 / 44的PREV指针分别指向44/77。
尝试 -将新的头2的PREV指针设置为NULL。
尝试 -将89的PREV指针设置为43。
然而，在五种模式之间的搜索/插入/移除操作存在细微差别。
对于堆栈，您只能从顶部/顶部查看/限制搜索，推/限制插入和弹出/限制删除。
对于队列，您只能从前面窥视/限制搜索，从后面推/限制插入，以及从前面弹出/限制删除。
对于双端队列，您可以从前/后，但不能从中间偷看/限制搜索，入队/限制插入，出队/限制删除。
单链表和双链表不具有这样的限制。
但是你可以提前阅读一些额外的挑战。
- 如果我们不存储尾部指针，会发生什么？
- 如果我们使用仿真头怎么办？
- 如果最后一个尾部项目指向头部项目呢？
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）
- 我们也有一些编程问题，在某种程度上需要使用链表、堆栈、队列或双端队列等数据结构：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.
创建
搜索
插入
移除