许少提到过,就看一下知识点
数组和链表是两种基本的数据结构,在内存存储上表现不一样
链表中各结点在内存中的存放位置是任意的
区别
- 数组元素个数是固定的,而组成链表的结点个数可按需要增减
- 数组元素的存储单位在数组定义时候分配,链表结点的存储单位在程序执行时候动态向系统申请
- 数组的元素顺序关系由元素在数组中的位置[下标]确定,链表中的结点顺序关系由结点所包含的指针来体现
- 对于不是固定长度的列表,用可能最大长度的数组来描述,会浪费许多内存空间
- 对于元素的插入,删除操作非常频繁的列表处理场合,用数组表示列表也是不好的;若用链表实现,会是程序结构清晰,处理的方法也比较简便
数组的特点
- 在内存中,数组是一个连续的区域
- 数组需要预留空间,在使用前要先申请占内存的大小,可能会浪费内存空间
- 插入或者删除数据效率低,插入数据时候,这个位置后面的数据在内存中都要向后移
- 随机读取效率很高,因为数据是连续的,知道每一个数据的内存地址,可以直接找到给定地址的数据
- 并不利于扩展,数组定义的空间不够时候要重新定义数组
优缺点
- 随机性访问强
- 查找速度快
- 插入删除效率低
- 可能浪费内存空间
- 内存空间要求高,必须又足够的连续的内存空间
- 数组大小固定,不能动态拓展
链表的特点
- 在内存中可以存在任何地方,不要求连续
- 每一个数据都保存了下一个数据的内存地址,通过这个地址找到下一个数据
- 增加或者删除数据很容易
- 查找数据效率低
- 不指定大小,扩展方便,链表大小不用定义,数据随意删除
优缺点
- 插入删除速度快
- 内存利用率高,不会浪费内存
- 大小没有固定,拓展很灵活
- 不能随机查找,必须从第一个开始遍历,查找效率低