一、基本圖示

image

二、基本介紹

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

結(jié)構(gòu)

• LinkedList 繼承 AbstractSequentialList 抽象類，該類是只支持按次序訪問
• LinkedList 實現(xiàn)了 List 接口
• LinkedList 實現(xiàn)了 Deque 接口，即能被當(dāng)作雙端隊列
• 實現(xiàn)了 Cloneable 接口，覆蓋了 clone 方法，即可以被克隆
• 實現(xiàn)了 Serializable 接口，支持序列化

特性

• 底層使用鏈表，還是雙向鏈表
• 元素是有序的，輸入順序和輸出順序一致
• 是線程不安全的
• 可以添加元素 null，可以添加相同的元素

三、雙向鏈表的基本結(jié)構(gòu)

因為底層是雙向鏈表，因此所有成員變量都和鏈表的屬性有關(guān)

// 鏈表的長度
transient int size = 0;

// 頭節(jié)點
transient Node<E> first;

// 尾節(jié)點
transient Node<E> last;

這是一個雙向鏈表改有的基本結(jié)構(gòu)，包括指向前面的節(jié)點、數(shù)據(jù)、指向后面的節(jié)點

private static class Node<E> {
    E item;
    Node<E> next;   //指向下一個節(jié)點
    Node<E> prev;   //指向上一個節(jié)點

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

四、內(nèi)部調(diào)用的方法

因為在調(diào)用增加、刪除、修改方法的時候，都是直接調(diào)用這幾個方法，因此就直接來看這幾個方法。包括

• void linkFirst(E e)：把數(shù)值插入到鏈表頭部
• void linkLast(E e)：把數(shù)值插入到鏈表尾部
• void linkBefore(E e, Node<E> succ)：在指定節(jié)點前面插入值(節(jié)點不為空)
• E unlinkFirst(Node<E> f)：刪除不為空的頭節(jié)點，返回刪除的值
• E unlinkLast(Node<E> l)：刪除不為空的尾節(jié)點，返回刪除的值
• E unlink(Node<E> x)：刪除不為空的指定節(jié)點
• Node<E> node(int index)：返回指定位置的節(jié)點

// 把數(shù)據(jù)插入到鏈表頭部
private void linkFirst(E e) {
    // 獲取當(dāng)前鏈表的頭節(jié)點
    final Node<E> f = first;
    // 創(chuàng)建一個節(jié)點，向前指向 null，向后指向當(dāng)前鏈表的頭節(jié)點 f
    final Node<E> newNode = new Node<>(null, e, f);
    // f 指向新的節(jié)點
    first = newNode;
    // 如果 f 為空(添加之前什么也沒有)，則鏈表的尾節(jié)點也指向新建節(jié)點
    // 此時鏈表的頭節(jié)點和尾節(jié)點都指向這個新創(chuàng)建的節(jié)點
    if (f == null)
        last = newNode;
    // 如果 f 不為空(添加之前頭節(jié)點已經(jīng)有了)，原來的頭節(jié)點向前指向新的節(jié)點
    else
        f.prev = newNode;
    size++;
    modCount++;
}

// 把數(shù)據(jù)插入到鏈表尾部
void linkLast(E e) {
    // 獲取當(dāng)前鏈表的尾節(jié)點
    final Node<E> l = last;
    // 創(chuàng)建一個節(jié)點，向前指向該鏈表的尾節(jié)點，向后指向 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 將 l(之前的尾節(jié)點) 指向新的節(jié)點
    last = newNode;
    // 如果 l 為空，則鏈表的頭節(jié)點也指向該新節(jié)點，此時鏈表的頭和尾節(jié)點都指向該節(jié)點
    if (l == null)
        first = newNode;
    // 如果 l 不為空(鏈表不為空)，則原來的尾節(jié)點向后指向新創(chuàng)建的節(jié)點
    else
        l.next = newNode;
    size++;
    modCount++;
}

// 在指定節(jié)點前面插入值，這里假設(shè)指定節(jié)點不為空
void linkBefore(E e, Node<E> succ) {
    // 獲取指定節(jié)點的前一個節(jié)點
    final Node<E> pred = succ.prev;
    // 創(chuàng)建一共新節(jié)點，向前指向 succ 節(jié)點的前一個節(jié)點，向后指向 succ 節(jié)點，數(shù)值是 e
    final Node<E> newNode = new Node<>(pred, e, succ);
    // succ 向前指向新建的節(jié)點
    succ.prev = newNode;
    // 如果 succ 前面的節(jié)點為空，則新建的節(jié)點就是第一個節(jié)點
    if (pred == null)
        first = newNode;
    // 如果 succ 前面的節(jié)點不為空，則用 succ 節(jié)點向后指向新建的節(jié)點
    // 此時代表插入完成
    else
        pred.next = newNode;
    size++;
    modCount++;
}

// 刪除不為空的頭節(jié)點，返回刪除節(jié)點的值
private E unlinkFirst(Node<E> f) {
    // 獲取頭節(jié)點的數(shù)據(jù)
    final E element = f.item;
    // 獲取頭節(jié)點的后面一個節(jié)點 next
    final Node<E> next = f.next;
    // 將頭節(jié)點的數(shù)據(jù)置空
    f.item = null;
    // 將頭節(jié)點向后指向 null
    f.next = null;
    // 此時后面一個節(jié)點變?yōu)轭^節(jié)點
    first = next;
    // 如果頭節(jié)點向后指向 null，即原本鏈表中就這一個節(jié)點，移除后鏈表中就沒有節(jié)點了
    if (next == null)
        last = null;
    // 如果頭節(jié)點后面還有節(jié)點，那么刪除的頭節(jié)點就指向 null
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

// 刪除不為空的尾節(jié)點，返回刪除節(jié)點的值
private E unlinkLast(Node<E> l) {
    // 獲取尾節(jié)點的數(shù)值
    final E element = l.item;
    // 獲取尾節(jié)點的前面一個節(jié)點 prev
    final Node<E> prev = l.prev;
    // 將尾節(jié)點的置空
    l.item = null;
    // 將尾節(jié)點向前指向 null
    l.prev = null;
    // 此時前面一個節(jié)點變?yōu)殒湵淼奈补?jié)點
    last = prev;
    // 如果尾節(jié)點的向前指向 null，即鏈表本來就只有這一個節(jié)點，移除后鏈表中就沒有節(jié)點了
    if (prev == null)
        first = null;
    // 如果尾節(jié)點前面還有節(jié)點，則向后指向 null
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

// 刪除指定不為空的節(jié)點，返回節(jié)點對應(yīng)的值
E unlink(Node<E> x) {
    // 獲取要刪除節(jié)點的值
    final E element = x.item;
    // 獲取刪除節(jié)點后面的節(jié)點 next，前面的節(jié)點 prev
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    // 如果要刪除的節(jié)點前面沒有節(jié)點，說明是第一個節(jié)點
    if (prev == null) {
        // 此時刪除節(jié)點后面的那個節(jié)點變成頭節(jié)點
        first = next;
    // 如果要刪除的節(jié)點不是第一個
    } else {
        // 讓要刪除節(jié)點的前一個節(jié)點向后指向要刪除節(jié)點的后一個節(jié)點，即直接跨過要刪除的節(jié)點
        prev.next = next;
        // 同時向前指向 null
        x.prev = null;
    }

    // 如果要刪除節(jié)點后面沒有節(jié)點，說明是最后一個節(jié)點
    if (next == null) {
        // 此時刪除節(jié)點前面那個節(jié)點變?yōu)槲补?jié)點
        last = prev;
    // 如果要刪除的節(jié)點不是最后一個節(jié)點
    } else {
        // 讓要刪除節(jié)點的后一個節(jié)點向前指向要刪除節(jié)點的前一個節(jié)點，還是跳過要刪除的節(jié)點
        next.prev = prev;
        // 同時向后指向 null
        x.next = null;
    }
    
    // 將要刪除的節(jié)點的值置空
    x.item = null;
    size--;
    modCount++;
    // 返回刪除的節(jié)點
    return element;
}

// 獲取指定位置的節(jié)點
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;
    }
}

需要注意 Node<E> node(int index) 方法，該方法會在后面的查找和刪除等方法中用到，它的作用在于，是根據(jù)你傳入的位置來判斷是從鏈表的前面還是后開始查找，當(dāng)傳入位置小于長度的一半時，從前向后查找；否則，從后向前查找

五、添加方法

在指定位置進行插入的時候，會先調(diào)用 node(int index) 方法判斷該位置是在集合長度的一半之后還是之后，如果小于長度一半則從前向后尋找位置，然后添加元素；否則，從后向前尋找位置，然后添加

// 在集合尾部添加元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在集合的指定位置添加值
public void add(int index, E element) {
    checkPositionIndex(index);
    
    // 如果插入位置正好是集合最后一位的后一位
    if (index == size)
        // 則在鏈表最后添加
        linkLast(element);
    else
        // 否則先根據(jù)位置確定對應(yīng)的元素
        // 然后把指定值插入到該元素的前面
        linkBefore(element, node(index));
}

// 在指定位置插入一個集合
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    
    // 將傳入的集合轉(zhuǎn)為 Object 數(shù)組
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    
    // 定義兩個節(jié)點，pred 是插入位置的前一個節(jié)點，succ 是插入位置的后一個節(jié)點
    Node<E> pred, succ;
    // 直接將集合插入到最后
    if (index == size) {
        // succ 沒什么用，直接置空
        succ = null;
        // pred 用來保存每插入一個元素的位置
        pred = last;
    // 如果集合不是插入到尾部
    } else {
        succ = node(index);
        pred = succ.prev;
    }

