前言

今天來(lái)介紹下LinkedList，在集合框架整體框架一章中，我們介紹了List接口，LinkedList與ArrayList一樣實(shí)現(xiàn)List接口，只是ArrayList是List接口的大小可變數(shù)組的實(shí)現(xiàn)，LinkedList是List接口鏈表的實(shí)現(xiàn)?；阪湵韺?shí)現(xiàn)的方式使得LinkedList在插入和刪除時(shí)更優(yōu)于ArrayList，而隨機(jī)訪問(wèn)則比ArrayList遜色些。
構(gòu)造圖如下:
藍(lán)色線條：繼承
綠色線條：接口實(shí)現(xiàn)

正文

LinkedList是基于鏈表結(jié)構(gòu)的一種List，在分析LinkedList源碼前有必要對(duì)鏈表結(jié)構(gòu)進(jìn)行說(shuō)明。

1.鏈表的概念
鏈表是由一系列非連續(xù)的節(jié)點(diǎn)組成的存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)單分下類的話，鏈表又分為單向鏈表和雙向鏈表，而單向/雙向鏈表又可以分為循環(huán)鏈表和非循環(huán)鏈表，下面簡(jiǎn)單就這四種鏈表進(jìn)行圖解說(shuō)明。

1.1.單向鏈表
單向鏈表就是通過(guò)每個(gè)結(jié)點(diǎn)的指針指向下一個(gè)結(jié)點(diǎn)從而鏈接起來(lái)的結(jié)構(gòu)，最后一個(gè)節(jié)點(diǎn)的next指向null。

1.2.單向循環(huán)鏈表
單向循環(huán)鏈表和單向列表的不同是，最后一個(gè)節(jié)點(diǎn)的next不是指向null，而是指向head節(jié)點(diǎn)，形成一個(gè)“環(huán)”。

1.3.雙向鏈表
從名字就可以看出，雙向鏈表是包含兩個(gè)指針的，pre指向前一個(gè)節(jié)點(diǎn)，next指向后一個(gè)節(jié)點(diǎn)，但是第一個(gè)節(jié)點(diǎn)head的pre指向null，最后一個(gè)節(jié)點(diǎn)的tail指向null。

1.4.雙向循環(huán)鏈表
雙向循環(huán)鏈表和雙向鏈表的不同在于，第一個(gè)節(jié)點(diǎn)的pre指向最后一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的next指向第一個(gè)節(jié)點(diǎn)，也形成一個(gè)“環(huán)”。而LinkedList就是基于雙向循環(huán)鏈表設(shè)計(jì)的。

更形象的解釋下就是：雙向循環(huán)鏈表就像一群小孩手牽手圍成一個(gè)圈，第一個(gè)小孩的右手拉著第二個(gè)小孩的左手，第二個(gè)小孩的左手拉著第一個(gè)小孩的右手。。。最后一個(gè)小孩的右手拉著第一個(gè)小孩的左手。

ok，鏈表的概念介紹完了，下面進(jìn)入寫注釋和源碼分析部分，但是在這之前還是要提醒一句，不是啰嗦哦，鏈表操作理解起來(lái)比數(shù)組困難了不少，所以務(wù)必要理解上面的圖解，如果源碼解析過(guò)程中遇到理解困難，請(qǐng)返回來(lái)照?qǐng)D理解。

LinkedList簡(jiǎn)介

LinkedList定義

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向循環(huán)鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。
LinkedList 實(shí)現(xiàn) List 接口，能對(duì)它進(jìn)行隊(duì)列操作。
LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用。
LinkedList 實(shí)現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能克隆。
LinkedList 實(shí)現(xiàn)java.io.Serializable接口，這意味著LinkedList支持序列化，能通過(guò)序列化去傳輸。
LinkedList 是非同步的。

LinkedList屬性

明白了上面的鏈表概念，以及LinkedList是基于雙向循環(huán)鏈表設(shè)計(jì)的，下面在具體來(lái)看看LinkedList的底層的屬性

private transient Entry<E> header = new Entry<E>(null, null, null);
2 private transient int size = 0;

LinkedList中提供了上面兩個(gè)屬性，其中size和ArrayList中一樣用來(lái)計(jì)數(shù)，表示list的元素?cái)?shù)量，而header則是鏈表的頭結(jié)點(diǎn)，Entry則是鏈表的節(jié)點(diǎn)對(duì)象。

