重学数据结构（二）：线性表

线性表（List）：是零个或多个数据元素的有限序列，它是最常用且最简单的一种数据结构。

前提说明，本篇文章只会介绍线性表相关概念的理论知识，对线性表操作的算法实现，会单独用一篇文章来介绍，现已完成，感兴趣请戳：线性表的算法实现之JS

基本概念和特点

线性表元素的个数 n （n ≥ 0）定义为线性表的长度，当 n = 0 时，称为空表。

在较复杂的线性表中，一个数据元素可以由若干个数据项（item）组成，在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称为文件（file）。

线性表的常见操作有：创建和初始化、重置为空表、插入数据、删除数据、合并线性表等。

当数据元素为非空有限集合时，线性结构具有如下特点：

• 存在唯一的一个被称为“第一个”的数据元素
• 存在唯一的一个被称为“最后一个”的数据元素
• 除第一个之外，集合中的每个数据元素均只有一个前驱
• 除最后一个之外，集合中的每个数据元素均只有一个后继

顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素，它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。由于线性表的每个数据元素的类型都相同，所以我们常用一维数组来实现顺序存储结构。

相关概念

通过以下三个属性来描述顺序存储结构：

• 存储空间的起始位置：即数组 data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度 MaxSize
• 线性表的当前长度：Length

要注意区分数据长度和线性表长度这两个概念，数据的长度即数组的长度，是存放线性表的存储空间的长度，存储分配后这个量就一般是不变的；而线性表长度是线性表中数据元素的个数，是会随着线性表的插入和删除操作进行相应变化的。所以，线性表的长度应该小于等于数组长度。

存储器中每个存储单元都有自己的编号，这个编号称之为地址。对于每个数据元素来说，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间，我们假设占用的都是 c 个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系：

LOC(a_i+1) = LOC(a_i) + c

其中 LOC 表示的是获得存储位置的函数。由此我们可得对于第 i 个数据元素 a_i的存储位置可以由a₁推算得出

LOC(a_i) = LOC(a₁) + (i - 1) * c

通过这个公式，我们可以随时算出线性表中任意位置的地址，也可以算出对每个线性表位置的存入或取出，算法复杂度都是一样的，为 O(1)，我们把具有这一特点的存储结构称为随机存取结构。

优缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

链式存储结构

链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这意味着这些数据元素可以存在内存未被占用的任意位置。

线性链表

为了表示每个数据元素 a_i 与其直接后继数据元素 a_i+1 之间的逻辑关系，对数据元素 a_i 来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 a_i 的存储映像，称为结点（Node）。

n 个结点（a_i的存储映像）链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，我们又称之为线性链表或单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

我们把链接中第一个结点的指针（即存储位置）叫做头指针；最后一个结点的指针为“空”（通常用 NULL 或 ^{^ 符号表示）。}

有时我们为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点，头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

注意区别头指针和头结点：
头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
• 头结点不一定是链表必须元素

静态链表

对于早期的编程高级语言，如：Basic、Fortran 由于没有指针，那我们该怎么描述它们的单线表呢？我们的做法是用数组来代替指针，把这种用数组描述的链表称为静态链表，这种描述方法还有起名叫做游标实现法。

我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表行程一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。

双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，一个指向直接前驱。