线性表
1.线性表定义
线性表：线性表是拥有n个元素的有限序列。
线性表特性：1.线性表存在唯一一个称为第一个的元素。2.线性表存在唯一一个称为最后一个的元素。3.除了第一个元素之外每个元素都有唯一前驱。4.除了最后一个元素之外，每个元素都有唯一后继。
线性表按存储类型：
-
顺序存储：用一组地址连续的存储单元依次存储数据。
- 顺序表
-
链式存储：用一组地址任意的存储单元存储数据。
- 单链表
- 头插法：从链表头不断插入数据，是逆向构建的过程，输入顺序与生成链表的顺序是相反的。
- 尾插法：次序相同。
- 节点插入操作：单链表的插入通常采用的是尾插法
- 循环链表
- 双向链表
- 静态链表（使用一维数组实现的）
- 单链表
关联知识：ArrayList和LinkedList的区别
- ArrayList的数据结构是动态数组，而LinkedList的数据结构是链表。
- ArrayList在内存中是顺序存储的，支持随机读取，适用于查询较多的场景；LinkedList在内存中是随机存储的，得从头遍历所有查询效率较低，适用于增删较多的场景。
- 同时由于链表的节点带有指针域，因此存储空间上的花销比顺序存储更大，存储密度不够大。
- ArrayList数组在必要时会增长，但数组从不被垃圾回收，列表本身被摧毁前其元素不会被垃圾回收，LinkedList当元素被移除时候会缩小，未使用的节点会被垃圾回收。
Tips：
- ArrayList的get方法中加入了数组越界的判断，所以set的时候调用get方法隐式地对越界进行了判断。
- ArrayList的remove方法下标是从数组末尾开始的，方便移除末尾元素。
- ArrayList的add（双参）方法是先调用add单参方法，然后从末尾开始依次将a[i]=a[i-1]，前一个数赋值给后面一个数，直到指定的index为止。