private static class Entry<E> {
    E element;  // 當(dāng)前存儲(chǔ)元素
    Entry<E> next;  // 下一個(gè)元素節(jié)點(diǎn)
    Entry<E> previous;  // 上一個(gè)元素節(jié)點(diǎn)
    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

Entry為L(zhǎng)inkedList 的內(nèi)部類，其中定義了當(dāng)前存儲(chǔ)的元素，以及該元素的上一個(gè)元素和下一個(gè)元素。結(jié)合上面雙向鏈表的示意圖很容易看懂。

LinkedList構(gòu)造函數(shù)

/**
* 構(gòu)造一個(gè)空的LinkedList .
*/
public LinkedList() {
    //將header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)都設(shè)置為自身
    header.next = header. previous = header ;
}

/**
* 構(gòu)造一個(gè)包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列
*/
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

需要注意的是空的LinkedList構(gòu)造方法，它將header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)都設(shè)置為自身，這里便說(shuō)明LinkedList 是一個(gè)雙向循環(huán)鏈表，如果只是單存的雙向鏈表而不是循環(huán)鏈表，他的實(shí)現(xiàn)應(yīng)該是這樣的：

public LinkedList() {
    header.next = null;
    header. previous = null;
}

非循環(huán)鏈表的情況應(yīng)該是header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)均為null（參見(jiàn)鏈表圖解）。

API方法摘要

LinkedList源碼解析(基于JDK1.6.0_45)

增加

增加方法的代碼讀起來(lái)比較不容易理解，需要的時(shí)候請(qǐng)結(jié)合鏈表圖解。

/**
 * 將一個(gè)元素添加至list尾部
 */
public boolean add(E e) {
   // 在header前添加元素e，header前就是最后一個(gè)結(jié)點(diǎn)啦，就是在最后一個(gè)結(jié)點(diǎn)的后面添加元素e
   addBefore(e, header);
    return true;
}
/**
 * 在指定位置添加元素
 */
public void add(int index, E element) {
    // 如果index等于list元素個(gè)數(shù)，則在隊(duì)尾添加元素(header之前)，否則在index節(jié)點(diǎn)前添加元素
    addBefore(element, (index== size ? header : entry(index)));
}
 
private Entry<E> addBefore(E e, Entry<E> entry) {
    // 用entry創(chuàng)建一個(gè)要添加的新節(jié)點(diǎn)，next為entry，previous為entry.previous，意思就是新節(jié)點(diǎn)插入entry前面，確定自身的前后引用，
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
     // 下面修改newEntry的前后節(jié)點(diǎn)的引用，確保其鏈表的引用關(guān)系是正確的
    // 將上一個(gè)節(jié)點(diǎn)的next指向自己
    newEntry. previous.next = newEntry;
    // 將下一個(gè)節(jié)點(diǎn)的previous指向自己
    newEntry. next.previous = newEntry;
    // 計(jì)數(shù)+1
     size++;
     modCount++;
     return newEntry;
}

到這里可以發(fā)現(xiàn)一點(diǎn)疑慮，header作為雙向循環(huán)鏈表的頭結(jié)點(diǎn)是不保存數(shù)據(jù)的，也就是說(shuō)hedaer中的element永遠(yuǎn)等于null。

/**
 * 添加一個(gè)集合元素到list中
 */
public boolean addAll(Collection<? extends E> c) {
        // 將集合元素添加到list最后的尾部
    return addAll(size , c);
}

