7    VisuAlgo.net / /list Login LL 队列 DLL 双端队列
示例模式 ▿

>

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

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 are used as 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).


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.


Click 'Next' (on the top right)/press 'Page Down' to advance this e-Lecture slide, use the drop down list/press 'Space' to jump to a specific slide, or Click 'X' (on the bottom right)/press 'Esc' to go to Exploration mode.


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

X Esc
下一个 PgDn
这里我们将把五种不同的数据结构包括链表(Linked List), 栈(Stack),队列(Queue), 双向链表(Double LinkedList),双端队列(Double Ended Queue)全部放在链表的环节下。为了多样性,我们随机加载不同的模式:HTTPS://VisualGo.NET/En/List. 但是,您可以直接使用以下URL快捷方式访问单个模式:
  1. https://visualgo.net/en/ll,
  2. https://visualgo.net/en/stack,
  3. https://visualgo.net/en/queue,
  4. https://visualgo.net/en/dll,
  5. https://visualgo.net/en/deque.

Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

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

Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). 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.

X Esc
上一个 PgUp
下一个 PgDn
列表的顺序是非常重要的。其中位置顺序{a0, a1, ..., aN-2, aN-1 }。常见列表ADT操作为:
  1. 获取(i)- 也许是一个微不足道的操作,返回ai的值(基于0的索引),
  2. 搜索(v )-决定是否存在项/数据v(并报告其位置)或不存在(并且通常在列表中报告不存在的索引-1),
  3. 插入(i,v)-插入项目/数据v,在列表中的位置/索引 i,这个操作会有一个可能的问题在与他需要把索引i后面的所有数据都向后移动一位。
  4. 删除(i)- 删除列表中特定位置/索引i的项,这可能会让这个数据i后面的数据全部向前移动一位。
讨论:如果我们想要在列表中移除一个具体的值v,我们要如何做?
X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn
(紧凑)数组是实现列表ADT(抽象数据类型)的一个很好的候选对象,因为它是处理项目集合的简单结构。
当我们说密集阵列(compact array) 时,我们指的是一个没有间隙的数组,即如果数组中有n个项(大小m,其中m>=n),那么只有索引[0…n-1 ]的空间被占用,其他索引[n.M.1]应该保持空。
X Esc
上一个 PgUp
下一个 PgDn
让紧凑数组名称为A,它的索引是[0..N-1] 的。
  1. 获取(i),返回A[i]。如果数组不紧凑,这个简单的操作将会不必要地复杂化。
  2. 搜索(v),我们逐一检查每个索引i [0…n-1 ],看看是否A[i]==v。这是因为v(如果存在)可以在索引[0…n-1 ]中的任何地方。
  3. 插入(i,v),我们将项[i,N-1 ]移到[i+1...N](从最后面往后移动),并设置一个A[i]=v。这使得v在索引i中被正确插入并依旧保持紧凑性。
  4. 删除(i),我们将项 ∈ [i+1…N-1 ]移到[i, N-2],重写旧A[i]。这是为了保持紧凑。
X Esc
上一个 PgUp
下一个 PgDn
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)。
X Esc
上一个 PgUp
下一个 PgDn
密集阵列(compact array)的大小是M且不是无限的,而是有限的数。这带来了一个问题,因为在许多应用中,你可能事先不知道数组的大小。
如果M太大,那么闲置的空间就会被浪费掉。如果M太小,那么我们很容易耗尽空间。
X Esc
上一个 PgUp
下一个 PgDn
解决方案:使M成为变量。因此,当数组满时,我们创建一个更大的数组(通常是两倍大),并将元素从旧数组移动到新数组。因此,除了(通常很大的)物理计算机存储器大小之外,没有更多的限制。
C++ STL std::vectorJava Vector, 或者 Java ArrayList 实现所有可变大小的数组列表。
然而,经典的基于数组的空间浪费和复制/转移项目的浪费仍然是有问题的。
X Esc
上一个 PgUp
下一个 PgDn
对于固定大小的集合,即我们知道它有多少个元素,或者它最多有多少个元素,比如Max是M个元素,那么简单数组(array)可以被考虑去实现你的需要。
对于具有未知大小m的可变大小的集合,以及诸如插入/移除之类的动态操作是常见的,简单数组(array)会是一个糟糕的选择。
对于这样的应用,有更好的数据结构。让我们阅读…

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

In its basic form, a single vertex (node) in the Linked List has this rough structure:

