摘要：介紹是線程不安全的，允許元素為的雙向鏈表。構(gòu)造方法共有兩個(gè)構(gòu)造方法，一個(gè)是創(chuàng)建一個(gè)空的構(gòu)造函數(shù)，一個(gè)是將已有的添加到中。是將元素插入到的頭部。下一篇文章繼續(xù)分析上次分析了的結(jié)構(gòu)和添加方法這次開始分析下面的。注意源碼版本為直接進(jìn)入正題。

如果本文中有不正確的地方請指出
由于沒有留言可以在公眾號添加我的好友共同討論。

LinkedList 是線程不安全的，允許元素為null的雙向鏈表。

我們來看一下LinkedList的繼承結(jié)構(gòu)圖：

代碼實(shí)現(xiàn):

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

Cloneable實(shí)現(xiàn)克隆

Serializable序列化

List 定義了一些集合類的方法

Deque雙向隊(duì)列接口(就是兩端都可以進(jìn)行增加刪除操作)

注意一點(diǎn)LinkedList并沒有實(shí)現(xiàn)RandomAccess所以隨機(jī)訪問是非常慢的。

元素個(gè)數(shù)

transient int size = 0;

指向第一個(gè)節(jié)點(diǎn)的指針(注釋直接就寫著)

  /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node first;

指向最后一個(gè)節(jié)點(diǎn)的指針

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node last;

transient關(guān)鍵字的作用是保持變量不被序列化具體的百度。

不過我們注意到LinkedList是有Node類，這里的Node是一個(gè)內(nèi)部類：

item存儲的元素

next指向后置節(jié)點(diǎn)

prev指向前置節(jié)點(diǎn)

內(nèi)部類同時(shí)包含了一個(gè)構(gòu)造函數(shù)

其實(shí)LinkedList 集合就是由許多個(gè) Node 對象y一個(gè)連著一個(gè)組成手構(gòu)成，可以看下方的圖

可以看上面的四個(gè)元素，分別就是四個(gè)Node對象，可以看到node1所指向的prev上一個(gè)節(jié)點(diǎn)是空也就是沒有上節(jié)點(diǎn),node4所指向的next節(jié)點(diǎn)為空也就是沒有下一個(gè)節(jié)點(diǎn)。

LinkedList共有兩個(gè)構(gòu)造方法，一個(gè)是創(chuàng)建一個(gè)空的構(gòu)造函數(shù)，一個(gè)是將已有的Collection添加到LinkedList中。

因?yàn)長inkedList不同于ArrayList所以初始化不需要指定大小取分配內(nèi)存空間。

LinkedList有幾種添加方法我們先從add()開始。

checkPositionIndex(index);

可以看到在調(diào)用Add方法首先校驗(yàn)一下索引是否合法，如果不合法就會拋出異常。

if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));

然后如果索引值等于size的值則直接調(diào)用linkLast插入到尾部節(jié)點(diǎn)。

否則就linkBefore方法。
linkLast方法：

void linkLast(E e) {
        //將l設(shè)為尾節(jié)點(diǎn)
        final Node l = last;
        //構(gòu)造一個(gè)新節(jié)點(diǎn)，節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)引用指向尾節(jié)點(diǎn)l
        final Node newNode = new Node<>(l, e, null);
        //將尾節(jié)點(diǎn)設(shè)為創(chuàng)建的新節(jié)點(diǎn)
        last = newNode;
        //如果尾節(jié)點(diǎn)為空，表示原先鏈表為空
        if (l == null)
        //將頭節(jié)點(diǎn)設(shè)為新創(chuàng)建的節(jié)點(diǎn)（尾節(jié)點(diǎn)也是新創(chuàng)建的節(jié)點(diǎn)）
            first = newNode;
        else
        //將原來尾節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)
            l.next = newNode;
        size++;//節(jié)點(diǎn)數(shù)加1
        modCount++;
    }

注意一下這里出現(xiàn)了modCount方法，和ArrayList中一樣，iterator和listIterator方法返回的迭代器和列表迭代器實(shí)現(xiàn)使用。
linkBefore:

