数据结构其一线性表

数据结构：线性表

前言（啰嗦两句）

作为一名普通野鸡大学的毕业的科班生，虽然在学校学过《数据结构》这样一门课程，但彼时的我所有的编码经验也就只是写过一些诸如杨辉三角，水仙花数之类的例题，因而在结课后很快就还给老师了……

最近颇乏于~~写应用层代码~~画页面，终于又双叒叕难得想学数据结构了，遂打算开一个系列，希望能够有始有终的写完。

yuchiXiong/data-structure: 我又双叒叕准备学数据结构啦

1. 线性表是什么？

wiki: 线性表是一个具有顺序的，由同类型数据组成的集合，它是常用的数据结构之一。线性表具有几个基本特征：

有限性，线性表是一个有限序列。
有序性，线性表具有基本的顺序属性。
同一性，线性表元素具有相同的类型。

关于上述3，在参考广义表的相关定义后，我认为应该更完整的描述为：线性表由同类型数据组成，且该类型被限定为原子类型（如整数、字符串、布尔值等），而非结构类型（如数组、结构体、类等）。

关于 线性 ，我们知道数据结构中还定义了其他诸多非线性数据结构如树、图等。它们在计算机中存储时并非真的表现为树状或图状，而是从逻辑上抽象为树状或图状。线性结构与之类似，当我们将线性表的元素按照逻辑顺序排列时，它呈现为一条线段，因而我们称之为线性结构。对应的，当我们将广义表的元素按照其层次排列时，它并不是一条线段，而更像是一个平面，这正是我们说广义表是一种非线性数据结构的原因，同时也是线性表同一性限制存在的原因。

2. 顺序存储与链式存储

线性表的线性是逻辑层面的，但实际无论是线性表，广义表，还是树，图等，在计算机中存储时，都无外乎两种形式：顺序存储和链式存储。

2.1 顺序存储与顺序表

在计算机中存储数据的第一种方式是顺序存储，基于顺序存储方式实现的线性表称为顺序表，举一个比较形象的例子：

你和小伙伴一起去看电影，你当然希望可以和小伙伴们坐在一起，因而你们选择购买了某一座位开始往后的多个连续的座位。

不难发现，在这一案例中有几个重要的细节：

我们需要一次性购买多个连续的座位。
当我们知道第一个座位的编号时，很容通过第一个座位的编号，计算出后面的座位的编号。
当我们希望在保持原有的座位顺序的前提下，插入一个新的座位时，我们需要将原有的每一个座位向后移动一个位置。
当我们希望在保持原有的座位顺序的前提下，删除一个已有座位时，我们需要将原有的每一个座位向前移动一个位置。

我们将这个例子映射到顺序表中，就可以得到顺序表的几个重要特征：

在使用顺序表时，我们需要一次性申请存储元素所需要的空间。
通过元素下标我们可以快速的访问元素。
在插入/删除顺序表中的元素时，我们需要将原有的每一个元素向后/向前移动一个位置。

这些特征决定了顺序表最重要的优点：访问速度快。通过下标我们能在 O(1) 时间复杂度内访问到某个元素。

同时也暴露了顺序表的缺点：

由于在使用前需要一次性申请指定容量的空间，当遇到数据增长速度较快的场景时，顺序表容量可能会达到最大值而无法添加新的数据，但如果一次性申请的空间过大，则又容易造成浪费。
如果需要对顺序表进行扩容，则需要额外的空间来进行数据的复制。
如果需要插入元素到顺序表中，则需要将原有的每一个元素向后移动一个位置，时间复杂度为 O(n)。

最后，以 C 语言为例，我们可以将数组看作一个顺序表，但值得注意的是，在部分动态语言如 Python/JavaScript/Ruby 等中，数组元素的类型是动态的，它可以是数组、对象等任何类型的数据，此时的数组则更应该看作广义表而非线性表。

2.2 链式存储与链表

在计算机中存储数据的另一种方式是链式存储，基于链式存储方式实现的线性表称为链表。

链表的每一个节点分散存储在不同的地址，而后使用一个 next 指针来指向下一个节点，最终实现了维护其逻辑上的线性的目的。这样做的好处是当我们需要对链表进行修改时，无需再对其他元素进行移动操作：

当需要在链表中插入新节点时，我们只需要修改目标位置上一个位置节点的 next 指针指向新节点，然后将新节点的 next 指针指向原有位置上的节点即可。
当需要在链表中删除一个节点时，我们只需要将目标位置上一个位置节点的 next 指针指向目标位置下一个节点即可。
当需要在表头插入新节点时，我们只需要将新节点的 next 指针指向原有的表头即可。
当需要在表尾插入新节点时，我们只需要将表尾节点的 next 指针指向新节点即可。

但由于链表的线性关系是通过 next 指针来实现的，因此当希望读取链表的某一个元素时，无法通过下标的方式以 O(1) 的时间复杂度完成而是需要进行遍历，时间复杂度为 O(n)。

基本单链表节点实现 LinkedNode.cpp

3. 常见线性数据结构

在实际的使用过程中，我们经常基于线性表来实现一些更符合业务场景的数据结构。

3.1 变长数组

由于顺序表始终需要维护一个固定的长度，在使用过程中扩容极不方便，因而我们可以基于顺序表来实现一个变长数组，使其能够在使用的过程中进行动态扩容。