struct Vertex { // we can use either C struct or C++/Java class
int item; // the data is stored here, an integer in this example
Vertex* next; // this pointer tells us where is the next vertex
};

Using the default example Linked List [22 (head)->2->77->6->43->76->89 (tail)] for illustration, we have:
a0 with its item = 22 and its next = a1,
a1 with its item = 2 and its next = a2,
...
a6 with its item = 89 and its next = null.


Discussion: Which one is better for a C++ implementation of Linked List? struct or class? How about Java implementation?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

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.

  1. The head pointer points to a0 — it is 22, nothing points to the head item,
  2. The tail pointer points to aN-1 — it is a6 = 89, nothing is after the tail item.

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

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

Since we only keep the head and tail pointers, list traversal subroutine is needed to reach positions other than the head (index 0) and the tail (index N-1).


As this sub-routine is so frequently used, we will abstract it out as a function. The code below is written in C++.

Vertex* Get(int i) { // returns the vertex
Vertex* ptr = head; // we have to start from head
for (int k = 0; k < i; k++) // advance forward i time(s)
ptr = ptr->next; // the pointers are pointing to the higher index
return ptr;
}

It runs in O(N) as i can be as big as index N-2.
Compare this with array where we can access index i in O(1) time.

X Esc
上一个 PgUp
下一个 PgDn

As we only have direct reference to the first head item and the last tail item, plus the pointers are pointing to the right (higher position/index), we can only access the rest by starting from the head item and hopping through the next pointers. On the default [22 (head)->2->77->6->43->76->89 (tail)], we have:


Search(77) — found in the example above at position/index 2 (0-based indexing).


Search(7) — not found in the example above, and this is only known after all N items are examined, so Search(v) has O(N) worst case time complexity.

X Esc
上一个 PgUp
下一个 PgDn
由于链表的特性,它比简单数组有更多的情况。
大多数第一次学习链表的CS学生通常不知道所有的情况,直到他们发现他们自己的链接列表代码失败时。在这个电子讲课中,我们直接阐述所有的案例。
对于插入(i,v),有四个(有效)可能性,即v项被添加到:
  1. 头节点(在当前第一个项目之前),i=0,
  2. 空链表(与先前的情况类似)
  3. 当前链表的尾部,i=n,
  4. 链表的其他位置,i=〔1…n-1〕。
X Esc
上一个 PgUp
下一个 PgDn

The (C++) code for insertion at head is simple and efficient, in O(1):

Vertex* vtx = new Vertex(); // create new vertex vtx from item v
vtx->item = v;
vtx->next = head; // link this new vertex to the (old) head vertex
head = vtx; // the new vertex becomes the new head

Try InsertHead(50), which is insert(0, 50), on the example Linked List [22 (head)->2->77->6->43->76->89 (tail)].


Discussion: What happen if we use array implementation for insertion at head of the list?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

Empty data structure is a common corner/special case that can often cause unexpected crash if not properly tested. It is legal to insert a new item into a currently empty list, i.e. at index i = 0. Fortunately, the same pseudo-code for insertion at head also works for an empty list so we can just use the same code as in this slide (with one minor change, we also need to set tail = head).


Try InsertHead(50), which is insert(0, 50), but on the empty Linked List [].

X Esc
上一个 PgUp
下一个 PgDn

With the Linked List traversal Get(i) sub-routine, we can now implement insertion in the middle of the Linked List as follows (in C++):

Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
aft = pre.next // aft cannot be null, think about it
Vertex vtx = new Vertex(); // create new vertex
vtx->item = v;
vtx->next = aft; // link this
pre->next = vtx; // and this

Try Insert(3, 44) on the example Linked List  [22 (head)->2->77->6->43->76->89 (tail)].


Also try Insert(6, 55) on the same example Linked List. This is a corner case: Insert at the position of tail item, shifting the tail to one position to its right.


This operation is slow, O(N), due to the need for traversing the list (e.g. if i close to N-1).

X Esc
上一个 PgUp
下一个 PgDn

If we also remember the tail pointer as with the implementation in this e-Lecture (which is advisable as it is just one additional pointer variable), we can perform insertion beyond the tail item (at i = N) efficiently, in O(1):

Vertex* vtx = new Vertex(); // this is also a C++ code
vtx->item = v; // create new vertex vtx from item v
tail->next = vtx; // just link this, as tail is the i = (N-1)-th item
tail = vtx; // now update the tail pointer

