一篇文章搞懂 数据结构中的 线性表存储方式（顺序表 与 链表）
我们知道：数据结构是计算机存储和组织数据的方式。选择不同的数据结构来处理数据，可以在不同的场景发挥很棒的效率。
数据结构从逻辑层面上分为
线性结构和非线性结构。
线性结构：顾名思义，就是数据连成线一样存储。
非线性结构：分为 树 和 图，树与图的区别就是：树是没有环路的，从大的意义来看，图是包含树的，即没有环路的图就是树。
线性表
线性表是线性结构的基本表现。
线性表有两种存储方式：
顺序表链表。下面分别来看这两种存储方式：
顺序表顺序表 是 开辟连续的空间（如一维数组），顺次把每一个元素存进来。
链表链表就是 每一个数据存储单元有两部分 一是存数据的地方，另一个是存指针的地方。
在实际的存储位置上，链表中相邻的AB，在实际位置可能距离很远。
为什么会有链表呢？可以从这角度入手：在磁盘中，空闲的存储空间有极大可能不是连续的，如果采用顺序表的存储方式，那么就只能存很多组非常小的数据。
而采用链表时，可以把这些不连续的空闲空间利用起来存储一组数据。
链表又分为单链表、循环链表和双向链表。它们之间的主要区别就是指针。单链表只有一个指针，指向它的下一个元素的地址。（就是说单链表只可以从前往后遍历）
双向链表有两个指针，头指针指向上一个元素的地址，尾指针指向下一个元素的地址（既可以从前往后也可以从后往前遍历）
循环链表更多的是指最后一个元素的指针指向了第一个元素的地址（既可以是单链表也可以是双链表）。
顺序表的操作
顺序表的操作很简单。
比如一维数组，每个元素都有一个对应的下标，下标相邻的元素在顺序表中就是相邻的，存储空间的实际位置也是相邻的。
顺序表的空间性能
存储密度：就是说存储的数据的数量 / 存储单元的数量 , 顺序表的存储密度为 1 ，每一个空间都用来存数据。容量分配：既空间是动态分配的还是静态的，顺序表在存储前就需要确定需要的空间大小，是静态分配空间的。顺序表的时间性能
查找（只知道内容，不知道下标叫查找）：一般来说顺序表查找一个元素与链表查找一个元素是相同的时间复杂度，但在数据有序的情况下，顺序表可以使用二分查找大大优化时间性能，但链式表不能使用二分查找。读取一个已知位置的元素：当知道一个要查找的元素的下标时，可以直接通过下标访问。时间复杂度是O（1）.插入操作：如果要插入一个元素到最后一个位置，那是最好的情况直接插入即可，时间复杂度为O(1)，但如果要插入到第一个位置，是最坏的情况，需要把从第一个位置到最后一个位置的元素先依次往后挪一个位置，再插入，这时的时间复杂度是O(n)。删除操作：与插入操作类似，删除最后一个位置的元素为O(1)，删除第一个位置的元素，需要把第二到最后位置的元素依次往前挪一位，为O(n - 1)（也属于O（n）的范围）。链表的操作
单链表的删除操作 : 待删除元素为B, B的上一个元素是A，B的下一个元素是C。很简单， 找到A元素 ， 把A元素的指针指向C的地址（原来是指向B的地址）。如果B是第一个元素，那么把 head 指针指向 C 就可以了。
单链表的插入操作：如果要把B插入到A元素、C元素中间第一步，把B的指针 指向 A的指针指向的地址（也就是B的指针指向C，但这是一个技巧，只需要找到A就可以，不需要再去找C）第二步，把A的指针指向B（如果用上面的技巧时，又把这两个顺序搞反，会出现B指向B的问题）
双向链表的删除操作 : 待删除元素为B, B的上一个元素是A，B的下一个元素是C。与单向链表的操作类似很简单， 找到A元素 ， 把A元素的尾指针指向C的地址，把C的头指针指向A就可以了。如果B是第一个元素，那么把 head 指针指向 C ，C的头指针指向空就可以了。
单链表的插入操作：如果要把B插入到A元素、C元素中间稍微复杂一点第一步，把C的头指针指向B，把B的尾指针指向C。（此时的C可以用A的尾指针指向的元素来代替）第二步，把A的尾指针指向B，B的头指针指向A。
链表的空间性能
存储密度：因为链表的每一个数据都最少需要有两部分空间，存数据与存指针，所以链表的存储密度是小于 1 的。容量分配：从前面我们可以知道，链表是不需要先声明一大段空间的,可以随时需要用的时候，随时声明一块空间，是动态的。链表的时间性能
查找（只知道数据内容）：即使有序，也不能使用二分查找来加快查找效率。读取一个元素：链表不能直接通过下标访问，必须从头开始一个个去找，直到找到需要的元素，最好的情况是需要查找的元素在第一个位置，时间复杂度为O(1)，但最坏的情况是最后一个元素，时间复杂度为O(n)总结：
链式存储中每个数据需要有多余的存储空间来存放指针，顺序存储中所有空间都没有浪费。
链式存储可以动态分配空间，而顺序存储只能静态分配空间。
顺序存储在读取运算中优于链式存储。
但在插入删除运算中链式存储的速度更优。