void linkBefore(E e, Node succ) {
        //將pred設(shè)為插入節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
        final Node pred = succ.prev;
        //將新節(jié)點(diǎn)的上引用設(shè)為pred,下引用設(shè)為succ
        final Node newNode = new Node<>(pred, e, succ);
        //succ的上一個(gè)節(jié)點(diǎn)的引用設(shè)為新節(jié)點(diǎn)
        succ.prev = newNode;
        //如果插入節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)引用為空
        if (pred == null)
        //新節(jié)點(diǎn)就是頭節(jié)點(diǎn)
            first = newNode;
        else
        //插入節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)引用設(shè)為新節(jié)點(diǎn)
            pred.next = newNode;
        size++;
        //同上
        modCount++;
    }

在LinkedList中有兩個(gè)addAll方法一個(gè)是 addAll(Collection c)一個(gè)是addAll(int index, Collection c),其實(shí)

addAll(Collection c)=addAll(int index, Collection c)

可以看下面的截圖:

源碼如下：

現(xiàn)在開始分析源碼：
首先我們可以看到先調(diào)用了checkPositionIndex(index);方法來檢查索引是否合法。
然后將傳進(jìn)來的Collection轉(zhuǎn)成Object數(shù)組

 Object[] a = c.toArray();

如果集合為空就直接返回false

if (numNew == 0)
            return false;

如果插入的位置等于鏈表的長度就把新增加的元素放在尾部。

Node pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

最后在循環(huán)要插入的元素。這里我們可以看到上面也有modCount。

addFirst是將元素插入到LinkedList的頭部。
如果現(xiàn)在的機(jī)構(gòu)是下圖的：

addFirst執(zhí)行的操作就是：

紅色是使用addFirst插入后的位置。一下是源碼

調(diào)用了linkFirst方法。

上面的操作時(shí)：

首先執(zhí)行final Node f = first;將頭節(jié)點(diǎn)賦值給 f

final Node newNode = new Node<>(null, e, f);將指定元素構(gòu)造成一個(gè)新節(jié)點(diǎn)，此節(jié)點(diǎn)的指向下一個(gè)節(jié)點(diǎn)的引用為頭節(jié)點(diǎn)

        //將新節(jié)點(diǎn)設(shè)為頭節(jié)點(diǎn)，那么原先的頭節(jié)點(diǎn) f 變?yōu)榈诙€(gè)節(jié)點(diǎn)
        first = newNode;
        //如果第二個(gè)節(jié)點(diǎn)為空，也就是原先鏈表是空
         if (f == null)
         //將這個(gè)新節(jié)點(diǎn)也設(shè)為尾節(jié)點(diǎn)（前面已經(jīng)設(shè)為頭節(jié)點(diǎn)了）
          last = newNode;
       else
            f.prev = newNode;//將原先的頭節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
       size++;//節(jié)點(diǎn)數(shù)加1
       modCount++;//和ArrayList中一樣記錄修改次數(shù)

addLast是將元素插入到尾部如圖(黃色元素)：

黃色node是新增加。注意add也是把元素添加到尾部。我們來看一下源碼：

這里看到addLast和add是調(diào)用的同一方法，這里就不在講解。可以看上方的代碼。

由于文章比較長分為兩次更新。下一篇文章繼續(xù)分析

上次分析了LinkedList的結(jié)構(gòu)和添加方法這次開始分析下面的。

注意源碼版本為JDK1.8

直接進(jìn)入正題。

在LinkedList中remove()和removeFirst()是相同的

在LinkedList中的刪除其實(shí)就是通過修改上一個(gè)節(jié)點(diǎn)和指向下一個(gè)節(jié)點(diǎn)的引用完成的,可以看下面的圖片：

我們可以看到把node6的prev指向清空然后把node3的next設(shè)置成空就完成了刪除的操作。
看一下JDK的源碼實(shí)現(xiàn)：

調(diào)用removeFirst,在調(diào)用removeFirst中先獲取頭部節(jié)點(diǎn)，如果頭節(jié)點(diǎn)為空就拋異常。

調(diào)用unlinkFirst

