数组和链表的区别
定义
数组的定义
- 数组是一组具有相同数据类型的变量的集合，这些变量称之为集合的元素
- 每个元素都有一个编号，称之为下标，可以通过下标来区别并访问数组元素，数组元素的个数叫做数据的长度
链表的定义
- 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
- 链表的特性是在中间任意位置插入和删除元素都非常快，不需要移动其它元素
- 对于单向链表而言，链表中的每一个元素都要保存一个指向下一个元素的指针
- 对于双向链表而言，链表中的每个元素既要保存指向下一个元素的指针，又要保存指向上一个元素的指针
- 对于双向循环链表而言，链表中的最后一个元素保存一个指向第一个元素的指针
区别
| 比较项 | 数组 | 链表 |
|---|---|---|
| 逻辑结构 | （1）数组在内存中连续； （2）使用数组之前，必须事先固定数组长度，不支持动态改变数组大小； （3）数组元素增加时，有可能会数组越界； （4） 数组元素减少时，会造成内存浪费； （5）数组增删时需要移动其它元素 | （1）链表采用动态内存分配的方式，在内存中不连续 （2）支持动态增加或者删除元素 （3）需要时可以使用 malloc 或者 new 来申请内存，不用时使用 free 或者 delete 来释放内存 |
| 内存结构 | 数组从栈上分配内存，使用方便，但是自由度小 | 链表从堆上分配内存，自由度大，但是要注意内存泄漏 |
| 访问效率 | 数组在内存中顺序存储，可通过下标访问，访问效率高 | 链表访问效率低，如果想要访问某个元素，需要从头遍历 |
| 越界问题 | 数组的大小是固定的，所以存在访问越界的风险 | 只要可以申请得到链表空间，链表就无越界风险 |
使用场景
数组(顺序表)和链表各有短长，在实际应用中，应该具体问题具体分析，通常有以下方面的考虑
| 比较项 | 数组使用场景 | 链表使用场景 |
|---|---|---|
| 空间 | 数组的存储空间是栈上分配的，存储密度大，当要求存储的大小变化不大时，且可以事先确定大小，宜采用数组存储数据 | 链表的存储空间是堆上动态申请的，当要求存储的长度变化较大时，且事先无法估量数据规模，宜采用链表存储 |
| 时间 | 数组访问效率高。当线性表的操作主要是进行查找，很少插入和删除时，宜采用数组结构 | 链表插入、删除效率高，当线性表要求频繁插入和删除时，宜采用链表结构 |