专栏首页技术探索ArrayList与LinkedList 源码分析(基于JDK1.7)

ArrayList与LinkedList 源码分析(基于JDK1.7)

List接口

List接口中的方法有很多,但最重要的无非是增删查改,我们从ArrayList与LinkedList的实现上来讨论他们的增删查改性能问题。先列出这几个重要的方法:

public interface List<E> extends Collection<E> {
    boolean add(E e); 
    void add(int index, E element);
    E get(int index);
    E set(int index, E element);
    E remove(int index);
    boolean remove(Object o);
}

ArrayList

ArrayList的默认容量大小是 10

构造函数 ArrayList底层使用的是动态数组,我们常用到的构造方法一般是如下两种:

/**
    * Constructs an empty list with the specified initial capacity.
    *
    * @param  initialCapacity  the initial capacity of the list
    * @throws IllegalArgumentException if the specified initial capacity
    *         is negative
    */
   public ArrayList(int initialCapacity) {
       super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       this.elementData = new Object[initialCapacity];
   }

   /**
    * Constructs an empty list with an initial capacity of ten.
    */
   public ArrayList() {
       super();
       this.elementData = EMPTY_ELEMENTDATA;
   }

从源码可以看出,两者的区别在于初始化数组的长度,前者给定一个空数组,后者若initialCapacity大于0即给定一个initialCapacity大小的数组

add一个元素

/**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e;
       return true;
   }
private void ensureCapacityInternal(int minCapacity) {
       if (elementData == EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }

       ensureExplicitCapacity(minCapacity);
   }
private void ensureExplicitCapacity(int minCapacity) {
     modCount++;

     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }

添加元素时会检测数组大小是否满足条件,不满足会去新建一个更大的数组,把原来数组中的元素都copy过来,可以看出,对于ArrayList的add操作来讲,是比较低效的(当需要扩容时)。 另外还有个public void add(int index, E element)方法,它在指定位置add元素时,需要把指定位置后面的所有元素都往后移动一个位置,所以也是比较低效的。

get一个元素

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

 E elementData(int index) {
        return (E) elementData[index];
    }

可以看到,ArrayList的Get是非常高效的,只要index没有越界,直接从底层数组中返回即可,这也是ArrayList的优势所在。同理 ,ArrayList的Set也很高效,直接往数组中写即可。

remove一个元素

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;
    }

ArrayList在做删除操作时,因为需要把后面的所有元素整体前移来填空,所也也是非常耗资源的。 另外还有个public boolean remove(Object o)方法,这个是做一次遍历查询,然后删除。

LinkedList

构造函数

通过名字就可知道,LinkedList底层使用的是链表的形式去实现的,它的构造函数什么也没干:

public LinkedList() {
   }

add一个元素

public boolean add(E e) {
       linkLast(e);
       return true;
   }

/**
    * Links e as last element.
    */
   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++;
   }

add一个元素就直接把这个元素放到链表的末端即可。但需要注意的是,相对于ArrayList的add方法,LinkedList的add方法并不见得高效,而且当数据量大后还远慢于ArrayList。 同时,LinkedList还是双向链表,所以内部同时保留了transient Node last和transient Node first;的引用。

get一个元素

   public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
 private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

通过查看index更靠近链表的哪一端,决定从哪一端去遍历。LinkedList在查找时需要遍历,所以相对于ArrayList的随机存取来说,会低效一些。

remove一个元素

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

总结

  • ArrayList因为是基于动态数组去实现,在随机存取时,有着良好的性能。而增删时需要扩容,整块移动元素,所以相对较慢。但在数据量很大,顺序添加时是个例外,这种情况下它的性能优于LinkedList。
  • LinkedList因为是基于链表实现,随机增删较快,而存取时需要遍历查询,相对于ArrayList会更慢。 之后会比较下两种实现的迭代器性能。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • zookeeper集群搭建步骤

    日薪月亿
  • 微服务扩展性和高可用-章节2(翻译)

    SLA决定系统是否必须扩展。它们还推动了增长时间表。股票交易系统必须在最低和最高可用性水平内实时扩展。相比之下,电子商务系统可能会在一年中“缓慢”的几个月扩大规...

    日薪月亿
  • 分布式ID生成方法

    优点: (1)简单,使用数据库已有的功能 (2)能够保证唯一性 (3)能够保证递增性 (4)步长固定 缺点: (1)可用性难以保证:数据库常见架构是一主多从+读...

    日薪月亿
  • Apache2为什么会自动加载index.php

    我直接输入域名后,Apache2自动加载了对应目录下的index.php, 这是怎么做到的?

    Jerry Wang
  • 【AlexeyAB DarkNet框架解析】七,YOLOV1损失函数代码详解(detection_layer.c)

    灵魂拷问,你真的懂YOLOV1的损失函数吗?进一步,懂了损失函数,你清楚它的反向求导过程吗?为了解决这俩问题,本文就结合DarkNet中的YOLOV1的损失函数...

    BBuf
  • 在phpstudy集成环境下的nginx服务器下配置url重写

    直接在对应的vhosts.conf配置文件的location / {}中添加以下内容:

    砸漏
  • Python_二维数组

    py3study
  • 封装Python列表实现多下标访问

    class MyArray(object): def __init__(self, values): #values can be of...

    Python小屋屋主
  • nginx 配置目录转发

    server { listen 80; autoindex off; server_name image.imooc.com; ...

    Dar_Alpha
  • lodash源码分析之baseFindIndex中的运算符优先级

    我悟出权力本来就是不讲理的——蟑螂就是海米;也悟出要造反,内心必须强大到足以承受任何后果才行。 ——北岛《城门开》 本文为读 lodash 源码的第十篇,后...

    对角另一面

扫码关注云+社区

领取腾讯云代金券