java-arrayList和linkedList区别

2018-08-13 本文已影响44人一个喜欢烧砖的人

arrayList和linkedList的相同点

都是最终继承于抽象类 abstractList,anstractCollection,接口 list

arrayList和linkedList的不同点

父类稍加不同
arraylist <--- abstractLIst < --- collection
linkedList <--- abstractSquentialList < ---abstractList <--- collection
底层数据存储不同
arrayList是以数组储存数据的
linkedList是以循环双向链表存储数据的

内部结构不同
添加元素
1、添加尾部元素
arraylist:
```
*/
  public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
  }
```
从源码中可以看出只要add 都会走这个方法，arryalist的add的性能取决于ensureCapacityInternal方法。
如果当前容量足够，则添加到数组末尾（add效率特别高），如果当前容量不足，则就需进行扩容，扩容过程中会进行大量的复制操作，每次扩容都会扩到当前的1.5倍
linkedList:

   * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**

而linkedlist因为使用了链表结构，因此不需要维护容量大小
总结：linkedList 使用了链表，不需要扩容，所以不存在添加数据是还要存在扩容是否复制数据的问题，所以性能存在优势，但是正因为是链表，所以每次添加都需创建一个entry对象，对性能有一定的影响

2、任意位置添加元素
arrayList:

    * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

arrayList是基于数组实现的，所以每次在一个位置添加元素之后，之后的数据都会往后移动一个位置（需要重新排列），添加的元素越往前，消耗越大（重新排列的数据越多）；
linkedList：
因为linkedList是链表结构，中间添加元素和尾部添加元素的开销是一样的

     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    /**

删除元素
arrayList:
arrayList的删除元素和添加元素是雷同的，如果在中间删除元素之后，后面的元素都会向前移动位置，如果在末尾，就不存在；
linkedList:
linkedList的删除元素很快，但是查找元素位置很低效（如果要删除位置处于list的前半段，则从前往后找，如果其位置处于后半段，则从后往前找，如果数据量不大，会很高效，如果数据量很大，且数据如果在中间的话几乎遍历了半个list，效率很低）
修改元素
对于set修改元素，arrayList的效率要高于linkedList，因为linkedList要一种指针
查找元素
对于get查找元素，arrayList的效率要高于linkedList，因为linkedList要一种指针
扩容机制
因为arrayList是内部基于数组的，所以初始化设置一个合理的大小对性能有很大的提升
eg:现以构造一个拥有100万元素的List为例，当使用默认初始化大小时，其消耗的相对时间为125ms左右，当直接制定数组大小为100万时，构造相同的ArrayList仅相对耗时16ms。
遍历列表
jdk 1.5之后都有三种遍历
偷个图展示哈把

image.png
总结
ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

所以，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作，最好选择LinkedList

java-arrayList和linkedList区别

arrayList和linkedList的相同点

arrayList和linkedList的不同点

猜你喜欢

热点阅读