/**
 * 在指定位置添加一個(gè)集合元素到list中
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 越界檢查
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException( "Index: "+index+
                                            ", Size: "+size );
    Object[] a = c.toArray();
    // 要插入元素的個(gè)數(shù)
    int numNew = a.length ;
    if (numNew==0)
        return false;
    modCount++;

    // 找出要插入元素的前后節(jié)點(diǎn)
    // 獲取要插入index位置的下一個(gè)節(jié)點(diǎn)，如果index正好是lsit尾部的位置那么下一個(gè)節(jié)點(diǎn)就是header，否則需要查找index位置的節(jié)點(diǎn)
    Entry<E> successor = (index== size ? header : entry(index));
    // 獲取要插入index位置的上一個(gè)節(jié)點(diǎn)，因?yàn)槭遣迦?，所以上一個(gè)點(diǎn)擊就是未插入前下一個(gè)節(jié)點(diǎn)的上一個(gè)
    Entry<E> predecessor = successor. previous;
    // 循環(huán)插入
    for (int i=0; i<numNew; i++) {
        // 構(gòu)造一個(gè)節(jié)點(diǎn)，確認(rèn)自身的前后引用
        Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
        // 將插入位置上一個(gè)節(jié)點(diǎn)的下一個(gè)元素引用指向當(dāng)前元素（這里不修改下一個(gè)節(jié)點(diǎn)的上一個(gè)元素引用，是因?yàn)橄乱粋€(gè)節(jié)點(diǎn)隨著循環(huán)一直在變）
        predecessor. next = e;
        // 最后修改插入位置的上一個(gè)節(jié)點(diǎn)為自身，這里主要是為了下次遍歷后續(xù)元素插入在當(dāng)前節(jié)點(diǎn)的后面，確保這些元素本身的順序
        predecessor = e;
    }
    // 遍歷完所有元素，最后修改下一個(gè)節(jié)點(diǎn)的上一個(gè)元素引用為遍歷的最后一個(gè)元素
    successor. previous = predecessor;

    // 修改計(jì)數(shù)器
    size += numNew;
    return true;
}

其實(shí)刪除也是一樣的對(duì)不對(duì)？下面看看刪除方法的實(shí)現(xiàn)。

刪除

/**
 * 刪除第一個(gè)匹配的指定元素
 */
public boolean remove(Object o) {
     // 遍歷鏈表找到要被刪除的節(jié)點(diǎn)
    if (o==null) {
        for (Entry<E> e = header .next; e != header; e = e.next ) {
            if (e.element ==null) {
                remove(e);
                return true;
            }
        }
    } else {
        for (Entry<E> e = header .next; e != header; e = e.next ) {
            if (o.equals(e.element )) {
                remove(e);
                return true;
            }
        }
    }
    return false;
}

private E remove(Entry<E> e) {
    if (e == header )
       throw new NoSuchElementException();

   // 被刪除的元素，供返回
    E result = e. element;
   // 下面修正前后對(duì)該節(jié)點(diǎn)的引用
   // 將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
   e. previous.next = e.next;
   // 將該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的previous指向該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
   e. next.previous = e.previous;
   // 修正該節(jié)點(diǎn)自身的前后引用
    e. next = e.previous = null;
   // 將自身置空，讓gc可以盡快回收
    e. element = null;
   // 計(jì)數(shù)器減一
    size--;
    modCount++;
    return result;
}

上面對(duì)于鏈表增加元素總結(jié)了，一句話就是“改變前后的互相指向關(guān)系”，刪除也是同樣的道理，由于節(jié)點(diǎn)被刪除，該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)互相拉一下小手就可以了，注意的是“互相”，不能一廂情愿。

修改

/**
 * 修改指定位置索引位置的元素
 */
public E set( int index, E element) {
    // 查找index位置的節(jié)點(diǎn)
    Entry<E> e = entry(index);
    // 取出該節(jié)點(diǎn)的元素，供返回使用
    E oldVal = e. element;
    // 用新元素替換舊元素
    e. element = element;
    // 返回舊元素
    return oldVal;
}    

set方法看起來(lái)簡(jiǎn)單了很多，只要修改該節(jié)點(diǎn)上的元素就好了，但是不要忽略了這里的entry()方法，重點(diǎn)就是它。

查詢

終于到查詢了，終于發(fā)現(xiàn)了上面經(jīng)常出現(xiàn)的那個(gè)方法entry()根據(jù)index查詢節(jié)點(diǎn)，我們知道數(shù)組是有下標(biāo)的，通過(guò)下標(biāo)操作天然的支持根據(jù)index查詢?cè)?，而鏈表中是沒(méi)有index概念呢，那么怎么樣才能通過(guò)index查詢到對(duì)應(yīng)的元素呢，下面就來(lái)看看LinkedList是怎么實(shí)現(xiàn)的。

/**
 * 查找指定索引位置的元素
 */
public E get( int index) {
    return entry(index).element ;
}

/**
 * 返回指定索引位置的節(jié)點(diǎn)
 */
