前言

线性结构虽然有“线性”二字，但是大家别和数学中的线性关系关联起来。在《数据结构与算法》中的解释为：
线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。
线性表是最简单、最基本，也是最常用的线性结构。线性表有两种存储方法：顺序存储和链式存储。

ps：因为试了很多次上传图片都失败了，所以只能用 md 文字/表格来代替图片展示它们的数据结构了。

顺序表

顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。由于这种存储特性使得顺序表读取速度是非常快的。
看完这些特性是不是很快想到了数组呢？但是顺序表并不等于数组，数组只是顺序表的一种实现。除了数据，同样可以使用链表来实现顺序表，所以别搞错了哦。

如下表格，数据在物理存储位置是相邻的，一次IO的读取就非常方便，而且可以通过元素序号（物理地址）快速找到某一个元素（随机访问）。因此，顺序表读取数据的平均时间复杂度是O(1)。

在添加删除数据方面，顺序表就比较麻烦了。比如我要在 data2 前面插入一个 data4，那么我首先需要将 data2 和 data3 向后移动1格，再把 data4 放在 data2 原来的位置上（如果之前只有3格存储空间的话，那么还需要开辟一个足够大的存储空间）。因此，顺序表操作数据的平均时间复杂度是O(n)。

链表

与顺序表不同的是链表不需要一个连续的内存空间，它只是通过逻辑关系体现了数据元素间的线性结构。这种逻辑关系使得这些数据元素看起来就像是“链”一样。这种存储方式叫链式存储。

单链表

1. Node A -> 2. Node B -> 3. Node C -> null

循环链表

1. Node A -> 2. Node B -> 3. Node C
^                                  |
|__________________________________|

双向链表

NULL <-- [A:1] <--> [B:2] <--> [C:3] --> NULL

双向循环链表

<--> [A:1] <--> [B:2] <--> [C:3] <-->
|                                   |
|___________________________________|

因为数据的关系只是逻辑上的关系，所以没法随机访问。如果要找查某个元素，就只能顺着指针挨个往下走直到找到目标。因此，链表读取数据的平均时间复杂度是O(n)。
在添加删除数据方面，用“在单链表的 data2 前面插入一个 data4”说明。我只需要将 data1 指向 data2 的指针修改指向 data4，再将 data4 的指针修改指向 data2即可（其他类型的链表也是修改指针即可，这里有个术语叫前继节点，后继节点，大家可以自行了解。我想尽量不用术语，而用白话来解释）。因此，顺序表操作数据的平均时间复杂度是O(1)。

比较两种存储方式