Try InsertTail(10), which is insert(7, 10), on the example Linked List [22 (head)->2->77->6->43->76->89 (tail)] . A common misconception is to say that this is insertion at tail. Insertion at tail element is insert(N-1, v). This insertion beyond the tail is insert(N, v).


Discussion: What happen if we use array implementation for insertion beyond the tail of the list?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn
对于remove(i),有三种可能性:
  1. 链表的头(当前第一项),i=0,它影响头指针。
  2. 链表的尾部,i=n-1,它影响尾部指针
  3. 链表的其他位置,i=〔1…N-2〕。
讨论:将该幻灯片与插入幻灯片进行比较,以实现细微差别。从一个空链接列表中删除任何东西是有效的操作吗?
X Esc
上一个 PgUp
下一个 PgDn

This case is straightforward (written in C++):

if (head == NULL) return; // avoid crashing when SLL is empty
Vertex* temp = head; // so we can delete it later
head = head->next; // book keeping, update the head pointer
delete temp; // which is the old head

Try RemoveHead() repeatedly on the (shorter) example Linked List [22 (head)->2->77->6 (tail)]. It will continuously working correctly up until the Linked List contains one item where the head = the tail item. We prevent execution if the LL is already empty as it is an illegal case.


Discussion: What happen if we use array implementation for removal of head of the list?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

With the Linked List traversal Get(i) sub-routine (discussed earlier), we can now implement removal of the middle item of the Linked List as follows (in C++):

Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
Vertex* del = pre->next, aft = del->next;
pre->next = aft; // bypass del
delete del;

Try Remove(5), the element at index N-2 (as N = 7 in the example [22 (head)->2->77->6->43->76->89 (tail)] .
This is the worst O(N) case on the example above.


Note that Remove(N-1) is removal at tail that requires us to update the tail pointer, see the next case.

X Esc
上一个 PgUp
下一个 PgDn

We can implement the removal of the tail of the Linked List as follows, assuming that the Linked List has more than 1 item (in C++):

Vertex* pre = head;
temp = head->next;
while (temp->next != null) // while my neighbor is not the tail
pre = pre->next, temp = temp->next;
pre->next = null; // alternatively: pre = Get(N-2), temp = Get(N-1)
delete temp; // temp = (old) tail
tail = pre; // update tail pointer

Try RemoveTail() repeatedly on the (shorter) example Linked List [22 (head)->2->77->6 (tail)]. It will continuously working correctly up until the Linked List contains one item where the head = the tail item and we switch to removal at head case. We prevent execution if the LL is already empty as it is an illegal case.

X Esc
上一个 PgUp
下一个 PgDn

Actually, if we also maintain the size of the Linked List N (compare with this slide), we can use the Linked List traversal sub-routine Get(i) to implement the removal of the tail of the Linked List this way (in C++):

Vertex* pre = Get(N-2); // go to one index just before tail, O(N)
pre->next = null;
delete tail;
tail = pre; // we have access to old tail

Notice that this operation is slow, O(N), just because of the need to update the tail pointer from item N-1 backwards by one unit to item N-2 so that future insertion after tail remains correct... This deficiency will be later addressed in Doubly Linked List variant.


Discussion: What happen if we use array implementation for removal of tail of the list?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn
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)。
X Esc
上一个 PgUp
下一个 PgDn
链表 紧凑数组进行比较,纯(单列)链表应用程序是罕见的,因为更简单的可缩放紧凑数组(vector)可以更好地完成工作。
然而,允许顶点在内存中不连续的链表的基本概念,让堆栈 和 队列.的可以成为一个极好的可调整大小的数据结构。
X Esc
上一个 PgUp
下一个 PgDn
堆栈是一种特殊的抽象数据结构或者组合,其主要的(仅有的)操作为将元素加入栈中,称为进栈和将元素移除,称为出栈。堆栈是一种后进先出(LIFO-Last-In-First-Out) 的数据结构。

在我们的可视化中,堆栈基本上是一个受保护的单向链表,我们仅能查找栈头的元素(peek),在栈头插入新的元素(入栈)和将现有的元素从栈头移除(出栈)。

所有操作的时间复杂度为O(1)。
X Esc
上一个 PgUp
下一个 PgDn

In most implementations and also in this visualization, Stack is basically a protected (Singly) Linked List where we can only peek at the head item, push a new item only to the head (insert at head), e.g. try InsertHead(6), and pop existing item only from the head (remove from head), e.g. try RemoveHead(). All operations are O(1).


