ArrayList和LinkedList的区别以及优缺点

ArrayList和LinkedList的区别以及优缺点
(在面试的时候经常会提问,谈一谈以你对ArrayList和LinkedList的区别以及优缺点,今天做一下笔记,方便以后查看,个人理解,不一定正确,若真有错误,请轻喷)

1、ArrayList:

  • ArrayList实现了基于动态数组的数据结构,每个元素在内存中存储地址是连续的,根据下标查询的速度是很快的,向集合元素末尾添加的效率也是非常快的,删除数组中的元素以及向数组中间插入元素的效率就大打折扣了,当在添加的时候,会先去检测数组的长度,如果达到一定的峰值,会对数组进行一个扩容(前数组的1.5倍)
  • ArrayList在调用add方法的时候
- 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++;
    }`

首先会进行一个简短的验证,验证当前传入的数字是否越界,其次再对数组进行一个扩容的检查,扩容等操作,最后会调用arraycopy的方法进行数组的复制(如果向数组中间位置添加元素,则需要移动其他元素的位置),虽然效率也很高,但是和LinkedList还是有差距的。Arraylist删除也需要移动数组,效率较慢。

  • ArrayList在调用get方法的时候
       public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

2、LinkedList:

  • LinkedList底层是双向链表的结构

  • LinkedList则相反,它在插入、删除集合中任何位置的元素所花费的时间都是一样的,但是它根据索引查询一个元素的时候却比较慢。

  • (链表结构)

/**
     * Pointer to first node.
     * Invariant: (first == null  last == null) ||
     *            (first.prev == null  first.item != null)
     */
    transient NodeE first;

    /**
     * Pointer to last node.
     * Invariant: (first == null  last == null) ||
     *            (last.next == null  last.item != null)
     */
    transient NodeE last;

3、总结:

1.ArrayList是实现了基于动态数组的数据结构,LinkedList是基于链表结构。
2.对于随机访问的get和set方法,ArrayList要优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。

最新回复(0)
/jishujzzqwXzRdawRpqbGP4zttqtxNlFMnimdAvsGoa4jxfA_3D4858792
8 简首页