数据结构之线性表
2018 algorithm线性表(Linear List)是一种线性结构。线性表是由 n(n ≥ 0)个数据元素的有限序列。
非空线性表的结构特点
- 存在一个唯一没有前驱的数据元素(头元素)
- 存在一个唯一没有后驱的数据元素(尾元素)
- 除了头元素，尾元素，每个元素的均有一个直接前驱和一个直接后继的数据元素。
线性表的存储结构
- 顺序存储 - 顺序表
- 数组
- 链式存储 - 链表
- 单链表
- 双链表
- 循环链表
- 静态链表
顺序表(Sequenatial list)
顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。
优点：可以随机存取表中的元素。缺点：插入和删除操作需要移动元素。
数组与链表的对比
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
链表简单易用，在实现上使用的是连续内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能申请一个更大的内存空间，把原数组拷贝进去。链表本身没有大小的限制，支持动态扩容。