一、LinkedList基本原理

1. 優(yōu)點：插入數(shù)據(jù)特別的快，不像ArrayList數(shù)組那樣子，挪動大量的元素的，他是直接在鏈表里加一個節(jié)點就可以了
2. 缺點，不太適合在隨機(jī)的位置，獲取某個隨機(jī)的位置的元素，比如LinkedList.get(10)，這種操作，性能就很低，因為他需要遍歷這個鏈表，從頭開始遍歷這個鏈表，直到找到index = 10的這個元素為止
3. LinkedList底層是基雙向鏈表，而ArrayList底層基于數(shù)組。也就是底層結(jié)構(gòu)不同，才影響著他們的優(yōu)缺點

二、使用場景

1. ArrayList：代表一個集合，只要別頻繁的往里面插入和灌入大量的元素就可以了，遍歷，或者隨機(jī)查，都可以
2. LinkedList：適合，頻繁的在list中插入和刪除某個元素,典型的就是用作隊列

三、插入元素源碼

我們還是從基本的方法作為入口，還有一點就是我們一定要清楚，LinkedList主要用作隊列使用，最后只關(guān)注一下他的核心源碼

代碼片段一、

1. 首先要看下，最主要的是Node節(jié)點，包含了當(dāng)前元素，上一個節(jié)點、下一個節(jié)點

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

代碼片段二、add方法

1. addFirst方法其實和add方法一樣的

/**
* 這里默認(rèn)向鏈表的尾部插入
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 將當(dāng)前元素放入隊尾
    linkLast(e);
    return true;
}

代碼片段二、

/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 定義一個l元素，指向last尾元素
    final Node<E> l = last;
    // 新增一個Node，他的pre指針指向l，就是隊尾的那個元素，next指向null
    final Node<E> newNode = new Node<>(l, e, null);
    // 讓last指向新增的節(jié)點
    last = newNode;
    if (l == null)
        // 如果l為空，說明這是一個新的鏈表，新怎的節(jié)點也是頭結(jié)點
        first = newNode;
    else
        // l.next的意思是原來的隊尾節(jié)點的next指向當(dāng)前新怎的節(jié)點
        l.next = newNode;
    // 鏈表長度+1
    size++;
    modCount++;
}

代碼片段三、 addFirst方法

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    // 定義一個f變量，指向隊首
    final Node<E> f = first;
    // 新增一個新的節(jié)點，pre指針指向Null ,next指向隊首元素
    final Node<E> newNode = new Node<>(null, e, f);
    // 將first指針指向新增節(jié)點
    first = newNode;
    if (f == null)
        // 如果f為空，說明這是一個新的鏈表，新怎的節(jié)點也是頭結(jié)點
        last = newNode;
    else
        // y原來首節(jié)點的prev指向當(dāng)前新增節(jié)點
        f.prev = newNode;
    size++;
    modCount++;
}

代碼片段四、

在指定位置插入元素

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 參數(shù)校驗
    checkPositionIndex(index);

    // 如果是index==size，則直接插入尾部
    if (index == size)
        linkLast(element);
    else
        // node方法如下
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果index < size/2,說明index在隊列的前半部分
    if (index < (size >> 1)) {
        // 拿到第一個元素，然后從頭開始遍歷，
        Node<E> x = first;
        //不停的遍歷，直到找到index的位置，然后返回x
        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;
    }
}

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    //創(chuàng)建一個新的節(jié)點，前一個節(jié)點是index節(jié)點的前一個節(jié)點，next節(jié)點為succ節(jié)點
    // 其實就是node方法遍歷的時候找到的那個index對應(yīng)的節(jié)點
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 讓原來的節(jié)點的prev指向新創(chuàng)建的節(jié)點
    succ.prev = newNode;
    if (pred == null)
        // pred如果為空的話，說明index對應(yīng)是頭結(jié)點
        first = newNode;
    else
        // index節(jié)點原來對應(yīng)的next指向創(chuàng)建的新節(jié)點
        pred.next = newNode;
    size++;
    modCount++;
}

四、獲取元素源碼

代碼片段一、getFirst peek

/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
//返回第一個元素，這里的first其實就是指向了鏈表的第一個元素
// 如果鏈表為空的話，則拋出異常
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
// 和getFirst區(qū)別就是如果鏈表為空的話，返回null
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * Returns the element at the specified position in this list.
 * 對于LinkedList而言，讀取某個元素的時候，是通過node方法，遍歷鏈表，判斷index的位置，所以隨機(jī)讀取
* 是LinkedList的弱點
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

五、刪除元素

代碼片段一、

/**
 * Retrieves and removes the head (first element) of this list.
 * 刪除頭部元素
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}



/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    // 首先。拿到鏈表的第一個元素
    final Node<E> f = first;
    // 如果隊頭的元素為null的話，這個隊列也是空的
    if (f == null)
        throw new NoSuchElementException();
    // 最后還是走到unlinkFirst，刪除的核心邏輯
    return unlinkFirst(f);
}


/**
 * Removes and returns the last element from this list.
 *
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * Removes and returns the last element from this list.
 *
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * Unlinks non-null last node l.
* 這里和unlinkfirst幾乎一個套路
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 1.先拿到隊頭的元素
    // 2. 然后拿到隊頭的next元素
    // 3. 隊頭的元素=null，
    // 4. 隊頭的next指針指向null
    // 5.將first指針指向next
    // 6. 通過2、3、4、5步驟，其實就是將隊頭的元素釋放掉了
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}