In this visualization, we orientate the (Single) Linked List top down, with the head/tail item at the top/bottom, respectively. In the example, we have [2 (top/head)->7->5->3->1->9 (bottom/tail)].


Discussion: Can we use vector, a resizeable array, to implement Stack ADT efficiently?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn
Stack(堆栈)在教科书中有一些非常经典的应用,例如:
  1. 一些其他有趣的应用程序但没有用于教学目的。
  2. 括号匹配,
  3. 后缀计算器,
X Esc
上一个 PgUp
下一个 PgDn
数学表达式可以变得相当复杂,例如 {[x+2]^(2+5)-2}*(y+5).
括号匹配问题是检查给定输入中所有括号是否正确匹配的问题,即(with)、[with ]和{with}等。
括号匹配对于检查源代码的合法性同样有用。
讨论:我们可以使用堆栈的LIFO行为来解决这个问题。那么如何解决呢?
X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

Postfix expression is a mathematical expression in: operand1 operand2 operator format which is different from what human is most comfortable at, the Infix expression: operand1 operator operand2.


For example, expression 2 3 + 4 * is the Postfix version of (2+3)*4.


In Postfix expression, we do not need brackets.


Discussion: It turns out that we can also use Stack to solve this problem efficiently.
The question is how?

X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

Queue is another Abstract Data Type in which the items in the collection are kept in order and the main operations on the collection are the addition of items to the back position (enqueue) and removal of items from the front position (dequeue).


It is known as First-In-First-Out (FIFO) data structure as the first item to be enqueued will eventually be the first item to be dequeued, as in real life queues (see below).


Queue Illustration
X Esc
上一个 PgUp
下一个 PgDn
如果我们简单地使用紧凑数组实现这个队列ADT是a0是队列的前面,an-1是队列的后端,我们将遇到与dequeue(出列)操作相关的主要性能问题。
这是因为在紧凑数组后面的插入速度很快,O(1),但是由于需要移位项目,所以在紧凑数组前面的移除是慢的,请查看此幻灯片
X Esc
上一个 PgUp
下一个 PgDn
另一种可能的数组(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。
X Esc
上一个 PgUp
下一个 PgDn
然而,许多出列和如列操作,我们可能有[-,-,-,-,-,6,2,3]front = 5, and back = 7。到目前为止,我们不能插队任何东西,尽管我们在数组的前面有很多空的空间。
如果我们允许前索引和后索引在索引M-1到达索引0时“回滚”到索引,则有效地使数组“循环”,并且我们可以使用空的空间。
例如,如果我们调用 enqueue(8),我们有[8,-,-,-,-,6,2,3],前面=5,后面=(7+1)% 8=0。
X Esc
上一个 PgUp
下一个 PgDn
然而,这并不能解决数组实现的主要问题:数组的项以连续的方式存储在计算机内存中。
稍后再进行几个入列操作,我们可能有[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。
X Esc
上一个 PgUp
下一个 PgDn
回想一下,在队列中,我们只需要列表的两个极端,一个只用于插入(入队),一个用于删除(出列)。
如果我们回顾这个幻灯片,我们看到在单链接列表中尾部中插入和在头部中移除的是快非常快的,即O(1)。因此,我们将单链表的头/尾分别指定为队列的前/后。然后,因为链表中的项目没有连续存储在计算机内存中,所以我们的链表的大小可以根据需要增加和缩小。
在我们的可视化中,队列基本上是一个受保护的单链表,在这里我们只能查看头部项目,将一个新的项目排队到在当前尾之后的一个位置,例如尝试Enqueue(random-integer),并从头部中删除现有的项目,例如,尝试RemoveHead()(这也是出列操作)。所有的运算都是O(1)。
X Esc
上一个 PgUp
下一个 PgDn
队列ADT通常用于模拟实际队列。
队列ADT的一个非常重要的应用是在 广度优先搜索图遍历算法中。
X Esc
上一个 PgUp
下一个 PgDn

Doubly Linked List (DLL) is 99% the same as its Singly Linked List version. The main difference is that now each vertex contains two pointers. The next pointer is the same as in Singly Linked List version in which it links item ai with the next item ai+1, if exists. The additional prev pointer also links item ai with the previous item ai-1, if exists.


The usage of prev pointers makes it possible to move/iterate backwards at the expense of two-times memory usage requirement as now each vertex records one additional pointer. The positive side effect of this ability to move backwards is now we can address the weak removal at tail case of the Singly Linked List.


In this visualization, notice that the edges in Doubly Linked List (and later Deque) are undirected (bidirectional) edges.

X Esc
上一个 PgUp
下一个 PgDn

The main problem of removal of the tail element in the Singly Linked List, even if we have direct access to the tail item via the tail pointer, is that we then have to update the tail pointer to point to one item just before the tail after such removal.


With Doubly Linked List ability to move backwards, we can find this item before the tail via tail->prev... Thus, we can implement removal of tail this way (in C++):

Vertex* temp = tail; // remember tail item
tail = tail->prev; // the key step to achieve O(1) performance :O
tail->next = null; // remove this dangling reference
delete temp; // remove the old tail

Now this operation is O(1). Try RemoveTail() on example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)].

