LinkedList源碼刨析

數組和結點這兩種數據結構之間的差異，決定了LinkedList相比ArrayList擁有更高的插入和刪除效率，而隨機訪問效率不如ArrayList。

目錄

• transient
• Externalizable
• LinkedList源碼刨析
  • Node
  • LinkedList

transient

transient只能用來修飾成員變數（field），被transient修飾的成員變數不參與序列化過程。

序列化: JVM中的Java對象轉化為位元組序列。

反序列化: 位元組序列轉化為JVM中的Java對象。

靜態成員變數即使不加transient關鍵字也無法被序列化。

Externalizable

自定義序列化，無視transient關鍵字

public class Person implements Externalizable {
    private String nickName;
    private transient String realName;
    
    @Override
    public void writeExternal(ObjectOutput out) throws IOException {
        out.writeUTF(realName);
        out.writeUTF(childName);
    }

    @Override
    public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
        realName = in.readUTF();
        childName = in.readUTF();
    }
    
    public static void main(String[] args){
        //序列化
        os = new ObjectOutputStream(new FileOutputStream(filePath));
        os.writeObject(x);
        //反序列化
        is = new ObjectInputStream(new FileInputStream(filePath));
        Person readObject = (Person)is.readObject();
    }
}

LinkedList源碼刨析

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;
        }
}

LinkedList

因為存在數據結構基礎，不全記錄，只記錄覺得寫的妙的源碼和比較經典的源碼。

看了一段就知道，LinkedList的核心問題在註意頭指針和尾指針的同時，怎麼嚴密的修改前指針和後指針的問題，看前問自己幾個問題，怎麼添加(刪除)頭(尾)結點？怎麼插入(刪除)中間結點(給你個結點你怎麼確定它是中間結點還是頭尾結點?)？。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    
    transient int size = 0;
    
    transient Node<E> first;
    
    transient Node<E> last;
    
    //因為類中只記錄了first結點和last結點，通過一次二分可以找到目標結點和first結點比較接近還是last結點比較接近
	Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
	}
    
    //如果原頭結點為空，則讓尾指針指向新結點（頭尾重合）；如果原頭結點不為空，那麼就讓原頭結點的前指針指向新的頭結點
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    
    //將原尾節點的後指針指向新的尾節點
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    
    //插入到succ結點之前
    void linkBefore(E e, Node<E> succ) {
        //記錄succ的前指針
        final Node<E> pred = succ.prev;
        //pred<-newNode->succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        //將prev<-succ修改為newNode<-succ
        succ.prev = newNode;
        if (pred == null)
            //前指針為空，說明succ為頭指針，而現在newNode為頭指針
            first = newNode;
        else
            //將pred->succ 修改為 pred->newNode
            pred.next = newNode;
        size++;
        modCount++;
    }
    
    //這也有棧頂？peek出的first頭節點。
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    
    //很粗暴的轉換數組
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
    
    
}