浅析 ArrayList 和 LinkedList 有什么区别

ArrayList 和 LinkedList 有什么区别,是面试官非常喜欢问的一个问题。可能大部分小伙伴和我一样,能回答出“ArrayList 是基于数组实现的,LinkedList 是基于双向链表实现的。”

关于这一点,我之前的文章里也提到过了。但说实话,这样苍白的回答并不能令面试官感到满意,他还想知道的更多。

那假如小伙伴们继续做出下面这样的回答:

“ArrayList 在新增和删除元素时,因为涉及到数组复制,所以效率比 LinkedList 低,而在遍历的时候,ArrayList 的效率要高于 LinkedList。”

面试官会感到满意吗?我只能说,如果面试官比较仁慈的话,他可能会让我们回答下一个问题;否则的话,他会让我们回家等通知,这一等,可能意味着杳无音讯了。

为什么会这样呢?为什么为什么?回答的不对吗?

暴躁的小伙伴请喝口奶茶冷静一下。冷静下来后,请随我来,让我们一起肩并肩、手拉手地深入地研究一下 ArrayList 和 LinkedList 的数据结构、实现原理以及源码,可能神秘的面纱就揭开了。

ArrayList 是如何实现的?

浅析 ArrayList 和 LinkedList 有什么区别

ArrayList 实现了 List 接口,继承了 AbstractList 抽象类,底层是基于数组实现的,并且实现了动态扩容。

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 private static final int DEFAULT_CAPACITY = 10;
 transient Object[] elementData;
 private int size;
}

ArrayList 还实现了 RandomAccess 接口,这是一个标记接口:

public interface RandomAccess {
}

内部是空的,标记“实现了这个接口的类支持快速(通常是固定时间)随机访问”。快速随机访问是什么意思呢?就是说不需要遍历,就可以通过下标(索引)直接访问到内存地址。

public E get(int index) {
 Objects.checkIndex(index, size);
 return elementData(index);
}
E elementData(int index) {
 return (E) elementData[index];
}

ArrayList 还实现了 Cloneable 接口,这表明 ArrayList 是支持拷贝的。ArrayList 内部的确也重写了 Object 类的 clone() 方法。

public Object clone() {
 try {
 ArrayList<?> v = (ArrayList<?>) super.clone();
 v.elementData = http://www.cppcns.com/ruanjian/java/Arrays.copyOf(elementData, size);
 v.modCount = 0;
 return v;
 } catch (CloneNotSupportedException e) {
 // this shouldn't happen, since we are Cloneable
 throw new InternalError(e);
 }
}

ArrayList 还实现了 Serializable 接口,同样是一个标记接口:

public interface Serializable {
}

内部也是空的,标记“实现了这个接口的类支持序列化”。序列化是什么意思呢?Java 的序列化是指,将对象转换成以字节序列的形式来表示,这些字节序中包含了对象的字段和方法。序列化后的对象可以被写到数据库、写到文件,也可用于网络传输。

眼睛雪亮的小伙伴可能会注意到,ArrayList 中的关键字段 elementData 使用了 transient 关键字修饰,这个关键字的作用是,让它修饰的字段不被序列化。

这不前后矛盾吗?一个类既然实现了 Serilizable 接口,肯定是想要被序列化的,对吧?那为什么保存关键数据的 elementData 又不想被序列化呢?

这还得从 “ArrayList 是基于数组实现的”开始说起。大家都知道,数组是定长的,就是说,数组一旦声明了,长度(容量)就是固定的,不能像某些东西一样伸缩自如。这就很麻烦,数组一旦装满了,就不能添加新的元素进来了。

ArrayList 不想像数组这样活着,它想能屈能伸,所以它实现了动态扩容。一旦在添加元素的时候,发现容量用满了 s == elementData.length,就按照原来数组的 1.5 倍(oldCapacity >> 1)进行扩容。扩容之后,再将原有的数组复制到新分配的内存地址上 Arrays.copyOf(elementData, newCapacity)

private void add(E e, Object[] elementData, int s) {
 if (s == elementData.length)
 elementData = http://www.cppcns.com/ruanjian/java/grow();
 elementData[s] = e;
 size = s + 1;
}

private Object[] grow() {
 return grow(size + 1);
}

private Object[] grow(int minCapacity) {
 int oldCapacity = elementData.length;
 if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 int newCapacity = ArraysSupport.newLength(oldCapacity,
  minCapacity - oldCapacity, /* minimum growth */
  oldCapacity >> 1  /* preferred growth */);
 return elementData = Arrays.copyOf(elementData, newCapacity);
 } else {
 return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
 }
}

浅析 ArrayList 和 LinkedList 有什么区别

扫一扫手机访问