LinkedList底層實作

一、什麼是LinkedList

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

根據源碼我們可以看出：

• ①LinkedList繼承了AbstractSequentialList，即按次序的List，也就是說不像ArrayList一樣具有随機通路元素的能力，也就是說LinkedList支援按順序通路清單中元素的操作。
• ②實作了List接口，可進行清單相關操作
• ③實作了Deque接口，可以将LinkedList當作雙端隊列進行使用
• ④實作Clonalbe接口，即覆寫了clone()方法，可以進行克隆操作
• ⑤實作了java.io.Serializable接口，可以進行序列化，即支援網絡傳輸

LinkedList的本質是雙向連結清單，與 ArrayList 相比，LinkedList 的增加和删除對操作效率更高，而查找和修改的操作效率較低。

二、LinkedList的建立

1、成員變量及資料結構

①transient int size = 0; //LinkedList存放元素個數

②first是雙向連結清單的表頭，last指向雙向連結清單的最後一個元素

transient Node first;

transient Node last;

③Node資料結構

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
           

存放資料元素，prev指向上一個節點，next指向下一個節點，item為元素值

2、first和last為什麼要用transist修飾？

在ArrayList中存放元素的資料結構elementData使用transisit修飾是為了節省空間，防止擴容後數組中的空資料也被序列化。

而LinkedList使用transist修飾是因為LinkedList中使用雙向連結清單儲存資料，結點中儲存前驅和後繼的引用。但是序列化之後前序結點和後繼結點的位址都變了，是以我們應該将資料傳輸過去再在另一邊連結為新的連結清單。

LinkedList的序列化與反序列化方法：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out size
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read in size
    int size = s.readInt();

    // Read in all elements in the proper order.
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}
           

3、LinkedList的建立

LinkedList list = new LinkedList(); // 普通建立方法

或者

LinkedList list = new LinkedList(Collection<? extends E> c); // 使用集合建立連結清單

使用集合建立連結清單步驟

• ①調用addAll( c )方法，而addAll( c )底層調用重寫方法addAll(size, c)

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
           

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

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

    size += numNew;
    modCount++;
    return true;
}
           

• ②addAll方法首先通過checkPositionIndex(index);判斷index是否越界，如果越界報越界異常。
• ③如果Collection為空直接return false
• ④如果Collection不為空，定義兩個指針pred,和succ；如果index等于size，那麼說明是在連結清單末尾插入Collection，使得pred指向last
• ⑤如果index不等于size，那麼一定小于size，使用node(index)方法獲得index處的node，是pred指向該node的上一個節點
• ⑥周遊Collection中的元素，将元素一個個插入進LinkedList中。

  

• ⑦最後，若succ為空，說明是在連結清單尾部插入的，更新last，若不為空，則是在連結清單中間插入的，執行操作，補全連結清單

  

三、LinkedList集合的各種插入删除操作

在前面我們說過，LinkedList可以當作隊列也能作為棧，是以linkedList中有許多插入删除的方法。

連結清單尾部插入資料操作：add()、addLast()、offer()、offerLast()

連結清單頭部插入資料操作：addFirst()、offerFirst()、push()

删除并傳回連結清單尾部的資料：removeLast()

删除并傳回連結清單頭部的資料：poll()、remove()、removeFirst()、pop()

擷取第一個元素的值：element()、getFirst()、peek()、peekFirst()

擷取最後一個元素的值：getLast()、peekLast()

在任意位置插入資料：add(int index, E element)

删除任意位置資料：remove(int index)

特别注意，作為如果使用linkedList作為棧，那麼以連結清單頭部作為棧進出的位置。

四、LinkedList的周遊

在ArrayList中已經講過，LinkedList不支援快速随機通路，是以周遊時采用疊代器周遊更快一些

要了解這個，首先要明白linkedList是一個連結清單，不支援随機通路，是以linkedList要得到一個元素，即get(i)的時間複雜度時o(n),是以使用一下的周遊方式，時間複雜度就會變為o(n^2)了

for (int i=0; i<size; i++) {
    list.get(i);        
}
           

而我們可以看到linkedList實作的iterator疊代器就是一個一個從first開始周遊到index大于size為止，是以擷取資料的時間複雜度為o(1)

是以使用LinkedList周遊推薦使用iterator疊代器

List<Integer> list = new LinkedList<>();
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    iterator.next();
}