java-arrayList和linkedList区别

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