ArrayList和LinkedList有什么区别
ArrayList查询快!LinkedList增删快!
有的人可能会说ArrayList底层是一个数组,所以查询快,LinkedList底层是一个链表,所以增删快.
这样回答的话当然比第一个更好,但是还是不够!
那么为什么数组查询就快了呢?因为假设数组里面保存的是一组对象,每个对象都有内存大小,例如对象中有一个字段是int类型占用4个字节(只考虑实际数据占用的内存),数组在堆上的内存在数组被创建出来就被确定了是40个字节.如果我们要查找第9个对象,可以通过(9-1)*4=32,从33到36字节就是我们要找的对象.是不是很快呢?而链表却不能做到这样的效率.如上图,我们要找到A4,必须先找到A3,再先找到A2,再先找到A1.这样的查找效率会大大降低.
好了,说了查找,再说说插入,数组的插入也相当的浪费效率,如果要在数组内的某一个位置进行插入,需要先将插入位置的前面复制一份,然后在新的数组后面添加新的元素,最后将旧的数组后半部分添加的新的数组后面,而在链表中插入就变得相当简单了,比如我要在A3和A4中插入B,只需定位到A3的指针和A4的数据即可,将A3的指针指向B的值,将B的指针指向A4的值,B就插入进了链表.