private Entry<E> entry( int index) {
    // 越界檢查
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException( "Index: "+index+
                                            ", Size: "+size );
    // 取出頭結(jié)點(diǎn)
    Entry<E> e = header;
    // size>>1右移一位代表除以2，這里使用簡(jiǎn)單的二分方法，判斷index與list的中間位置的距離
    if (index < (size >> 1)) {
        // 如果index距離list中間位置較近，則從頭部向后遍歷(next)
        for (int i = 0; i <= index; i++)
            e = e. next;
    } else {
        // 如果index距離list中間位置較遠(yuǎn)，則從頭部向前遍歷(previous)
        for (int i = size; i > index; i--)
            e = e. previous;
    }
    return e;
}

現(xiàn)在知道了，LinkedList是通過(guò)從header開(kāi)始index計(jì)為0，然后一直往下遍歷（next），直到到底index位置。為了優(yōu)化查詢效率，LinkedList采用了二分查找（這里說(shuō)的二分只是簡(jiǎn)單的一次二分），判斷index與size中間位置的距離，采取從header向后還是向前查找。
到這里我們明白，基于雙向循環(huán)鏈表實(shí)現(xiàn)的LinkedList，通過(guò)索引Index的操作時(shí)低效的，index所對(duì)應(yīng)的元素越靠近中間所費(fèi)時(shí)間越長(zhǎng)。而向鏈表兩端插入和刪除元素則是非常高效的（如果不是兩端的話，都需要對(duì)鏈表進(jìn)行遍歷查找）。

是否包含

// 判斷LinkedList是否包含元素(o)
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

// 從前向后查找，返回“值為對(duì)象(o)的節(jié)點(diǎn)對(duì)應(yīng)的索引”
// 不存在就返回-1
public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header .next; e != header; e = e.next ) {
            if (e.element ==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header .next; e != header; e = e.next ) {
            if (o.equals(e.element ))
                return index;
            index++;
        }
    }
    return -1;
}

// 從后向前查找，返回“值為對(duì)象(o)的節(jié)點(diǎn)對(duì)應(yīng)的索引”
// 不存在就返回-1
public int lastIndexOf(Object o) {
    int index = size ;
    if (o==null) {
        for (Entry e = header .previous; e != header; e = e.previous ) {
            index--;
            if (e.element ==null)
                return index;
        }
    } else {
        for (Entry e = header .previous; e != header; e = e.previous ) {
            index--;
            if (o.equals(e.element ))
                return index;
        }
    }
    return -1;
}

和public boolean remove(Object o) 一樣，indexOf查詢?cè)匚挥谌萜鞯乃饕恢?，都是需要?duì)鏈表進(jìn)行遍歷操作，當(dāng)然也就是低效了啦。

判斷容量

/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size ;
}

/**
 * {@inheritDoc}
 *
 * <p>This implementation returns <tt>size() == 0 </tt>.
 */
public boolean isEmpty() {
    return size() == 0;
}

和ArrayList一樣，基于計(jì)數(shù)器size操作，容量判斷很方便。
到這里L(fēng)inkedList就分析完了，不對(duì)好像還差些什么對(duì)不對(duì)？是什么呢，就是最開(kāi)始說(shuō)的Deque雙端隊(duì)列，明白了鏈表原理和LinkedList的基本crud操作，Deque的LinkedList實(shí)現(xiàn)就已經(jīng)是so easy了，我們簡(jiǎn)單看下。

LinkedList實(shí)現(xiàn)的Deque雙端隊(duì)列

/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return <tt> true</tt> (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

/**
 * Retrieves and removes the head (first element) of this list
 * @return the head of this list, or <tt>null </tt> if this list is empty
 * @since 1.5
 */
public E poll() {
    if (size ==0)
        return null;
    return removeFirst();
}

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    return remove(header .next);
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 * @return the head of this list, or <tt>null </tt> if this list is empty
 * @since 1.5
 */
public E peek() {
    if (size ==0)
        return null;
    return getFirst();
}

/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getFirst() {
    if (size ==0)
       throw new NoSuchElementException();

    return header .next. element;
}

/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 *
 * <p>This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
   addBefore(e, header.next );
}

看看Deque 的實(shí)現(xiàn)是不是很簡(jiǎn)單，邏輯都是基于上面講的鏈表操作的，對(duì)于隊(duì)列的一些概念我不打算在這里講，是因?yàn)楹竺骊?duì)列會(huì)單獨(dú)拿出來(lái)分析啦，這里只要理解基于鏈表實(shí)現(xiàn)的list內(nèi)部是怎么操作的就可以啦。

