数组和链表是两种基本的数据结构,他们在内存存储上的表现不同,因此也有各自的特色。数组
链表中各结点在内存中的存放位置是任意的。 数据结构
链表与数组的主要区别
(1)数组的元素个数是固定的,而组成链表的结点个数可按须要增减;spa
(2)数组元素的存诸单元在数组定义时分配,链表结点的存储单元在程序执行时动态向系统申请:指针
(3)数组中的元素顺序关系由元素在数组中的位置(即下标)肯定,链表中的结点顺序关系由结点所包含的指针来体现。内存
(4)对于不是固定长度的列表,用可能最大长度的数组来描述,会浪费许多内存空间。效率
(5)对于元素的插人、删除操做很是频繁的列表处理场合,用数组表示列表也是不适宜的。若用链表实现,会使程序结构清晰,处理的方法也较为简便。扩展
例如:在一个列表中间要插人一个新元素,如用数组表示列表,为完成插人工做,插人处以后的所有元素必须向后移动一个位置空出的位置用于存储新元素。遍历
对于在一个列表中删除一个元素状况,为保持数组中元素相对位置连续递增,删除处以后的元素都得向前移一个位置。如用链表实现列表.链表结点的插人或删除操做再也不须要移动结点,只需改变相关的结点中的后继结点指针的值便可,与结点的实际存储位置无关。程序
数组的特色
- 在内存中,数组是一块连续的区域。
- 数组须要预留空间,在使用前要先申请占内存的大小,可能会浪费内存空间。
- 插入数据和删除数据效率低,插入数据时,这个位置后面的数据在内存中都要向后移。
- 随机读取效率很高。由于数组是连续的,知道每个数据的内存地址,能够直接找到给定地址的数据。
- 而且不利于扩展,数组定义的空间不够时要从新定义数组。
链表的特色
- 在内存中能够存在任何地方,不要求连续。
- 每个数据都保存了下一个数据的内存地址,经过这个地址找到下一个数据。 第一我的知道第二我的的座位号,第二我的知道第三我的的座位号……
- 增长数据和删除数据很容易。 再来我的能够随便坐,好比来了我的要作到第三个位置,那他只须要把本身的位置告诉第二我的,而后问第二我的拿到原来第三我的的位置就好了。其余人都不用动。
- 查找数据时效率低,由于不具备随机访问性,因此访问某个位置的数据都要从第一个数据开始访问,而后根据第一个数据保存的下一个数据的地址找到第二个数据,以此类推。 要找到第三我的,必须从第一我的开始问起。
- 不指定大小,扩展方便。链表大小不用定义,数据随意增删。
各自的优缺点
数组的优势
数组的缺点
- 插入和删除效率低
- 可能浪费内存
- 内存空间要求高,必须有足够的连续内存空间。
- 数组大小固定,不能动态拓展
链表的优势
- 插入删除速度快
- 内存利用率高,不会浪费内存
- 大小没有固定,拓展很灵活。
链表的缺点