数据结构之线性表(一般的线性表)

前言

接下来就开始正式进入数据结构环节了，我们先从线性表开始。

线性表

线性表（linear list）也叫线性存储结构，即数据元素的逻辑结构为线性的数据表，它是数据结构中最简单和最常用的一种存储结构，专门存储“一对一”逻辑关系的数据。何为“一对一”？即除去第一个和最后一个数据元素，其他元素均首尾相通，第一个元素只有下家没有上家，最后一个元素只有上家而没有下家。
此外还有一种特殊的线性表——循环链表，其将尾指针指向首元素从而形成了一个闭环。存储在同一个线性表中的数据，其类型必须一致，即要么都是整型，要么都是字符串型。如果从数据结构的逻辑层次上讲，那么线性表还可以进一步细分为一般线性表和受限线性表。

一般的线性表

一般线性表可分为顺序表和链表，链表又可分为单向链表、双向链表和循环链表等，如下图所示。

1. 順序表

如下图所示。

顺序表（Sequential List） 也叫顺序存储结构，即将数据依次存储在连续的物理空间中，是不是发现这样的结构很熟悉？是的，顺序表最底层的结构即为我们常听说的数组（Array），而针对顺序表的任何操作（包括查找、添加和删除等）都是基于遍历。

一般情况下，顺序表申请的存储容量应大于顺序表的长度。

2. 链表

链表（Linked List）也叫链式存储结构，即将数据依次存储在分散的物理空间中，但其逻辑关系仍是连续的，如下图所示。

与顺序表不同，链表的数据元素是随机存储的，因此其物理存储空间比较散乱，但其凭借着一条连接各个数据元素的线条，使数据元素之间保持着一定的逻辑关系。
链表还可细分为单向链表、双向链表和循环链表等，接下来让我们逐一进行学习。

（1）単向链表

单向链表也叫单链表，是链表中最基础的类型，通过单链表开启对于链表的学习，显然是明智的。
上面我们讲到，链表的物理存储空间是不连续的，但逻辑关系却可以保持。这是如何实现的呢？答案是指针域。单链表为每个元素配备了一个指针域（next），指向自己的直接后继元素。

直接后继元素即目标元素后相邻的一个元素，相似的还有后继元素、前驱元素和直接前驱元素。

因此，单链表的数据元素结构应该包含数据域（data）和指针域（next），它们也称为节点，如下图所示。

整个单链表的结构如下图所示

然而完整的链表结构应该有头节点、头指针和首元节点，如下图所示。

• 头指针：指向链表第一个节点（头节点或首元节点）的指针，用于指明链表的位置；
• 头节点：链表第一个不包含数据的空节点，不是必需的；
• 首元节点：链表第一个包含数据的节点，不过作用不如头节点大。

若有头节点，则头指针指向头节点；若无头节点，则头指针指向首元节点。

单链表中的动态和静态

在单链表中又有动态和静态之分。
动态链表也叫动态单链表，很多时候人们还会把它直接称作单链表，这也导致很多人都会把链表的关系树混淆。不过，动态链表确实就是单链表，因此在后面的文章中笔者将会把动态链表称为单链表。
我们已经讲解了顺序表和单链表，而静态链表可以理解为顺序表和单链表的结合体。
静态链表融合了顺序表和单链表的优点——既可快速访问元素，又可快速增加和删除元素。这是怎么做到的呢？
在静态链表中，数据依旧存储在数组中（和顺序表一样），物理空间也是连续的（和顺序表一样），但存储位置是随机的（和单链表一样），元素的逻辑关系则靠“游标”（指针）进行维持（和单链表一样）。
是不是感觉有点懵？别急，我们继续往下看。假设我们创建了一个长度为5的静态链表，它的基础结构如下图所示。

上图所示的是一个空数组。我们进一步剖析一下：一个静态链表，应该是由数据链表和备用链表组成的才对。为了方便理解，我们进一步假设这个长度为5的静态链表存储的是数据｛1，2,3｝，则存储状态可能如下图所示。

通常，备用链表表头指向a[0]的位置，而数据链表表头指向 a[1]的位置。

这里的数据链表即为存储数据的链表。该链表的每个节点除了包含所存储的数据（如1、2、3）之外还拥有一个整型变量，这个变量称为游标变量，用于标记该节点的直接后继节点的位置下标（如2、4、0）。而备用链表则是记录空闲位置的链表。通过备用链表，我们可以清晰、便捷地知道目标链表是否还有空余位置，还可以快速又准确地找到空余位置的物理地址。静态链表的完整结构如下图所示。

在这个例子里，数据链表依次连接的是 a［1］、a［2］、a［4］，而备用链表依次连接的是a［0］、a［3］。在静态链表中，a［0］位置默认是不存储数据的，若 a［0］位置有数据，则说明该数组已满，即链表已满。
让我们将数据链表和备用链表结合起来，便可以得到如上图所示存储｛1，2，3｝的静态链表的完鏊结构。

• 当想要查找元素时，便从数据链表的a［1］位置开始遍历，毕竟我们只知道a［0］和 a［1］的地址；
• 当想要修改元素时，我们依旧从数据链表的a［1］位置开始遍历，找到目标元素后直接修改它的数据域即可，游标不用修改；
• 当想要增加元素时，默认插入位置为备用链表a［0]的直接后继节点，这样就不用移动游标，时间复杂度仅为 O（1）；
• 当想要删除元素时，我们先找到目标元素，将其直接前驱节点的游标指向其直接后继节点，然后删除该节点，并将空余位置存放于备用链表中，方便下次使用。

(2)双向链表

有单向链表则必有双向链表，双向链表也叫双链表。无论是我们学过的单链表还是静态链表，节点中都只包含一个指针（游标），用于指向直接后继节点，这确实解决了最基本的“一对一”问题。
当我们编写算法需要多次查找目标节点的前驱节点时，如果使用单链表的话问题就严重了——效率超低！因为单链表是“一根筋的憨憨”，更适合“从前往后”进行遍历。
那怎么办呢？这时候双链表就诞生了。双链表的存储结构和单链表基本一致，只是一个箭头变成了两个而已，这里就不赘述了。双链表的节点结构如下图所示。

双链表的每个节点都有一个数据域和两个指针域，prior 指针指向直接前驱节点，next指针指向直接后继节点。

虽然双向链表的逻辑关系是双向的，但通常情况下，头指针依旧只有一个。

(3)循环链表

循环链表，即环状链表，只是把单链表最后一个节点的指针指向了第一个节点（头节点或首元节点），形成一个头尾相接的环状链表，像个圆圈一样，因此也被称为“环”。
循环链表之下还有单向循环链表和双向循环链表。
单向循环链表：与动态单链表一样，单向循环链表也经常被简单称为循环链表。为了方便大家理解，画了一个循环链表的整体结构图，如下图所示。

双向循环链表：有了对从单链表到循环链表变形过程的认知，相信双向循环链表也就不难理解了。这里就作为作业，读者可尝试一下把双向循环链表的整体结构完整地画出来。

拓展

说到循环链表，提到了环，就必然会想到约瑟夫环。大家可以试着实现约瑟夫环，以加深自己对链表的理解。