问题13:数组和链表的区别

数组:是将元素在内存中连续存储的;它的优点:因为数据是连续存储的,内存地址连续,所以在查找数据的时候效率比较高;它的缺点:在存储之前,我们需要申请一块连续的内存空间,并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的,当数据两比较大的时候,有可能会出现越界的情况,数据比较小的时候,又有可能会浪费掉内存空间。在改变数据个数时,增加、插入、删除数据效率比较低。

链表:是动态申请内存空间,不需要像数组需要提前申请好内存的大小,链表只需在用的时候申请就可以,根据需要来动态申请或者删除内存空间,对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置,通过应用来关联数据(就是通过存在元素的指针来联系)。

数组和链表就拿增加数据来说,数组中增加一个元素,需要移动大量的元素,在内存中空出一个元素的空间,然后将增加的元素放到空出的空间中;而链表就是将链表中最后的一个元素的指针指向新增的元素,在指出新增元素是尾元素就好了。

数组的优点:

随机访问性强

查找速度快

数组的缺点:

插入和删除效率低

可能浪费内存

内存空间要求高,必须有足够的连续内存空间。

数组大小固定,不能动态拓展

链表的优点:

插入删除速度快

内存利用率高,不会浪费内存

大小没有固定,拓展很灵活。

链表的缺点

不能随机查找,必须从第一个开始遍历,查找效率低