X Esc
上一个 PgUp
下一个 PgDn

As we have one more pointer prev for each vertex, their values need to be updated too during each insertion or removal. Try all these operations on example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)].


Try InsertHead(50) — additional step: 22's prev pointer points to new head 50.


Try InsertTail(10) — additional step: 10's prev pointer points to old tail 89.


Try Insert(3, 44) — additional step: 6's/44's prev pointers point to 44/77, respectively.


Try RemoveHead() — set new head 2's prev pointer to null.


Try Remove(5) — set 89's prev pointer to 43.

X Esc
上一个 PgUp
下一个 PgDn
双端队列是一种抽象的数据结构,它是队列的拓展,它可以在队列的两端(头或尾)将元素加入或移除。
在我们的可视化中,双端队列基本上是受保护的双链表。我们仅能搜索头/尾的元素(读取头/尾),在头/尾插入新的元素(从头/尾推进),将现有头/尾元素移除(删除头/尾)。所有的操作复杂度为O(1)。
X Esc
上一个 PgUp
下一个 PgDn
双端队列一般用来比较高级的应用,例如在宽度优先搜素算法中找到0/1的加权图最短的路径,滑动窗口技术。
X Esc
上一个 PgUp
下一个 PgDn
创建操作对于所有五种模式都是相同的。
然而,在五种模式之间的搜索/插入/移除操作存在细微差别。
对于堆栈,您只能从顶部/顶部查看/限制搜索,推/限制插入和弹出/限制删除。
对于队列,您只能从前面窥视/限制搜索,从后面推/限制插入,以及从前面弹出/限制删除。
对于双端队列,您可以从前/后,但不能从中间偷看/限制搜索,入队/限制插入,出队/限制删除。
单链表和双链表不具有这样的限制。
X Esc
上一个 PgUp
下一个 PgDn
我们已经结束了这个电子讲座。
但是你可以提前阅读一些额外的挑战。
X Esc
上一个 PgUp
下一个 PgDn
以下是关于链表的更深入的讨论:
  1. 如果我们不存储尾部指针,会发生什么?
  2. 如果我们使用仿真头怎么办?
  3. 如果最后一个尾部项目指向头部项目呢?
X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn
Java API:链表(已经是双链表)堆栈 队列(实际上是一个接口,通常使用链表)双端队列(实际上是一个接口,通常使用LinkedList类)
X Esc
上一个 PgUp
下一个 PgDn

For a few more interesting questions about this data structure, please practice on Linked List training module (no login is required).


However, for registered users, you should login and then go to the Main Training Page to officially clear this module and such achievement will be recorded in your user account.

X Esc
上一个 PgUp
下一个 PgDn

尝试巩固和提高你对数据结构的理解。如果可以简化你的算法,你可以使用C++, STL或Java API。
X Esc
上一个 PgUp
下一个 PgDn
当操作进行时,状态面板将会有每个步骤的描述。
X Esc
上一个 PgUp
下一个 PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
上一个 PgUp
下一个 PgDn

Control the animation with the player controls! Keyboard shortcuts are:

Spacebar: play/pause/replay
Left/right arrows: step backward/step forward
-/+: decrease/increase speed
X Esc
上一个 PgUp
下一个 PgDn

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.

X Esc
上一个 PgUp

创建

插入(i,v)

移除(i)

>

清空

随机

随机排序

随机固定大小

执行

--- 用户自定义列表 ---

执行

i = 0 (Head), specify v =

执行

i = N (After Tail), specify v =

执行

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

执行

移除 i = 0 头部

移除  i = N-1 尾部

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

执行

关于 团队 使用条款

关于