private E unlinkFirst(Node f) {
         final E element = f.item;
         //next 為頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
         final Node next = f.next;
         f.item = null;
         // 將節(jié)點(diǎn)的元素以及引用都設(shè)為 null，便于垃圾回收
         f.next = null; 
         //修改頭結(jié)點(diǎn)為第二個(gè)節(jié)點(diǎn)
         first = next; 
         //如果第二個(gè)節(jié)點(diǎn)為空（當(dāng)前鏈表只存在第一個(gè)元素）
         if (next == null)
            //那么尾節(jié)點(diǎn)也置為 null
             last = null;
         else
         //如果第二個(gè)節(jié)點(diǎn)不為空，那么將第二個(gè)節(jié)點(diǎn)的上一個(gè)引用置為 null
             next.prev = null;
         size--;
         modCount++;
         return element;
     } 

我們看一下removeLast，從列表中刪除最后一個(gè)元素

首先看到先獲取了last最后一個(gè)元素，如果為空然后就拋異常
然后調(diào)用了unlinkLast

看到unlinkLast方法中有一個(gè) help gc ,它的主要作用就是幫助GC來做垃圾回收。

private E unlinkLast(Node l) {
       // assert l == last && l != null;
         final E element = l.item;
         final Node prev = l.prev;
         l.item = null;
          //幫助GC垃圾回收
         l.prev = null;
         //尾節(jié)點(diǎn)為倒數(shù)第二個(gè)節(jié)點(diǎn)
         last = prev;
         //如果倒數(shù)第二個(gè)節(jié)點(diǎn)為null
         if (prev == null)
            //那么將節(jié)點(diǎn)也置為 null
             first = null;
         else
             prev.next = null;
        //如果倒數(shù)第二個(gè)節(jié)點(diǎn)不為空，那么將倒數(shù)第二個(gè)節(jié)點(diǎn)的下一個(gè)引用置為 null
         size--;
         modCount++;
         return element;
     }

同樣執(zhí)行了modCount++

根據(jù)索引來刪除元素

  //刪除此列表中指定位置的元素
      public E remove(int index) {
          //判斷索引 index >= 0 && index <= size中時(shí)拋出IndexOutOfBoundsException異常
          checkElementIndex(index);
          return unlink(node(index));
      }
      E unlink(Node x) {
          // assert x != null;
          final E element = x.item;
         final Node next = x.next;
         final Node prev = x.prev;
 
         if (prev == null) {//如果刪除節(jié)點(diǎn)位置的上一個(gè)節(jié)點(diǎn)引用為null（表示刪除第一個(gè)元素）
             first = next;//將頭結(jié)點(diǎn)置為第一個(gè)元素的下一個(gè)節(jié)點(diǎn)
         } else {//如果刪除節(jié)點(diǎn)位置的上一個(gè)節(jié)點(diǎn)引用不為null
             prev.next = next;//將刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)引用指向刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（去掉刪除節(jié)點(diǎn)）
             x.prev = null;//刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)引用置為null
         }
 
         if (next == null) {//如果刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)引用為null（表示刪除最后一個(gè)節(jié)點(diǎn)）
             last = prev;//將尾節(jié)點(diǎn)置為刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
         } else {//不是刪除尾節(jié)點(diǎn)
             next.prev = prev;//將刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的引用指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
             x.next = null;//將刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)引用置為null
         }
        //刪除節(jié)點(diǎn)內(nèi)容置為null，便于垃圾回收
         x.item = null;
         size--;
         modCount++;
         return element;
     }

簡單粗暴直接貼代碼

public E set(int index, E element) {
        //檢查索引是否合法否則IndexOutOfBoundsException異常
        checkElementIndex(index);
        //獲取指定索引的元素
        Node x = node(index);
        E oldVal = x.item;
        //將指定索引的元素替換成新的元素
        x.item = element;
        /返回指定索引位置原來的元素
        return oldVal;/
    }

很簡單

返回第一個(gè)元素

  public E getFirst() {
            獲取頭
         final Node f = first;
            判斷是否為空
         if (f == null)
             throw new NoSuchElementException();
        元素返回
         return f.item;
     }

返回最后一個(gè)元素

public E getLast() {
         final Node l = last;
         if (l == null)
             throw new NoSuchElementException();
         return l.item;
     }

返回指定索引元素

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

暫時(shí)就這么多

原創(chuàng)不易,如果你喜歡本文或者對你有幫助就請轉(zhuǎn)發(fā)