线性表
顺序线性表
顺序线性表：使用一段连续的地址存储单元放置线性表的数据元素。
举个例子：数组。
顺序线性表的优缺点：
优点：
- 可以快速获取下标的数据元素，时间复杂度为O(1)
- 逻辑关系是一对一的关系，连续存储单元足以储存，不需要增加额外的存储空间
缺点：
- 插入和删除操作需要移动大量的元素，时间复杂度为O(n)
- 线性表的存储空间大小难以确定，并且不好扩展
- 造成存储空间碎片
链式线性表
链式线性表：线性表的数据元素可以存储在随意的存储单元，每一个节点不仅仅包括数据元素还有一个指向下一个节点的指针（基本的单链表）。
链式（单链表）和顺序线性表优缺点对比：
存储分配方式：
- 顺序 -> 一段地址连续的存储空间
- 链式 -> 任意地址存储空间
时间性能：
- 查找
顺序 -> O(1)
链式 -> O(n) - 插入和删除
顺序 -> O(n)
链式 -> 寻找相应的节点，时间复杂度为O(n)，然后，插入和删除为O(1)
空间性能：
- 顺序 -> 需要提前分配存储空间，分配大了，浪费空间，分配小了，容易发生上溢
- 链式 -> 不需要提前分配空间，只要有存储空间分配就行，数据元素个数只受可分配存储空间大小的限制