前言
线性表是数据结构中最基本的一种数据存储方式，深入了解线性表的特性不仅有助于更好地理解复杂数据结构（例如栈、队列等），还能给程序员的日常工作所需的内功大法打下一个基础。本文会从“定义”、“模型类比”、“性能评价”等多个维度对“顺序存储结构”、“链式存储结构”等线性表结构进行循序渐进的阐述，如有错误或描述不清的地方， 欢迎指导。
什么是线性表？
线性表即零个或多个有限元素的有限序列。
- 线性表首先强调的是“有限”，然后是“序列性”，即每个元素从前后关系上来看都有一一对应的关系。
- 十二星座是不是线性表呢？答案是YES，因为从“有限”和“序列性”上来考虑，十二星座的结构是符合要求的。
- 公司的组织架构是不是呢？首先它满足了“有限”特性，但由于整体结构呈“树状”，而非线性，所以它并不是线性表。
线性表结构👇👇👇
非线性表结构👇👇👇
线性表的顺序存储结构
定义
顺序存储结构的顺序二字，是针对物理结构而言的。使用顺序存储结构时, 系统会按照给定的长度在内存中开辟一段固定长度且连续的空间，也因此顺序存储结构存在内存溢出的问题。模型类比
电影院的座位就是一个线性表的顺序存储结构，在建造的时候甲方就是根据给定的设计建造出固定数量的座位。这些座位不仅是有限的，而且是按照固定顺序排序编号的。如果看电影的人数超出了总座位数量，则“内存溢出”。-
插入+删除+查询性能
- 由于内存地址是连续的，在进行查询操作时，只需要根据地址就能马上找到对应元素，因此查询的时间复杂度未O(1)。
-
在进行插入和删除操作时，每操作一个元素，其他相关元素都要移动一下，给即将加入的元素“让位”， 或者“补上”被删除的元素的位置。这个过程很好理解，举个例子，电影院有100个座位，目前有99个观众坐在1号到99号的座位上，突然来了一个傻逼观众，一定要坐到1号的座位上，此时这99个观众都需要向后挪一个座位，才能给这个傻逼让出1号座位，而这个过程的时间负责度为O(n)。删除的操作也是类似，如下图所示。
存储结构的删除操作
线性表的链式存储结构
链式存储结构和顺序刚好相反，它没有固定长度，而且物理空间也是不连续的，因此除非系统的所有内存空间都被用完了， 否则不存在内存溢出问题。
-
单链表定义
单链表由有限结点组成，每个结点由数据域和指针域组成， 数据域用来保存数据，指针域用来指向下一个元素。
单链表 模型类比
很多探宝电影都会有这么一个桥段，主角出现在地点一，得到一些好处，然后又得到提示前往下一个地点，到了下一个地点又得到一些好处，然后又得到提示前往再下一个地点，以此类推直到找到最后的大秘宝，而这个过程中所经过的每一个地点在物理空间上都是不连续的。以单链表来类比，每个地点都是一个结点，主角们得到的好处即数据，得到的提示即指针域，想要获取下一个结点的数据， 只能通过前一个指针域获取。-
插入+删除+查询性能
- 通过前文的类比解释可以得出一个结果，使用单链表时，要进行查询操作，只能一个结点一个结点地找下去，直到找出自己要查询的数据为止，因此单链表的查询操作的时间复杂度为O(n)。
- 而对于插入操作和删除操作，只需要在要插入的位置，重新指定前后结点的指针域的指向即可，因此时间复杂度为O(1)，具体操作如下图所示。
结语
对比顺序存储结构和链式存储结构后的数据操作性能后， 我们会发现两者在时间复杂度上的表现是刚好相反的，由此也可以得出一个简单的结论，对于长度不变且不需要频繁进行插入和删除操作的数据结构，我们应该使用顺序存储结构，而对于长度不确定且需要频繁进行插入和删除操作的数据结构，我们应该优先使用链式存储结构。两者各有利弊，而且有不同的适用场景，应该根据需求选择性地使用。