VisuAlgo在2011年由Steven Halim博士概念化,作为一个工具,帮助他的学生更好地理解数据结构和算法,让他们自己和自己的步伐学习基础。
VisuAlgo包含许多高级算法,这些算法在Steven Halim博士的书(“竞争规划”,与他的兄弟Felix Halim博士合作)和其他书中讨论。今天,一些高级算法的可视化/动画只能在VisuAlgo中找到。
虽然专门为新加坡国立大学(NUS)学生采取各种数据结构和算法类(例如CS1010,CS1020,CS2010,CS2020,CS3230和CS3230),作为在线学习的倡导者,我们希望世界各地的好奇心发现这些可视化也很有用。
VisuAlgo不是从一开始就设计为在小触摸屏(例如智能手机)上工作良好,因为需要满足许多复杂的算法可视化,需要大量的像素和点击并拖动手势进行交互。一个令人尊敬的用户体验的最低屏幕分辨率为1024x768,并且只有着陆页相对适合移动设备。
VisuAlgo是一个正在进行的项目,更复杂的可视化仍在开发中。
最令人兴奋的发展是自动问题生成器和验证器(在线测验系统),允许学生测试他们的基本数据结构和算法的知识。这些问题是通过一些规则随机生成的,学生的答案会在提交给我们的评分服务器后立即自动分级。这个在线测验系统,当它被更多的世界各地的CS教师采用,应该技术上消除许多大学的典型计算机科学考试手动基本数据结构和算法问题。通过在通过在线测验时设置小(但非零)的重量,CS教练可以(显着地)增加他/她的学生掌握这些基本问题,因为学生具有几乎无限数量的可以立即被验证的训练问题他们参加在线测验。培训模式目前包含12个可视化模块的问题。我们将很快添加剩余的8个可视化模块,以便VisuAlgo中的每个可视化模块都有在线测验组件。
另一个积极的发展分支是VisuAlgo的国际化子项目。我们要为VisuAlgo系统中出现的所有英语文本准备一个CS术语的数据库。这是一个很大的任务,需要众包。一旦系统准备就绪,我们将邀请VisuAlgo游客贡献,特别是如果你不是英语母语者。目前,我们还以各种语言写了有关VisuAlgo的公共注释:
zh, id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, 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

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

致谢
这个项目是由来自NUS教学与学习发展中心(CDTL)的慷慨的教学增进赠款提供的。

使用条款

VisuAlgo是地球上的计算机科学社区免费。如果你喜欢VisuAlgo,我们对你的唯一的要求就是通过你知道的方式,比如:Facebook、Twitter、课程网页、博客评论、电子邮件等告诉其他计算机方面的学生/教师:VisuAlgo网站的神奇存在
如果您是数据结构和算法学生/教师,您可以直接将此网站用于您的课程。如果你从这个网站拍摄截图(视频),你可以使用屏幕截图(视频)在其他地方,只要你引用本网站的网址(http://visualgo.net)或出现在下面的出版物列表中作为参考。但是,您不能下载VisuAlgo(客户端)文件并将其托管在您自己的网站上,因为它是剽窃。到目前为止,我们不允许其他人分叉这个项目并创建VisuAlgo的变体。使用(客户端)的VisuAlgo的离线副本作为您的个人使用是很允许的。
请注意,VisuAlgo的在线测验组件本质上具有沉重的服务器端组件,并且没有简单的方法来在本地保存服务器端脚本和数据库。目前,公众只能使用“培训模式”来访问这些在线测验系统。目前,“测试模式”是一个更受控制的环境,用于使用这些随机生成的问题和自动验证在NUS的实际检查。其他感兴趣的CS教练应该联系史蒂文如果你想尝试这样的“测试模式”。
出版物名单
这项工作在2012年ACM ICPC世界总决赛(波兰,华沙)和IOI 2012年IOI大会(意大利Sirmione-Montichiari)的CLI讲习班上进行了简要介绍。您可以点击此链接阅读我们2012年关于这个系统的文章(它在2012年还没有被称为VisuAlgo)。
这项工作主要由我过去的学生完成。最近的最后报告是:Erin,Wang Zi,Rose,Ivan。
错误申报或请求添加新功能
VisuAlgo不是一个完成的项目。 Steven Halim博士仍在积极改进VisuAlgo。如果您在使用VisuAlgo并在我们的可视化页面/在线测验工具中发现错误,或者如果您想要求添加新功能,请联系Dr Steven Halim博士。他的联系邮箱是他的名字加谷歌邮箱后缀:StevenHalim@gmail.com。