1x

Linked List is a data structure consisting of a group of vertices (nodes) which together represent a sequence. Under the simplest form, each vertex is composed of a data and a reference (link) to the next vertex in the sequence. Try clicking Search(77) for a sample animation on searching a value in a (Singly) Linked List.

Linked List (and its variations) can be used as the underlying data structure to implement List, Stack, Queue, and Deque ADTs (read this Wikipedia article about ADT if you are not familiar with that term). Another potential data structure that can be used to implement List ADT is (resize-able) array.

In this visualization, we discuss (Singly) Linked List (LL) — with a single next pointer — and its two variants: Stack and Queue, and also Doubly Linked List (DLL) — with both next and previous pointers — and its variant: Deque.

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.

🕑

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.

🕑

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] 向左移动一个位置以填补空白。

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.

🕑

Please review (Compact) Array data structure that can also be used to implement List ADT.

For fixed-size collections with known max limit of number of items that will ever be needed, i.e., the max size of M, then array is already a reasonably good data structure for List ADT implementation.

For variable-size collections with unknown size M and where dynamic operations such as insert/remove are common, a simple (fixed-size) array is actually a poor choice of data structure.

For such applications, there are better data structures, including Linked List. Read on...

🕑

🕑

🕑

`struct Vertex { // 我们可以使用C struct或C++/Python/Java 中的 class  int item; // 数据存储在这里，这个例子中是一个整数  Vertex* next; // 这个指针告诉我们下一个顶点在哪里};`

a0 其中的 item = 22 和它的 next = a1
a1 其中的 item = 2 和它的 next = a2
...
a6 其中的 item = 89 和它的 next = null

🕑

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

🕑

🕑

`Vertex* Get(int i) { // 返回顶点  Vertex* ptr = head; // 我们必须从头开始  for (int k = 0; k < i; ++k) // 向前推进 i 次    ptr = ptr->next; // 指针指向更高的索引  return ptr;}`

🕑

Search(77) - 在上面的的例子中找到位置/索引2（基于0的索引）。
Search(7) - 在上面的示例中检查完所有的N项之后，我们发现没有找到。因此在最坏情况下search(v)的时间复杂度O(n)。
🕑

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

`Vertex* vtx = new Vertex(); // 从项 v 创建新顶点 vtxvtx->item = v;vtx->next = head; // 将这个新顶点链接到（旧的）头顶点head = 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.

🕑

🕑

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

🕑

`Vertex* vtx = new Vertex(); // 这也是一个 C++ 代码vtx->item = v; // 从项目 v 创建新的顶点 vtxtail->next = vtx; // 只需链接这个，因为尾部是 i = (N-1)-th 项目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.

🕑

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

🕑

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

🕑

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;
pre->next = aft; // 忽略del
delete del;

🕑

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

🕑

Vertex* pre = Get(N-2); // 到尾部前的一个索引，O（n）
pre->next = null;
delete tail;
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.

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

🕑

🕑

🕑

🕑

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. 一些其他有趣的应用程序，出于教学目的没有显示。
🕑

🕑

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.

🕑

🕑

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.

🕑

🕑

🕑

🕑

🕑

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.

🕑

🕑

🕑

🕑

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

🕑

🕑

🕑

🕑

🕑

🕑

1. 如果我们不存储尾指针会发生什么？
2. 如果我们使用虚拟头部会怎样？
3. 如果最后一个尾部项指回头部项会怎样？
🕑

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）
🕑
Python：用list来实现链表/堆栈/队列/双向队列
OCaml：List Stack Queue （没有双向队列的原生支持）
🕑

🕑

UVa 11988 - Broken Keyboard (又名 Beiju Text)
Kattis - backspace，和
Kattis - integerlists

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.

🕑

>

N =

i = 0 (头部），v =

i = N (在尾部之后），v =

#### 关于

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

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

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

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

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

id, kr, vn, th.

#### 团队

Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

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

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

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

Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

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