ArrayList和LinkedList的效率对比
2017-10-03 本文已影响0人
阿哲正在努力
前言
List相信大家都使用得很多，其中ArrayList和LinkedList是使用最多的2个，本文将从源码角度解读2者的异同，效率和使用场景。如有疏忽之处，还请多指教。
正文
存储结构
- LinkedList是靠一个名为Node的数据结构来存储数据和前后元素的指针，和双向链表类似。first和last分别存储了第一个和最后一个元素
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
其中item存储了实际的元素数据，next是指向了下一个元素，prev指向了前一个元素
- 而ArrayList直接通过
transient Object[] elementData一个Object的数组存储数据
插入
- ArrayList在插入之前需要通过ensureCapacityInternal方法先计算下加入一个元素后，elementData数组的大小和当前所需要的大小，若大于于当前数组的大小，则需要进行resize和arrayCopy操作。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
resize和arrayCopy主要通过下面的grow方法执行的
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
一般情况下，ArrayList的插入操作是O(1)的时间复杂度，但是当需要resize的时候为O(n)；类似，add(int index, E element)的时间复杂度一般是O(n/2)，需要相应挪动插入的位置之后的元素。
- LinkedList的插入操作即在链表后加一个元素，先创建一个Node，当前插入的元素的prev指向last Node，将last赋值为当前插入Node。如果插入前的last不为null，则将last Node的next指向当前插入的元素；反之则将first也赋值为当前插入的Node（即空LinkedList插入元素后，last和first都指向同一个元素）
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList的插入操作的时间复杂度是O(1)；相应的add(int index, E element)的一般时间复杂度是O(n/4)，从链表前后同时搜索，如果index=linkedlist.size()/2，那么是最坏情况，为O(n/2)
取元素
- ArrayList直接根据数组下标获取相应的元素，所以时间复杂度为O(1)，这也是ArrayList的最大的好处
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
- 而LinkedList需要从第一个或最后一个Node往中间遍历，所以其时间复杂度和
add(int index, E element)类似，一般时间复杂度是O(n/4)，最坏为O(n/2)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int 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;
}
}
删除
-
当删除某个元素时
remove(int index)，ArrayList需要进行resize和arrayCopy操作，所以时间复杂度也为O(n/2)。只有当删除的是最后一个元素时，不用进行上述操作。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- LinkedList删除操作和取元素的时间复杂度一样，因为也是要先通过node方法来找到要被删除的元素，再进行改变其前后元素的prev和next指针，所以其时间复杂度是O(n/4)，最坏为O(n/2)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Iterator
- 使用Iterator迭代器循环时，可以进行add和remove操作。
List<String> listA = new ArrayList<>();
//List<String> listB = new LinkedList<>();
ListIterator<String> iteratorA = listA.listIterator();
while (iteratorA.hasNext()) {
String temp = iteratorA.next();
// iteratorA.add("some string");iteratorA.remove()
}
System.out.println(listA.toString());
- ArrayList在迭代遍历时，add和remove操作的时间复杂度都为O(n/2)，因为其需要将操作的元素之后的所有元素进行数组移位操作，即resize和arrayCopy
- LinkedList在迭代遍历时，add和remove操作的时间复杂度都为O(1)，这也是LinkedList的主要优势
总结
- ArrayList的优势在于随机快速读取，其直接在末尾插入元素的效率也很高。唯一需要注意的是，其resize的时候，需要一定的开销。所以如果你提前能预估ArrayList的大小，你可以在实例化时，给他赋一个initialCapacity，可以减小resize的次数。
- LinkedList的优势在于利用Iterator迭代器循环时，其插入和删除的效率都是最高的。
- 在存储空间上，LinkedList相比ArrayList的每个元素都有更多的开销，因为还存储了指向下一个和前一个元素的指针。所以如果你的list很大的话，这一点也需要考虑进去。
