链表

1. Introduction

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.

1-1. 5种模式

这里我们将把五种不同的数据结构包括链表(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.

2. 动机

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

2-1. 列表抽象数据类型

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

2-2. 结果

[This is a hidden slide]

2-3. 数组实现 - 第一部分

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

2-4. 数组实现 - 第二部分

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

2-5. 时间复杂性小结

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

2-6. 固定空间问题

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

2-7. 变量空间

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

2-8. 观察

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

3. 链表(LL)

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

3-1. 链表的顶点C++实现

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?

3-2. 答案

[This is a hidden slide]

3-3. 链表,其他数据元素

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.

3-4. 变化

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

3-5. 获取(i)- 比数组慢很多

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.

3-6. 搜索(v)-不优于数组

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.

3-7. 插入 - 四种情况

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

3-8. 插入(i, v) - 在头节点插入(i=0)

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?

3-9. 答案

[This is a hidden slide]

3-10. 插入(i, v) - 插入v到一个空的链表

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

3-11. 插入(i, v) - 在[1, N-1] 种插入

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).

3-12. 插入(i, v) -

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?

3-13. 答案

[This is a hidden slide]

3-14. 移除 - 三种情况

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

3-15. 移除(i)- 在头节点移除(i = 0)

这种情况很简单:
if (head == NULL) return; // 避免当SLL为空时崩溃
Vertex* temp = head; // 之后我们可以删除它
head = head->next; // 更新头部指针
delete temp; // 删除旧指针
在上面的(较短)示例链表 [22 (head)->2->77->6 (tail)] 上反复尝试RemoveHead()。它将继续正确地工作直到链表包含一个项目,其中头=尾部项目。如果LL已经是空的,因为它是无效的,我们阻止执行。
讨论:如果我们使用简单数组实现来移除列表的头,会发生什么?

3-16. 答案

[This is a hidden slide]

3-17. 移除(i)- 在[1, N-2]种移除

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.

3-18. Remove(i) - At Tail (i = N-1) - 第一部分

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.

3-19. Remove(i) - At Tail (i = N-1) - 第二部分

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?

3-20. 答案

[This is a hidden slide]

3-21. 时间复杂度小结

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

3-22. 链表的应用

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

4. 堆栈

堆栈是一种特殊的抽象数据结构或者组合,其主要的(仅有的)操作为将元素加入栈中,称为进栈和将元素移除,称为出栈。堆栈是一种后进先出(LIFO-Last-In-First-Out) 的数据结构。

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

所有操作的时间复杂度为O(1)。

4-1. 设计选择

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?

4-2. 结果

[This is a hidden slide]

4-3. 栈的应用

Stack(堆栈)在教科书中有一些非常经典的应用,例如:
  1. 一些其他有趣的应用程序但没有用于教学目的。
  2. 括号匹配,
  3. 后缀计算器,

4-4. 括号匹配问题

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

4-5. 时间复杂度为O(n)的解法(用 栈)

[This is a hidden slide]

4-6. 计算后缀表达式

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

4-7. 时间复杂度为O(n)的解法(用 栈)

[This is a hidden slide]

5. 队列

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

5-1. 数组实现问题 - 第一部分

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

5-2. 数组实现问题 - 第二部分

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

5-3. 数组实现问题 - 第三部分

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

5-4. 数组实现问题 - 第四部分

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

5-5. 这个时候就需要用到链表了

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

5-6. 队列的应用

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

6. 双向链表(DLL)

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

6-1. Remove(i) - At Tail (i = N-1), 重新访问

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

6-2. 固定常数额外的步骤

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.

7. 双端队列(Deque)

双端队列是一种抽象的数据结构,它是队列的拓展,它可以在队列的两端(头或尾)将元素加入或移除。
在我们的可视化中,双端队列基本上是受保护的双链表。我们仅能搜索头/尾的元素(读取头/尾),在头/尾插入新的元素(从头/尾推进),将现有头/尾元素移除(删除头/尾)。所有的操作复杂度为O(1)。

7-1. 出列的应用

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

8. 总结

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

9. 更多

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

9-1. 潜在的讨论话题

以下是关于链表的更深入的讨论:
  1. 如果我们不存储尾部指针,会发生什么?
  2. 如果我们使用仿真头怎么办?
  3. 如果最后一个尾部项目指向头部项目呢?

9-2. 我们现在的答案

[This is a hidden slide]

9-3. C++ STL 和 Java API 的实现

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

9-4. Python and OCaml Standard Library

Python:
list for List/Stack/Queue
deque


OCaml:
List
Stack
Queue
No built-in support for Deque

9-5. 在线测试

有关这一数据结构的一些更有趣的问题,请在链表 训练模块上实践(不需要登录,只有初级的和中等难度)。
但是,对于注册用户,您应该登录,然后转到 主训练页面 ,完成这个模块,这样您的成就将被记录在您的帐户。

9-6.


尝试巩固和提高你对数据结构的理解。如果可以简化你的算法,你可以使用C++, STL或Java API。