     // 遍歷集合數(shù)組
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 創(chuàng)建新節(jié)點，向前指向 pred
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果 pred 為空，表明新建的節(jié)點是頭節(jié)點
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        // pred 保存最后一個新建節(jié)點的位置
        pred = newNode;
    }
    
    // 如果 succ 是 null，說明集合是直接插入到尾部的
    if (succ == null) {
        // 此時插入的最后一個元素便是尾節(jié)點
        last = pred;
    // 否則，將插入的最后一個元素和插入位置的后一個節(jié)點相連接
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

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

// 將集合直接插入到尾部
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在集合頭部插入元素
public void addFirst(E e) {
    linkFirst(e);
}

// 在集合尾部插入元素
public void addLast(E e) {
    linkLast(e);
}

六、刪除方法

主要包括三種

• 按照位置刪除
• 按照指定元素刪除(如果重復(fù)則只刪除第一次出現(xiàn)的那個元素)
  • 從前往后尋找
  • 從后往前尋找
• 刪除第一個或最后一個元素

如果從指定位置刪除對應(yīng)的元素，也會先判斷位置然后再進行對應(yīng)的操作，這一點和增加操作一樣

// 刪除集合中的第一個元素
public E remove() {
    return removeFirst();
}

// 刪除集合中指定位置的節(jié)點
public E remove(int index) {
    checkElementIndex(index);
    // 先使用 node(int index) 方法找到指定位置的節(jié)點
    // 調(diào)用 unlink(Node<E> x) 刪除該節(jié)點
    return unlink(node(index));
}

// 刪除集合中指定的元素(如果集合中有不止一個，則只刪除前面一個)
public boolean remove(Object o) {
    // 如果指定元素為 null
    if (o == null) {
        // 遍歷鏈表中的元素
        for (Node<E> x = first; x != null; x = x.next) {
            // 只要遍歷到 null，刪除并返回 true
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    // 否則，直接根據(jù)節(jié)點中的元素進行判斷
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 刪除第一個頭節(jié)點，返回刪除的元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 刪除最后一個節(jié)點，返回刪除的元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 刪除指定元素(從前往后如果有相同的則只刪除第一次出現(xiàn)的)，就是 remove(Object o) 方法
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

// 刪除指定元素(從后往前如果有相同的則只刪除第一次出現(xiàn)的)，就是倒置的 remove(Object o) 方法
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 清空集合方法
public void clear() {
    // 這里將鏈表從頭到末尾每個節(jié)點的元素，向前之前，向后指向前部置空
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

七、修改，獲取的方法

// 在指定位置修改元素，返回被修改的元素的值
public E set(int index, E element) {
    checkElementIndex(index);
    // 獲取 node(int index) 找到指定該位置的節(jié)點
    Node<E> x = node(index);
    // 獲取該節(jié)點的元素，并替換
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

// 獲取指定位置的元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 獲取集合的第一個元素
public E getFirst() {
    // 獲取頭節(jié)點
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 獲取集合的最后一個元素
public E getLast() {
    // 獲取尾節(jié)點
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

八、其他方法

// 返回傳入的元素在集合中的位置，如果沒有則返回 -1
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        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;
}

// 判斷集合中是否存在傳入的元素
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

九、遍歷方法

(1) 迭代器方式

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

(2) 使用 for 循環(huán)

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

(3) 使用 foreach

for(String i: list) {
    
}

其中迭代器和 foreach 遍歷的方式速度基本是一樣的，因為 foreach 本質(zhì)上也是用迭代器進行遍歷。一定不要使用 for 循環(huán)對 LinkedList 進行遍歷，速度會慢到令人絕望

具體原因可以去看：http://www.cnblogs.com/xrq730/p/5189565.html

十、參考

https://blog.csdn.net/u011240877/article/details/52876543
https://www.cnblogs.com/xrq730/p/5005347.html