總結(jié)：
(01) LinkedList 實(shí)際上是通過(guò)雙向鏈表去實(shí)現(xiàn)的。
它包含一個(gè)非常重要的內(nèi)部類：Entry。Entry是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，它包括的屬性有：當(dāng)前節(jié)點(diǎn)所包含的值，上一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)。
(02) 從LinkedList的實(shí)現(xiàn)方式中可以發(fā)現(xiàn)，它不存在LinkedList容量不足的問(wèn)題。
(03) LinkedList的克隆函數(shù)，即是將全部元素克隆到一個(gè)新的LinkedList對(duì)象中。
(04) LinkedList實(shí)現(xiàn)java.io.Serializable。當(dāng)寫入到輸出流時(shí)，先寫入“容量”，再依次寫入“每一個(gè)節(jié)點(diǎn)保護(hù)的值”；當(dāng)讀出輸入流時(shí)，先讀取“容量”，再依次讀取“每一個(gè)元素”。
(05) 由于LinkedList實(shí)現(xiàn)了Deque，而Deque接口定義了在雙端隊(duì)列兩端訪問(wèn)元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時(shí)拋出異常，另一種形式返回一個(gè)特殊值（null 或 false，具體取決于操作）。

對(duì)LinkedList以及ArrayList的迭代效率比較

先說(shuō)結(jié)論：ArrayList使用最普通的for循環(huán)遍歷比較快，LinkedList使用foreach循環(huán)比較快。

看一下兩個(gè)List的定義：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

注意到ArrayList是實(shí)現(xiàn)了RandomAccess接口而LinkedList則沒(méi)有實(shí)現(xiàn)這個(gè)接口，關(guān)于RandomAccess這個(gè)接口的作用，看一下JDK API上的說(shuō)法：

為此，我寫一段代碼證明一下這一點(diǎn)，注意，雖然上面的例子用的Iterator，但是做foreach循環(huán)的時(shí)候，編譯器默認(rèn)會(huì)使用這個(gè)集合的Iterator。測(cè)試代碼如下：

public class TestMain
{
    private static int SIZE = 111111;
    
    private static void loopList(List<Integer> list)
    {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++)
        {
            list.get(i);
        }
        System.out.println(list.getClass().getSimpleName() + "使用普通for循環(huán)遍歷時(shí)間為" + 
                (System.currentTimeMillis() - startTime) + "ms");
        
        startTime = System.currentTimeMillis();
        for (Integer i : list)
        {
            
        }
        System.out.println(list.getClass().getSimpleName() + "使用foreach循環(huán)遍歷時(shí)間為" + 
                (System.currentTimeMillis() - startTime) + "ms");
    }
    
    public static void main(String[] args)
    {
        List<Integer> arrayList = new ArrayList<Integer>(SIZE);
        List<Integer> linkedList = new LinkedList<Integer>();
        
        for (int i = 0; i < SIZE; i++)
        {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        loopList(arrayList);
        loopList(linkedList);
        System.out.println();
    }
}

我截取三次運(yùn)行結(jié)果：

ArrayList使用普通for循環(huán)遍歷時(shí)間為10ms
ArrayList使用foreach循環(huán)遍歷時(shí)間為36ms
LinkedList使用普通for循環(huán)遍歷時(shí)間為21841ms
LinkedList使用foreach循環(huán)遍歷時(shí)間為34ms

ArrayList使用普通for循環(huán)遍歷時(shí)間為11ms
ArrayList使用foreach循環(huán)遍歷時(shí)間為27ms
LinkedList使用普通for循環(huán)遍歷時(shí)間為20500ms
LinkedList使用foreach循環(huán)遍歷時(shí)間為27ms

ArrayList使用普通for循環(huán)遍歷時(shí)間為10ms
ArrayList使用foreach循環(huán)遍歷時(shí)間為22ms
LinkedList使用普通for循環(huán)遍歷時(shí)間為20237ms
LinkedList使用foreach循環(huán)遍歷時(shí)間為38ms

有了JDK API的解釋，這個(gè)結(jié)果并不讓人感到意外，最最想要提出的一點(diǎn)是：如果使用普通for循環(huán)遍歷LinkedList，其遍歷速度將慢得令人發(fā)指。

總結(jié)

ArrayList和LinkedList的比較

