LinkedList源碼

jonh_felix 發(fā)布于2019-08-19 11:43 / 2190人閱讀

摘要：不是線程安全確保線程安全方法源碼分析靜態(tài)內(nèi)部類(lèi)是一個(gè)鏈表需要一個(gè)類(lèi)作為節(jié)點(diǎn)，因此他在內(nèi)部構(gòu)建了一個(gè)靜態(tài)內(nèi)部類(lèi)。靜態(tài)內(nèi)部類(lèi)，該類(lèi)不能直接訪問(wèn)的非靜態(tài)成員屬性和方法，因?yàn)榈募s束靜態(tài)方法不能直接訪問(wèn)非靜態(tài)的成員。通過(guò)方法取得對(duì)象，然后取得的值。

1 說(shuō)明

LinkedList是一個(gè)雙向鏈表，繼承看List接口和Duque接口。

LinkedList不是線程安全,確保線程安全方法

 List list = Collections.synchronizedList(new LinkedList(...))

2 源碼分析 2.1 靜態(tài)內(nèi)部類(lèi)

LinkedList是一個(gè)鏈表,需要一個(gè)node類(lèi)作為節(jié)點(diǎn)，因此他在內(nèi)部構(gòu)建了一個(gè)靜態(tài)內(nèi)部類(lèi)。

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

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

靜態(tài)內(nèi)部類(lèi)，該類(lèi)不能直接訪問(wèn)LinkedLIst的非靜態(tài)成員（屬性和方法），因?yàn)镴ava的約束：靜態(tài)方法不能直接訪問(wèn)非靜態(tài)的成員。

2.2 add()方法

往==鏈表尾部==添加元素,boolean修飾，總是返回true

public boolean add(E e) {
    linkLast(e);
    return true;
}

再看linkLast(e)方法

void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

如果l為空，則表示鏈表為空，插入的元素作為列表的第一個(gè)元素。
last是一個(gè)全局變量

transient Node last;

然后相應(yīng)的size也增加。size也是一個(gè)全局變量

transient int size = 0;

這樣的話就可以寫(xiě)個(gè)獲取size的方法，所以的size的方法為

public int size() {
    return size;
}

2.3 get()方法

public E get(int index) {
    checkElementIndex(index); 
    return node(index).item;
}

==checkElementIndex(index)== 判斷尋找的索引是否越界，如果越界則拋出異常。
==node(index).item== 通過(guò)方法取得nod對(duì)象，然后取得item的值。

Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

這里通過(guò)位運(yùn)算找出尋找范圍的中間值，如果小于中間值，則出鏈頭開(kāi)始尋找，否則從鏈尾往回尋找。值得借鑒。

2.4 toArray()方法

將列表轉(zhuǎn)成數(shù)組的一個(gè)橋梁方法

public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

2.5 clear()方法

此調(diào)用返回后，列表將為空

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node x = first; x != null; ) {
        Node next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

可以利用該方法清空l(shuí)ist列表，達(dá)到list多次復(fù)用的目的，減少內(nèi)存花銷(xiāo)