每周学点大数据 | No.8基础数据结构之线性表

No.8期

基础数据结构之线性表

Mr. 王：为了以后的知识描述方便，这里简单介绍一下数据结构的概念。数据结构是一个广泛存在于计算机科学中的概念。曾经有一位计算机界的大师说：“数据结构+算法=程序”。随着计算机科学的发展，虽然现在这个理论被认为不够全面，但也足以说明数据结构的重要性。

小可：这么说，数据结构拥有和算法同样重要的地位了！那么数据结构究竟是什么呢？

Mr. 王：在客观世界中，信息是多种多样的，有数字、颜色、图形、文本、声音等。但是这些信息“本身”并不能直接存储在计算机中，而是要以数据的形式存储在计算机中。比如要描述一个颜色，就可以用显示器输出的红色、绿色、蓝色的值(RGB值)来表示；描述一张图片，就是用多个这样的RGB值或标识颜色的数据标签来记录的。不论何种类型的信息都要以数据的形式在计算机中进行表示。

不过，这些数据不能杂乱无章地存放在计算机中；否则，不仅损失了信息之间应有的逻辑关系，而且查找起来效率也比较低，所以我们就要试图去发现这些数据之间的一些相互关系，并且利用这些关系将数据组织成一种逻辑结构。这种结构就是数据结构，它研究的就是如何依照这些数据之间的逻辑关系将数据表示在计算机中。对于一组数据，我们不仅要关注它们的逻辑结构，也就是数据之间在逻辑上的相互关系，在实际使用时，还要关注它们的存储结构，也就是说，这些数据在内存（磁盘）中是如何存储的。这都是数据结构研究的范畴。

小可：既然有人说，程序等于数据结构加算法，那么数据结构和算法之间又有怎么样的关系呢？

Mr. 王：这是个很好的问题，计算机中的算法都要对数据进行处理，而既然要处理数据，就要涉及数据如何存储在计算机中，如何能够高效地访问和处理数据，这就需要用到数据结构，所以说算法离不开数据结构。而当我们需要使用、访问、添加、删除、修改存储在数据结构之中的数据时，也要依照数据结构的特点进行操作，而增加、删除、修改、查找这些操作本身就是一种算法，所以说数据结构也离不开算法。

小可：原来是这样，数据结构和算法之间的联系还真是紧密啊。

Mr. 王：下面我们就来介绍一下最基础的数据结构——线性表。

小可：线性表是不是就是这些数据一个挨着一个地线性存储的结构呢？

Mr. 王：是的，线性表是由相同类型的数据按照一定的顺序排成的序列。这是一种非常常见的基础数据结构，使用非常广泛。

小可：具体的线性表都有哪些呢？

Mr. 王：常见的线性表有链表、数组线性表、栈和队列。

小可：数组我知道！ C语言和Java中就有，将同一类型的数据存储在连续的内存空间里，通过首地址和数组下标可以访问到数组中的每一个元素。嗯，数组果然是符合线性表的定义的。

Mr. 王：是的，数组就是一种典型的线性表。我们学过了算法分析，可以考虑一下，数组只要知道首地址和下标就可以找到一个元素，这意味着能够以O(1)的复杂度访问其中的每一个元素，从这个角度来看，数组也是具有其优势的。但是增加和删除其中的元素却比较麻烦，因为如果要在数组中间增加一个元素，需要将后面的元素全都向后移动一个位置，平均情况需要O(n)次移动数据，是非常耗时的。前面我们也讨论过，如果数组内容是无序存储的，查找其中某个特定的值就会比较困难，要逐个地去访问比较，需要O(n)的时间复杂度。从空间角度来讲，如果我们确定知道元素的数量，那么用数组会比较节省空间；但是对于那些不知道有多少个元素、需要频繁添加和删除的元素集合来说，就需要在定义数组时让它稍大一些，这就造成了空间浪费。

