LinkedList源碼-基于JDK1.8

連結清單

連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連接配接次序來實作的。連結清單由一些的節點組成，節點 可以在運作是動态生成。每個節點包括兩個部門：一個是存儲資料元素的資料域，一個是存儲下一個節點指針的指針域。

雙連結清單是連結清單的一種，由節點組成，每個資料節點中都有兩個指針，分别指向前驅和後繼

LinkedList基本介紹

LinkedList底層是一個雙連結清單。主要用來儲存資料，實作了List接口。特點是增删比較快。

源碼分析

在 LinkedList中，定義了一個内部類Node來儲存每個節點的資訊。在這個内部類中，有一個E類型的變量item，用于存儲該節點的值，next 和 prev分别指向上一個節點和下一個節點即前繼和後繼節點

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

成員變量

transient int size = 0;//集合大小
transient Node<E> first;//頭節點
transient Node<E> last;//尾結點           

構造方法

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

空的構造方法則什麼都不需要傳，傳入 Collection的構造方法需要調用的是addAll。我們分析下addAll

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//調用addAll的重載
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//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;//如果添加的是到連結清單的最後則pred指向尾結點
    } else {
        succ = node(index);//如果是中間插入先找到這個節點，再講pred指向succ.prev
        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;//上一個節點的next指向新增的節點
        pred = newNode;//移到新的節點
    }
    if (succ == null) {
        last = pred;//如果是在尾結點添加的講last指向新的尾結點pred
    } else {
        pred.next = succ;//中間插入，将後面部分連接配接
        succ.prev = pred;//中間插入，将前面部分連接配接
    }
    size += numNew;
    modCount++;
    return true;
}           

add插入元素

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;//l指向尾結點
    //l前繼節點 e新建立的節點 null後繼節點
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;//設定新節點是尾結點
    if (l == null)//連結清單是否有元素
        first = newNode;
    else
        l.next = newNode;//設定尾結點的後繼節點是newNode
    size++;
    modCount++;
    }           

set修改元素

public E set(int index, E element) {
    checkElementIndex(index);//驗證index合法性
    Node<E> x = node(index);//找到index對應的節點
    E oldVal = x.item;//儲存原有的
    x.item = element;//替換新值
    return oldVal;
}           

node根據index找到對應的節點元素

Node<E> node(int index) {
    if (index < (size >> 1)) {//如果index小于size的一半，從頭節點開始找。否則從尾結點開始找
        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;
    }
}           

get根據索引擷取元素

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;//調用node獲得節點，再取出值傳回
}           

remove删除元素

public boolean remove(Object o) {
    if (o == null) {//如果o為空，先找到節點，通過unlink删除
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        //先找到節點，通過unlink删除
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}           

unlink

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;//後繼節點
    final Node<E> prev = x.prev;//前繼節點
    //删除節點的前繼節點為null 
    if (prev == null) {
        first = next;//如果前繼節點為空，将頭結點指向next節點
    } else {
        prev.next = next;//删除元素的前繼節點指向後繼節點
        x.prev = null;//清空删除節點的前繼節點
    }
    //删除節點的前繼節點為null
    if (next == null) {
        last = prev;//如果後繼節點為null，将尾結點指向prev節點
    } else {
        next.prev = prev;//删除元素的後繼節點的前繼節點指向prev節點
        x.next = null;//清空删除節點後前繼節點
    }

    x.item = null;//清空元素
    size--;
    modCount++;
    return element;
}           

indexOf查找索引

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {//o為空因為采用==判斷否則用equals，都是頭節點開始周遊
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}           

LinkedList的疊代器與ArrayList類似，這裡面就不再分析了