Java Collection Framework（简称 JCF) 中实现的 ArrayList/Vector 以及 CPP STL Container adaptors 中提供的 Vector 都可以看作一个变长数组。其实现的原理大致为，当向数组中添加或删除元素时，首先检查数组的容量：

如果当前数组的容量不足以添加新的元素，将数组扩容（通常为原来的两倍），然后将原来的数据复制到新的数组中。
如果当前数组的使用容量低于阈值（通常是当前容量的 1/4 ），将数组的容量缩小为原来的一半，然后将原来的数据复制到新的数组中。

变长数组实现 Vector.cpp

3.2 链式线性容器

基础的链表节点实现在使用时并不太方便，我们可以基于此封装一个与变长数组相似的链式线性容器。

基于单链表的链式线性容器实现 SLinkedList.cpp

基于双向链表的链式线性容器实现 LinkedList.cpp

3.3 顺序栈

栈是一种受限制的线性表，其特点是 First In Last Out (简称 FILO )，即先进后出。

现实生活中的羽毛球桶就可以看作一个栈，当一个球桶里装满球时，只能先取出后放进的羽毛球，再取出倒数第二次序放入的羽毛球。

栈有两个基本操作：

将元素押入栈顶，即入栈
从栈中弹出栈顶元素，即出栈

栈是一种非常实用的数据结构，例如前端开发中比较常提及的页面跳转栈，在页面跳转过程中，我们可以将页面跳转的每一步都保存在栈中，当页面进行回退操作时，我们可以从栈中取出每一步的跳转页面，直到栈为空。

基于线性表我们可以很快的实现一个栈数据结构，不过由于线性表具体分为顺序表和链表两种，因而实现栈也有两种方式。其中通过顺序表实现的栈被称为顺序栈。

实现顺序栈通常来说不太困难，但考虑到顺序表固定长度的特性，为了使顺序栈拥有更好的可用性，我们可以通过变长数组来实现。而对于栈的弹出和押入操作，只需要简单的对变长数组队尾的元素进行简单的操作即可。同时，由于栈的操作中不涉及到在已有序列中插入和删除元素的操作，因而恰好避开了顺序表在插入和删除元素时需要移动元素的问题。

顺序栈实现 ArrayStack.cpp

3.4 链式栈

除了使用顺序表实现的栈，我们还可以使用链表来实现栈。链式栈和顺序栈本质上来说没有什么太大的区别，只是底层的存储方式不太一样。

基于链表实现的栈，主要的思路是维护一个链表的头节点，当押入新元素到栈内时，只需要基于新元素创建一个新的节点，并将头节点插入到新节点的后面即可。而弹出时，只需要将内部维护的头节点更新为当前头节点的下一个节点即可。以下给出的参考代码实现是基于双向链表的，但由于栈数据结构始终只对尾节点进行操作，因而使用双向链表并不能简化操作，甚至还会导致实现的抽象难度增加。

链式栈实现 LinkedStack.cpp

3.5 顺序队列，假溢出和循环队列

队列同样是一种受限制的线性表，其特点是 First In First Out (简称 FIFO )，即先进先出。

在现实生活中，我们其实经常使用到队列的特性，比如超市的排队等等。对于一个队列我们有两种基本的操作：

元素入队，即把元素插入队列的尾部
元素出队，即把队列的头元素删除

与顺序栈和链式栈相同，队列也有两种实现方式，一种是顺序队列，另一种是链式队列。

同样考虑到顺序表定长的特性，在实际实现中我们可以考虑基于变长数组来实现队列以支持自适应动态扩容和缩容。

当元素入队时，我们只需要把元素插入到变长数组的尾部即可，但当元素出队时问题就显的稍微复杂一些了。当元素出队时，我们需要删除队列的头元素，考虑到如果将后续元素都向前位移必定会造成大量的性能损耗，我们可以维护一个标识来表示实际的队列头。然而这样又回引出新的问题，既当元素不断的出队与入队，队头的标识会越来越靠后，这样势必会导致顺序队列中存在大量的连续的空间浪费。

基于变长数组的顺序队列实现 ArrayQueue.cpp

我们可以使用循环队列来解决这些问题，既当队列元素入队时，如果当前队尾元素的下标超过了队列的最大容量，那么我们就将队尾元素的下标重置为0，这样可以保证队列中的元素是连续的同时，不浪费之前的空间。而当元素出队时，我们还是一样删除队尾元素即可。当然，由于循环队列从存储上来说并不是完全连续的，在对变长数组进行动态扩容时我们需要两段的元素列表分别拷贝到对应的位置中。

循环顺序队列实现 CircularQueue.cpp

3.6 链式队列

很显然，基于链式存储结构实现的队列被称为链式队列。

由于队列的两种常用操作分别作用于队头和队尾，当我们使用单链表实现时，操作队尾元素很容易，但是操作队头元素则需要遍历整个队列，这样会带来较大的性能开销。此时我们可以增加一个指向上一个节点的 prev 指针来将单链表修改为双向链表，然后以同样的方式保存对头元素的指针和队尾元素的指针，之后就可以方便快捷的进行出队和入队操作了。

双向链表实现 DoublyLinkedNode.cpp

基于双向链表的链式队列实现 LinkedQueue.cpp

数据结构其一 线性表

数据结构： 线性表