4.1 线性数据结构

正如在现实世界中一样，只有当我们拥有足够多的东西，才会迫切需要一个储存东西的容器。对于数据来说也是一样，只有数据足够多，我们才有必要考虑它的组织形式。这也是为什么把数据结构放到这一章节介绍的原因，我们掌握足够多的Python知识，才可以操作更多的数据，我们才会重视数据结构的作用。这些储存大量数据结构的组织形式，在Python里称之为容器，它包括列表、字典等。

线性结构是最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。它们之间的组织顺序由添加或者删除的顺序决定。一旦一个数据元素被添加进容器，它相对于前后一直保持该位置不变。诸如此类的数据结构被称之为线性数据结构。

线性数据结构有两个端点，有时候称为左和右，有时候称为前和后，甚至也可以被称为顶部和底部。这些名称并不重要，重要的是线性数据结构中元素的添加和移除方式，特别是添加和移除的位置。这些变种的形式产生了计算机科学最常用的线性数据结构。他们出现在各种算法中，并可以用于解决很多重要的问题。

4.1.1 链表

链表是由许多相同数据类型的元素项按照特定顺序排列而成的线性表。链表的特性是其各个数据项在计算机内存中的位置是不连续且随机存放的。这样做的优点是数据的插入和删除相当方便，有新数据加入就向系统申请一块内存，而数据被删除后，就可以把这块内存空间还给系统，加入和删除都不需要移动大量的数据。其缺点是设计数据结构时比较麻烦，而且在查找数据时，也无法像静态数据那样可以随机读取，必须按照顺序查找到该数据为止。

日常生活中有很多和链表类似的逻辑结构，比如可以把单向链表想象成为“高铁”，有多少乘客就用多少车厢，节假日人们出游的时候，就需要较多的车厢，平时人少的时候就减少车厢数量。

单向链表也叫单链表，是链表中最简单的一种组织形式，如图4-1所示。单向链表中每个节点包含两个域，一个信息域（也叫元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

元素域就是存储数据A1的区域，指针就是保存指向下一个链表的地址。最后一个节点的链接域指向空，为NULL。

4.1.2 栈

栈是一个有序的集合，其中添加和移除新项总发生在同一端，这一端通常称为顶部。与顶部对应的是底部。栈的底部很重要，因为在栈中靠近底部的元素是存储时间最长的，而最新添加的元素反而是最先被移除的，这种排序原则就是后进先出原则（LIFO，Last In First Out）。如果根据在集合内的存储时间长度这个因素来做排序，较新的元素靠近顶部，较旧的元素靠近底部。

例4-1 用列表来演示堆栈的后进先出原则

先创建一个空的列表，然后连续插入两个数据元素1和2，这个时候列表stack中存储了两个元素。此时，用pop命令挤出来一个元素，先挤出来的是数字2，stack列表中只剩个下数字1，再执行一次pop操作，把数字1也挤出来了。这个例子充分说明了数字2后进先出的过程。

这种特性非常实用，可以想到使用计算机时所碰到的例子。例如，每个Web浏览器都有一个“返回”按钮，当我们浏览网页时，这些网页的地址被放置在一个堆栈中。如果单击“返回”按钮，将按相反的顺序浏览刚才的页面。

4.1.3 队列

队列也是数据元素的有序结合，其中添加新项的一端称为队尾，移除项的一端称为队首。当一个元素从队尾进入队列时，一直向队首移动，直到它成为下一个需要移除的元素为止。也就是说，最新添加的元素必须在队尾等待。集合中存活时间最长的元素在队伍首部，这种排序称为先进先出（FIFO）。队列的规则很容易理解，比如排队等待看电影，在杂货店的收银台等待付款，在餐厅等待排队就餐等。队列是有限制的，因为它只有一条入口，也只有一条出口，不能插队，只有等待了一定的时间才能排到前面。

在现实生活中，队列这个词其实挺好理解的，因为到处都可以见到。比如等公交需要排队，超市买东西付钱也要排队。但有一点与现实中的队列不同，那就数据结构中的队列是不准许中途放弃离开。