算法系列教程05 - 你真的了解线性表吗？
阅读本文大概需要 7 分钟。
线性表是数据结构最最基本的一个概念，可是你真的了解线性表吗？
线性表的存储方式是什么？栈和队列是线性表吗？
如果能正确地回答这两个问题，那么你就不用浪费时间看本文的内容了。否则，不管你觉得线性表是多么基础的东西都还是花几分钟把本文看完吧。
本系列教程的接下来几篇文章都是讲数据结构的基础，有人已经学过并掌握了，也有人没学过或者早已忘记了。不管怎么样，就当是复习一下吧。对于还没有系统学过数据结构的同学，正好可以用碎片时间快速系统地学习一下。本系列教程关于数据结构的知识不会讲每种数据结构的代码实现，因为几乎所有语言都内置实现好了。
基本概念
在本文开始之前，我们先了解一下线性表、顺序表和链表这三个基本概念：
线性表（Linear List）：线性表是最基础、最简单、最常用的一种基本数据结构。线性表存储的每个数据称为一个元素。一个线性表是 n 个具有相同特性的元素的有限序列。线性表有两种存储方式：顺序存储方式和链式存储方式。
顺序表（Sequence List）：顺序表就是线性表的顺序存储方式，以数组的形式保存。数组的顺序存储方式使得逻辑上相邻的元素，其在物理存储单元中也是相邻的。并且数组是静态分配的，即在使用数组之前需要分配固定大小的空间。可以通过索引直接得到数组中的元素，即获取数组中元素的时间复杂度为 O(1)。
链表（Linked List）：链表就是线性表的链式存储方式。链表中的元素在内存中不是连续分配的，即逻辑上相邻的两个元素在物理存储单元中不一定是相邻的。而且它的分配是动态的，即创建链表时不需要事先指定大小。链表每个元素都过指针来指向下一个元素地址，将链表中的元素有序地串起来。
综上，线性表有顺序和链式两种储存方式，分别由顺序表和链表这两种数据结构实现。
顺序表很简单，它就是下标和元素一一对应的数组，没什么好讲的。下面重点讲一下链表。
链表
链表（Linked List）是一种各元素按线性排列的数据结构。与数组不同的是，数组的线性顺序由数组的下标决定，链表的顺序是由各个元素的指针来决定的。链表主要分为三种：
-
单向链表（Singly Linked List）
-
双向链表（Doubly Linked List）
-
循环链表（Circular Linked List）
三种链表的元素节点都包含数据和指针，它们的操作有插入、删除和查找。当其中一个节点被删除或在节点前插入一个新节点时，都需要改变相关节点的指针指向。
单向链表
单向链表又称单链表，是链表中最简单的一种。一个单向链表的元素节点被分成两个部分。第一个部分存储节点的信息，第二个部分存储下一个节点的地址，最后一个节点则指向一个空值。一般第一个节点称为链头，最后一个节点称为链尾。单向链表只可向一个方向遍历。下面是单向链表的简单示意图：
一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。
双向链表
双向链表又称双链表。相对于一个节点只有一处指针的单链表，双链表中的一个节点有前、后两个指针，通用分别用 Prev 和 Next 表示。Prev 指向前一个节点，称为前驱，Next 指向后一个节点，称为后继。第一个节点的 Prev 指向空值或者空列表，最后一个节点的 Next 也指向空值或者空列表。下面是双向链表的简单示意图：
查找一个结点可以从任何结点开始，每次可以访问节点的前一个节点也可以访问后一个节点。
循环链表
循环链表和单向链表、双向链表基本一样，区别是它的首节点和尾节点连接在了一起，即尾节点的 Next 指向的是首节点而不是空值，这种操作在单向和双向链表中皆可实现。循环链表可以看着是无头无尾单向或双向链表。下面是循环链表的单向与双向实现示意图：
循环链表是闭环的，所以没有链头和链尾的说法。循环链表的设计对于算法插入操作更加容易，因为不需要考虑链头和链尾的情况。
到这我们已经知道线性表存储的存储方式了。接下来我们再来看看堆栈和队列这两种数据结构。
栈和队列
栈和队列是我们常用的两种数据结构，栈的后进先出和队列的先进先出，我们早已耳熟能详了。其实知道这点我觉得就够了，只是你可能会好奇它们是不是属于线性表呢？我先不直接回答这个问题，我们还是先看看栈和队列是都是什么样的结构和有什么操作吧。
栈
栈（Stack），又称为堆栈，它实现的是一种后进先出（Last In First Out, LIFO）策略，被删除的是最后插入的元素。栈的插入操作称为压入（Push），它的删除操作称为弹出（Pop）。栈有栈底（Bottom）和栈顶（Top），压入和弹出都是在栈顶进行操作。下面是栈的简单示意图：
从图中我们可以看到，栈中的元素是线性存储的，元素的组成其实就是一个线性表，只是它被限制了只能在一端进行进出操作。栈既然是线性表，在具体应用中就可以用顺序表或者链表来实现。
队列
队列（Queue）实现的是一种先进先出（First In First Out, FIFO）策略，被删除的是在集合中最先插入的元素。队列的插入操作称为入队（Enqueue），删除操作称为出队（Dequeue）。队列有队头（Head）和队尾（Tail），当有一个新元素入队时，它会被放在队尾的位置。下面是队列的简单示意图：
和栈一样，队列也是一种线性表，只是被限制在两端进行进出操作，在具体应用中也可以用顺序表或者链表来实现。
总结
线性表是一个大的概念。从存储方式上来说它有顺序存储和链式存储，分别对应顺序表和链表两种数据结构。栈和队列都属于线性表中的一种特例。虽都是基础知识，但看完本文，你有些许收获吗？反正我是挺有收获的。
本文图片来源：
http://t.cn/EZUNyFi
http://t.cn/EZUCgaV
本文参考：
算法导论，第三版，第 10 章