1、順序插入速度ArrayList會(huì)比較快，因?yàn)锳rrayList是基于數(shù)組實(shí)現(xiàn)的，數(shù)組是事先new好的，只要往指定位置塞一個(gè)數(shù)據(jù)就好了；LinkedList則不同，每次順序插入的時(shí)候LinkedList將new一個(gè)對(duì)象出來(lái)，如果對(duì)象比較大，那么new的時(shí)間勢(shì)必會(huì)長(zhǎng)一點(diǎn)，再加上一些引用賦值的操作，所以順序插入LinkedList必然慢于ArrayList

2、基于上一點(diǎn)，因?yàn)長(zhǎng)inkedList里面不僅維護(hù)了待插入的元素，還維護(hù)了Entry的前置Entry和后繼Entry，如果一個(gè)LinkedList中的Entry非常多，那么LinkedList將比ArrayList更耗費(fèi)一些內(nèi)存

3、數(shù)據(jù)遍歷的速度，看最后一部分，這里就不細(xì)講了，結(jié)論是：使用各自遍歷效率最高的方式，ArrayList的遍歷效率會(huì)比LinkedList的遍歷效率高一些

4、有些說(shuō)法認(rèn)為L(zhǎng)inkedList做插入和刪除更快，這種說(shuō)法其實(shí)是不準(zhǔn)確的：

（1）LinkedList做插入、刪除的時(shí)候，慢在尋址，快在只需要改變前后Entry的引用地址

（2）ArrayList做插入、刪除的時(shí)候，慢在數(shù)組元素的批量copy，快在尋址

所以，如果待插入、刪除的元素是在數(shù)據(jù)結(jié)構(gòu)的前半段尤其是非?？壳暗奈恢玫臅r(shí)候，LinkedList的效率將大大快過(guò)ArrayList，因?yàn)锳rrayList將批量copy大量的元素；越往后，對(duì)于LinkedList來(lái)說(shuō)，因?yàn)樗请p向鏈表，所以在第2個(gè)元素后面插入一個(gè)數(shù)據(jù)和在倒數(shù)第2個(gè)元素后面插入一個(gè)元素在效率上基本沒(méi)有差別，但是ArrayList由于要批量copy的元素越來(lái)越少，操作速度必然追上乃至超過(guò)LinkedList。

從這個(gè)分析看出，如果你十分確定你插入、刪除的元素是在前半段，那么就使用LinkedList；如果你十分確定你刪除、刪除的元素在比較靠后的位置，那么可以考慮使用ArrayList。如果你不能確定你要做的插入、刪除是在哪兒呢？那還是建議你使用LinkedList吧，因?yàn)橐粊?lái)LinkedList整體插入、刪除的執(zhí)行效率比較穩(wěn)定，沒(méi)有ArrayList這種越往后越快的情況；二來(lái)插入元素的時(shí)候，弄得不好ArrayList就要進(jìn)行一次擴(kuò)容，記住，ArrayList底層數(shù)組擴(kuò)容是一個(gè)既消耗時(shí)間又消耗空間的操作。

參考

該文為本人學(xué)習(xí)的筆記，方便以后自己跳槽前復(fù)習(xí)。參考網(wǎng)上各大帖子，取其精華整合自己的理解而成。集合框架源碼面試經(jīng)常會(huì)問(wèn)，所以解讀源碼十分必要,希望對(duì)你有用。
java提高篇（二三）-----HashMap
Java 集合系列10之 HashMap詳細(xì)介紹(源碼解析)和使用示例
圖解集合4：HashMap

整理的集合框架思維導(dǎo)圖

個(gè)人整理的Java集合框架思維導(dǎo)圖，動(dòng)態(tài)維護(hù)。導(dǎo)出的圖片無(wú)法查看備注的一些信息，所以需要源文件的童鞋可以關(guān)注我個(gè)人主頁(yè)上的公眾號(hào)，回復(fù)Java集合框架即可獲取源文件。

一直覺(jué)得自己寫的不是技術(shù)，而是情懷，一篇篇文章是自己這一路走來(lái)的痕跡。靠專業(yè)技能的成功是最具可復(fù)制性的，希望我的這條路能讓你少走彎路，希望我能幫你抹去知識(shí)的蒙塵，希望我能幫你理清知識(shí)的脈絡(luò)，希望未來(lái)技術(shù)之巔上有你也有我。