另外一种比较常见的线性结构是链表，它的构建是将元素一个一个地链接起来。访问链表时有一个首地址，我们可以通过这个首地址找到链表的第一个元素，这和数组是一样的；但和数组不一样的地方是，它的元素可能不连续地存储在空间中，而是每个元素的后面都带着一个地址，这个地址指向下一个元素的位置。我们想要逐个访问元素时，就要先找到第一个元素，通过第一个元素后面的地址找到第二个元素，然后再通过第二个元素后面的地址找到第三个元素，依此类推。

链表的例子

小可：那访问一个元素的时间复杂度就不是O(1)了，从平均情况来讲，访问一个元素的时间复杂度就是O(n)。

Mr. 王：很好，但是链表也并不是没有优点。链表的优点是，在一个特定的位置添加元素，并不需要移动任何元素的位置，只需要将其前面元素后面的地址指向新元素，再将新元素后面的地址指向前面元素原来的后面地址就可以了。删除也是一样，只需要将待删除元素前面元素的指针指向删除后面的元素，然后释放掉被删除元素的内存即可。

链表的插入操作

链表的删除操作

小可：这个时间复杂度是O(1)。

Mr. 王：这说明链表适合用于那些需要频繁进行添加、删除的元素集合。另外，从空间角度来讲，链表的长度相对比较灵活，它不像数组，即使那个位置是空的，也要占用预先申请的内存空间；而链表每有一个元素，就占用一个元素和它后面地址的存储空间，相对于元素数量变化幅度比较大的元素集合来说，链表的存储更加节省空间。

小可：嗯，果然是互补的两种结构，要根据实际情况选择适合的结构来存储。

Mr. 王：这里还有两种非常重要的线性结构要介绍，这两种结构非常简单，但却是很多算法的基础和组成部分，它们就是栈和队列。

小可：那什么是栈和队列呢？

Mr. 王：栈和队列都是特殊的线性表，不论用数组还是链表来实现它们都是可以的。但是它们除了是线性表以外，还有自己的特殊性质。其实栈和队列这两种结构在生活中都可以见到。

先说队列吧。平时我们在各种公共场所进行排队时，如果将每一个人都看作一个元素的话，那么组成的就是一个队列。队列的特点就是，每一个新加入的元素，都要放在整个队列的最后面；而当一个元素要离开队列时，总是从队列的最前端离开。这就是说，先进入队列的元素先离开队列，后进入队列的元素后离开队列，总结起来就是FIFO策略（先进先出策略）。队列的常见操作有入队列（enqueue、push，让一个元素进入队列）、取队首（front，获得队列最前端元素的值）和出队列（dequeue，让队首的元素离开队列）等，这些算法都非常简单。

小可：嗯，队列还是很直观的。那什么是栈呢？

Mr. 王：栈的特点和队列正好相反。用生活中的例子来说，就像是一个书箱子，箱子只有一个朝上的开口，我们可以把书从上面放进箱子，但是想要取书时，也只能从箱子的顶端取走，不能直接从箱子的中间和底部取书。所以，先进入箱子的书就会最后离开箱子。栈只有一个访问端，元素的出入都只能通过这一个端，这样我们也可以分析出，先进入栈的元素会被放在栈的最底端，也就是说，它会最后离开栈。总结起来就是LIFO策略（后进先出策略）。对栈的常见操作有入栈（push，将一个新元素放在栈顶的位置）、出栈（pop，将栈顶的元素弹出栈，露出下一个元素作为栈顶）和取栈顶元素（top，获得栈顶元素的值）。

栈的示意图

小可：嗯，我懂了。可是栈在计算机中有什么用呢？

Mr. 王：看起来队列在生活中似乎更加常见一些，但在计算机中，栈的应用却是非常广泛的，我们可以通过一个非常经典的例子来介绍计算机是如何利用栈这个结构的。

内容来源：灯塔大数据