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.

这里我们将把五种不同的数据结构包括链表（Linked List）， 栈（Stack)，队列（Queue）， 双向链表（Double LinkedList)，双端队列（Double Ended Queue)全部放在链表的环节下。为了多样性，我们随机加载不同的模式：HTTPS://VisualGo.NET/En/List. 但是，您可以直接使用以下URL快捷方式访问单个模式：

几乎所有的计算机科学本科专业都会教链表数据结构。原因如下：

列表的顺序是非常重要的。其中位置顺序{a₀, a₁, ..., a_N-2, a_N-1 }。常见列表ADT操作为：

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

让紧凑数组名称为A，它的索引是[0..N-1] 的。

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::vector, Java Vector, 或者 Java ArrayList 实现所有可变大小的数组列表。
然而，经典的基于数组的空间浪费和复制/转移项目的浪费仍然是有问题的。

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

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

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:
a₀ with its item = 22 and its next = a₁,
a₁ with its item = 2 and its next = a₂,
...
a₆ 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?

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 a₀ — it is 22, nothing points to the head item,
2. The tail pointer points to a_N-1 — it is a₆ = 89, nothing is after the tail item.

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

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

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.

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.

由于链表的特性，它比简单数组有更多的情况。
大多数第一次学习链表的CS学生通常不知道所有的情况，直到他们发现他们自己的链接列表代码失败时。在这个电子讲课中，我们直接阐述所有的案例。
对于插入（i，v），有四个（有效）可能性，即v项被添加到：

1. 头节点（在当前第一个项目之前），i＝0，
   
2. 空链表（与先前的情况类似）
   
3. 当前链表的尾部，i＝n，
   
4. 链表的其他位置，i＝〔1…n-1〕。

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?

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

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

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?

对于remove（i），有三种可能性：

这种情况很简单：

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.

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.

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?

get（i）是慢的：O（n）。在链表中，我们需要执行从头部元素的顺序访问。
search（v）在最佳情况下，v在第一位置中找到, O(1)。在最坏的情况下，在列表中没有发现v，并且我们需要O（n）扫描来确定。

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

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

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?

Stack（堆栈）在教科书中有一些非常经典的应用，例如：

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

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

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

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

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

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

然而，许多出列和如列操作，我们可能有[-,-,-,-,-,6,2,3], front = 5, and back = 7。到目前为止，我们不能插队任何东西，尽管我们在数组的前面有很多空的空间。
如果我们允许前索引和后索引在索引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。在这一点上，我们不能插队任何其他东西。
我们可以放大阵列，例如使M＝2×8＝16，但是这将需要在比较慢的O（n）过程中从索引前（front）到后（back）再复制项目，以具有[6，2，3，8，10，11，12，13，-，-，-，-，-，-，-]，前面（front）＝0，后面（back）＝7。

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

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

在单链表中删除尾元素的主要问题是我们必须更新尾部指针，以便在删除后尾部指针能指向一个项目(即使我们可以通过尾指针直接访问尾项)。
双链表的可以从后面向前移动，我们可以找到尾部指针前的一个项目通过tail->prev…因此，我们可以通过这种方式实现尾部的移除：
Vertex* temp = tail; / /记住尾部项目
tail = tail->prev; //实现O（1）性能的关键步骤
tail->next = null; //删除这个悬空引用

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.

双端队列是一种抽象的数据结构，它是队列的拓展，它可以在队列的两端（头或尾）将元素加入或移除。

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

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

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

以下是关于链表的更深入的讨论：

1. 如果我们不存储尾部指针，会发生什么？
   
2. 如果我们使用仿真头怎么办？
3. 如果最后一个尾部项目指向头部项目呢？

• C++ STL：forward_list （单链表），堆栈 ，队列 （双链表），deque（实际上不使用双向链表，但另一种技术，看cppreference）

Java API：链表（已经是双链表）堆栈 队列（实际上是一个接口，通常使用链表）双端队列（实际上是一个接口，通常使用LinkedList类）

Python:
list for List/Stack/Queue
deque

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

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

• 我们也有一些编程问题，在某种程度上需要使用链表、堆栈、队列或双端队列等数据结构：UVA 11988 - 破键盘（又名北菊文本）, Kattis-退格, and Kattis-整数列表.
  

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