线性表概念
List：由零个或多个数据元素组成的有限序列
1，元素之间是有序的
2，第一个元素无前驱，最后的元素无后驱，其他元素有且只有一个前驱和后驱
3，元素个数可以为零，且数量有限
抽象数据类型
数据类型：
一组性质相同的值的集合以及定义在此集合上的一个操作的总称
可分为：
原子类型，不可再分解的基本类型，如整型，浮点型，字符型
结构类型，由原子类型组合而成的可分解的类型抽象：
抽取事物的特征和其本质，忽略掉非本质的细节，对具体事物进行概括，它是一种思考问题的方式，所以，我们对数据类型进行抽象，就有了我们提到的抽象数据类型抽象数据类型 ADT -- Abstract Data Type：
一个数据模型以及定义在该模型上的一组操作，其数据类型的定义取决于它代表的逻辑特性（数学抽象特性），与其在计算机内部的表示和实现无关，比如1+1=2的操作，在不同的CPU上处理可能不一样，但是其数学特性是一致的，对于人来说，它们是相同的
我们将讨论宏观的问题，它与具体的某种编程语言无关
线性表的抽象数据类型
符合线性表的定义的数据结构 + 定义在数据结构上的行为
---JS和C#上都有叫数组的定义，都有对线性表的实现，C#中的Array，大小固定，元素类型一致，而JS的Array则相当于C#的List
---相关操作可能有：获取线性表的长度、增删改查元素、根据下标插入，还要有异常的判断和抛出；
线性表的顺序存储结构
物理上占用的一块连续的内存，很多语言中的的Array，它描述了长度，起始位置等内容，所以线性表的顺序存储需要满足的三个属性：1，起始位置 2，最大容量 3，当前长度，如果某语言支持容量扩容，必然伴随检测内存块的检查和复制移动删除等操作，消耗性能；
适合读取和存储数据，而插入 / 删除需要移动大量的元素，复杂度为O(n)，所以插入最好是开始或者结尾的位置
同时在初始化顺序线性表结构时，由于连续内存，这样会加大内存碎片的产生
实际项目中，在无法考虑该结构的大小的时候，不应该使用顺序线性表【或者采用预留空间的方式，但也是饮鸠止渴，设计时，这是不推荐的】
所以，需求的场景需要某个新的结构来处理这个顺序问题，so，出现了线性表的链式存储
线性表的链式存储
物理上占用的可能连续的内存，每个元素同顺序存储一样，但不同的是，元素还需要带有后续元素的信息，当然，最后的元素是指向null的；
而链表最常见的是单链表，也就是头指针，头结点，再就是首元素....直到指向Null，在链式存储里，当我们要查找元素时，不得不从第一个开始查找，而删除和插入则不再需要大量的转移元素
当两种链表结合使用的时候，会大大提高性能，比如最常见的比喻-手机通讯录，将名字的首字母作为顺序存储【提供快速查询，不具备删除的功能】，而元素内容为链表【具有添加删除的功能】；
网友评论