?????上篇文章我們介紹了ArrayList類的基本的使用及其內(nèi)部的一些方法的實現(xiàn)原理世吨，但是這種集合類型雖然可以隨機(jī)訪問數(shù)據(jù)类早，但是如果需要刪除中間的元素就需要移動一半的元素的位置，效率低下。并且它內(nèi)部是用數(shù)組來實現(xiàn)的搏色，數(shù)組要求連續(xù)的存儲空間，當(dāng)數(shù)據(jù)量大的時候就極耗內(nèi)存券册。本篇我們介紹使用鏈表實現(xiàn)的集合LinkedList频轿，這種類型不需要連續(xù)的存儲空間，刪除數(shù)據(jù)方便烁焙，但是不支持隨機(jī)訪問并且查找效率低下航邢，幾乎是ArrayList的對立面。我們將從以下方面介紹此類型：

• 超接口和超類的基本方法及實現(xiàn)
• 內(nèi)部組成細(xì)節(jié)
• add方法的源碼解析
• remove方法的源碼解析
• 低效的get方法
• LinkedList的應(yīng)用場景
  一骄蝇、了解LinkedList的超接口
  ?????我們首先看到LinkedList實現(xiàn)了接口Deque膳殷，而這個接口又實現(xiàn)了Queue接口，那我們就從Queue接口看起九火。

public interface Queue<E> extends Collection<E> {
    boolean add(E e);//添加元素
    boolean offer(E e);//添加元素
    E remove();//刪除元素
    E poll();//刪除元素
    E element();//返回頭部元素
    E peek();//返回頭部元素
}

?????我們可以看到該接口中聲明的每個操作都是由兩個方法對應(yīng)秽之，那這兩個方法之間有什么不同呢？調(diào)用兩種方法的任意一種都是可以完成我們所需要的大部分功能吃既，但是當(dāng)處于特殊情況下考榨，兩者處理方式不一樣。比如：當(dāng)鏈表為空時鹦倚，調(diào)用remove就會拋異常河质，而poll則是返回特殊值null，當(dāng)鏈表滿了震叙，調(diào)用add就會拋異常掀鹅，而offer就會false。（我們的LinkedList 是沒有長度限制的媒楼，但是對于其他實現(xiàn)Queue的類可能會有長度限制乐尊，及可能會滿員）。
?????看完了Queue我們看看看他的子接口Deque（雙端隊列）：

public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    .......
    //由于方法比較多划址，此處為了不增加篇幅扔嵌，列舉一些說明問題即可
    .......
  }

?????我們可以很清晰的看到，Deque在繼承Queue接口的前提下夺颤，擴(kuò)展了N多方法痢缎，但是這些方法都是以XXfirst，XXlast形式的世澜，這說明了独旷，實現(xiàn)這個接口的類必須具有雙端操作隊列的能力。不在局限于從隊頭出，從隊尾增加嵌洼。當(dāng)然缸夹，可能有些讀者會有疑問磕诊，add方法和addlast方法實際上是相同的添寺，為什么要聲明addLast方法呢胚想？沒錯霜第，他們完成的功能的確一樣苛让，在LinkedList中也是這樣實現(xiàn)的：

 public void addLast(E e) {
        linkLast(e);
    }
 public boolean add(E e) {
        linkLast(e);
        return true;
   }
   //實際上他們調(diào)用同樣的方法來實現(xiàn)啤贩，只是返回了不同的類型
   
   //博主也不知道為何這樣設(shè)計唯欣，可能是為了封裝性更好吧

?????所以混萝，在LinkedList的內(nèi)部方法中遗遵，有三對是具有一樣功能的方法。
二逸嘀、LinkedList的內(nèi)部實現(xiàn)細(xì)節(jié)
?????之前我們也說過车要，既然實現(xiàn)了接口Deque 就一定是用雙向鏈表來實現(xiàn)的，學(xué)過數(shù)據(jù)結(jié)構(gòu)的讀者就會發(fā)現(xiàn)這種結(jié)構(gòu)靈活性很強(qiáng)崭倘。我們一起來看看：

/*為了節(jié)約篇幅翼岁，只截取部分代碼*/
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 transient Node<E> first;
 transient Node<E> last;
 //成員內(nèi)部類
 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的大體結(jié)構(gòu)司光，一個成員內(nèi)部類定義了每個節(jié)點的內(nèi)容琅坡，數(shù)據(jù)值和一個指向前一個節(jié)點的prev指針和一個指向后一個節(jié)點的next指針。在整個LinkedList中残家，有一個頭指針指向整個隊列的頭部榆俺，一個尾指針指向整個隊列的尾部。整個隊列的結(jié)構(gòu)如下圖：

這里寫圖片描述

public boolean add(E e) {
        linkLast(e);
        return true;
}
//主要實現(xiàn)還是linkLast
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++;
 }

?????我們知道add方法是在隊列尾部添加元素，還是很容易的啡直。首先用變量 l 指向最后一個節(jié)點烁涌，然后創(chuàng)建一個節(jié)點將它的prev指向 l ，這樣newnode成為最后一個節(jié)點酒觅，使用last指向它烹玉，接著使 l 的next指向newnode，這種直接添加在隊列尾部的方式還是很好理解的阐滩，我們重點看看如何添加在隊列的中間位置二打。

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
 void linkBefore(E e, Node<E> succ) {
     // assert succ != null;
     final Node<E> pred = succ.prev;
     final Node<E> newNode = new Node<>(pred, e, succ);
     succ.prev = newNode;
     if (pred == null)
         first = newNode;
     else
         pred.next = newNod
         size++;
        modCount++;
 }

?????首先判斷，指定的索引是否大于鏈表中節(jié)點個數(shù)size掂榔，如果index == size表示继效，將要添加在最后一個元素的后面症杏，和上述一樣，如果不是在最后位置添加元素瑞信，將數(shù)據(jù)域和node（index）（方法不具體看厉颤，就是返回索引值為index的結(jié)點）

這里寫圖片描述

這里寫圖片描述

這里寫圖片描述

這里寫圖片描述

這里寫圖片描述

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

?????從源代碼中我們可以清晰的看到毫痕，所謂的get方法也就是征峦，調(diào)用node方法遍歷整個鏈表，只是其中稍微做了點優(yōu)化消请，如果index的值小于size/2從頭部遍歷栏笆，否則從尾部遍歷‰可見效率一樣低下蛉加，所以我們以后寫程序的時候，如果遇到數(shù)據(jù)量不大但是需要經(jīng)常遍歷查找的時候使用ArrayList而不是LinkedList，如果數(shù)據(jù)量非常的大针饥，但是不是很經(jīng)常的查找時使用LinkedList厂抽。

?????本文是作者查閱書籍和博客總結(jié)得來，如有錯誤丁眼，望大家指出筷凤！