今天有群里一个哥儿问面试官问他ArrayList和LinkedList区别,和适用场景,仔细想了一下如果自己去面试自己应该会从下面这几个方面去回答一下
1:ArrayList和ListedList都是list的实现类(其实还有Vector和它的子类stack(同步效率底很少使用了)),
ArrayList和LinkedList都不是线程安全的,而vector是线程安全的这个算是两者的相同之处吧
2:底层方面来说,ArrayList是用动态数组来实现的,LinkList是用链表来实现的
3:对于随机访问get()和set()方法-(相当于改查),ArrayList的效率要比linkList的效率好一点(linkList要移动指针啦,这个老铁们应该理解吧).
4:对于add()和remove()方法-(相当于增删),群里好多哥们说linkList的效率要比ArraList的效率好,应为数组要移动元素吗,但这个时候有个大神说这个是不一定的,当插入的数据量(数组的容量)小的时候,linkList的效率是比ArrayList效率好,但容量较大,插入的位置靠后,这个就ArrayList要比linkLit要好,接下来一阵吹水,多说无益,还是要自己看源码
二:看源码
2.1:我们在Eclipse中打开下ArrayList源码(搜索下get关键字,剩下的方法你会发现是连这的)
//随机访问查询调用这个方法
public E get(int index) {
//判断index是否越界
rangeCheck(index);
return elementData(index);
}
//修改调用
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//增加
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//其实add方法增加最耗时间的在这,我们需要index后面的元素往后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//然后在index处插入元素
elementData[index] = element;
size++;
}
//删除
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 删除也是同样的道理,这里我就不多比比了(覆盖index出元素位置,多出的一位删掉)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
2.2: 我们在打开下LinkedList源码(搜索下get关键字,很巧你会发现也是连这的)
//查
public E get(int index) {
checkElementIndex(index);
//查的时候这个玩意最费时间,我们看下node方法点进去.
return node(index).item;
}
//修改
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//增
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//删
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//查找第index元素,我们通过for循环遍历,(java开发人员牛逼的优化了一下,看if)
Node<E> node(int index) {
// assert isElementIndex(index);
//小于1/2时候,从头开始找,否者从尾(不得不说很牛逼,
//但还是查改的时候不比ArrayList快,人家直接是直接返回index元素)
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//增加的时候我们遍历indx的位置然后添加,问题就出现在这,看是遍历更消耗时间,还是ArraLIst更消耗时间了
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
三:给个验证例子吧(源码说是这个理,但实践是检验真理的唯一标准)
package com.vvut;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Test {
static List<Integer> array=new ArrayList<Integer>();
static List<Integer> linked=new LinkedList<Integer>();
public static void main(String[] args) {
//首先分别给两者插入5000条数据
for(int i=0;i<5000;i++){
array.add(i);
linked.add(i);
}
//获得两者随机访问的时间
System.out.println("array time:"+getTime(array));
System.out.println("linked time:"+getTime(linked));
//获得两者插入数据的时间
System.out.println("array insert time:"+insertTime(array));
System.out.println("linked insert time:"+insertTime(linked));
}
public static long getTime(List<Integer> list){
long time=System.currentTimeMillis();
for(int i = 0; i < 5000; i++){
//进行查找。若数组中存在要查找的元素，则返回改地址,若不存在，则返回比查找元素小的数组元素的地址加一个负号。(从1开始)
int index = Collections.binarySearch(list, list.get(i));
if(index != i){
System.out.println("ERROR!");
}
}
return System.currentTimeMillis()-time;
}
//插入数据
public static long insertTime(List<Integer> list){
/*
* 插入的数据量和插入的位置是决定两者性能的主要方面，
* 我们可以通过修改这两个数据，来测试两者的性能
*/
long num = 5000; //表示要插入的数据量
int index=1000;//
//int index = 5000; //表示从哪个位置插入 2/1
//array insert time:56
// linked insert time:125
long time=System.currentTimeMillis();
for(int i = 1; i < num; i++){
list.add(index, i);
}
return System.currentTimeMillis()-time;
}
}
三: 结果截图
3.1 当插入元素位置很前面的时候LinkedList比ArraList牛逼
3.2:当插入元素位置1/5的时候,两个都差不多,
3.3: 当插入元素位置最后的时候,ArrayList翻身农奴把歌唱啦,比LinkList牛逼
四:结果分析:
我们发现当插的位置越来越后的时候,Linklist越来越差,当时候就这样给面试官说,当插入的数据在容量靠前面的时候.linkedList牛逼(牛逼这个词到时候不说,我们谈效率,显的高雅),1/5,两个货都一样,插入位置后面的时候,ArrayList牛逼,我们在平常使用的时候,用ArrayList多一点(这个看具体的情况)