数组和列表很相似,都是有序的元素集合。他们之间的特点列在了下面:
数组 array
- 数组在内存中,数组是一块连续的区域。 这就要求在物理上这一片空间是连续的,每个元素都有指定的索引
index
指向内存地址,因此查询的时候,可根据index
快速找到对应地址存储的信息,使得数组查询速度快。 - 数组在插入数据时,这个位置后面的数据在内存中都要向后移。在删除数据时,这个数据后面的数据都要往前移动,这就导致了数组在插入数据和删除数据效率低。
- 数组需要预留空间,在使用前要先申请占内存的大小,可能会浪费内存空间,这就不利于扩展,数组定义的空间不够时要重新定义数组。
链表 list
- 链表在内存中可以存在任何地方,不要求连续。每一个数据都保存了下一个数据的内存地址,通过这个地址找到下一个数据。因为不具有随机访问性,所以访问某个位置的数据都要从第一个数据开始访问,然后根据第一个数据保存的下一个数据的地址找到第二个数据,以此类推。这就导致链表查询是效率很低.
- 链表因为不需要在内存中连续,所以增加数据和删除数据很容易。
- 链表不指定大小,扩展方便。链表大小不用定义,数据随意增删。