8

ArrayList和LinkedList的效率对比

 2 years ago
source link: http://neoyeelf.github.io/2017/10/03/ArrayList%E5%92%8CLinkedList%E7%9A%84%E6%95%88%E7%8E%87%E5%AF%B9%E6%AF%94/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

ArrayList和LinkedList的效率对比

2017-10-03

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;
    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很大的话，这一点也需要考虑进去。

上一篇：利用docker-compose快速部署php-fpm+nginx环境

下一篇：API设计和代码结构组织心得


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK