1.线性表概述

线性表是一个有序的序列

1.1.定义

线性表是有n（n>=0）个节点的有限序列（A0、A1、……、An-1）。A0为起始结点，An-1是末尾结点，i称为Ai的序号或位置。

1.2.线性表基本运算

主要有以下8个操作场景

（1）create：创建线性表

（2）clear：清空线性表

（3）length：线性表的长度

（4）insert：在某个索引i处插入一个元素

（5）remove：从线性表删除某个索引i对应的线性表元素

（6）search：查询某个元素是否在线性表中

（7）visit：访问某个索引i对应的线性表元素。

（8）traverse：遍历整个线性表

1.3.使用场景

使用场景广泛，比如记录操作步骤。

2.线性表数组实现

线性表的数组实现就是将数据元素存储在一块连续的空间中。物理位置上相邻的元素在逻辑上也是相邻的。

下面是一个简单的数组实现的线性表。

其中data表示指向数组的引用，length表示元素个数，maxSize表示当前可存储的元素的最大数量，可根据实际情况自动进行扩容。

length、visit、clear操作都是O(1)的时间复杂度。

2.1.insert操作

如下图所示：

涉及到n-i个元素的移动，时间复杂度为O(N)

2.2.remove操作

如下图所示：

涉及到n-i个数据的移动，时间复杂度为O(N)

2.3.顺序表适用场景

顺序表优点：无需为维护结点间的逻辑关系而增加额外的存储空间，可随机访问表中任意结点。

顺序表缺点：顺序表在插入和删除时需要移动大量的数据，性能不太理想；必须预先为线性表准备存储空间，当length小于maxSize时，有部分空间（maxSize-length）被浪费。

因此，顺序表适合静态场景、且经常做定位访问。

3.线性表链表实现

用链接方式存储的线性表称为链表。

链表有两种形态

3.1.单链表

每个节点仅保存指向直接后继节点的指针。

简单单链表如下图所示：

3.1.1.insert操作

如下图所示：

无需迁移结点

3.1.2.remove操作

如下图所示：

无需迁移结点

3.1.3.单循环链表

如下图所示：

3.2.双链表

每个节点既保存指向直接后继结点的指针，又保存指向直接前驱结点的指针。

简单双链表如下图所示：

3.2.1.insert操作

如下图所示：

3.2.2.remove操作

如下图所示：

3.2.3.双循环链表

如下图所示：

3.3.链表适合场景

当指针已经定位到需要insert或remove的前一个结点后，insert和remove都只需要常量的时间，时间复杂度为O(1)。