• 虛擬頭節(jié)點(diǎn)

再前面的add(int index, E element)或者remove(int index)函數(shù)中盟蚣，我們針對index == 0的情況進(jìn)行了特殊處理，因為一般來講徐伐，在頭尾兩部分的時候，可能存在一些特殊情況付翁。

有時候為了讓代碼更加精簡筛欢，統(tǒng)一所有節(jié)點(diǎn)的處理邏輯，可以再最前面增加一個虛擬頭節(jié)點(diǎn)（不存儲數(shù)據(jù)）

在前面的鏈表當(dāng)中战秋，我們是直接將first指針指向0的節(jié)點(diǎn)

1566905748814.png

現(xiàn)在我們增加一個虛擬頭節(jié)點(diǎn)璧亚，來指向0的節(jié)點(diǎn)，然后讓first指針指向虛擬的頭節(jié)點(diǎn)

1566905982701.png

需要做如下的調(diào)整

1. 為LinkedList增加一個構(gòu)造方法

       public LinkedList() {
           first = new Node<>(null,null);
       }
   

2. 調(diào)整node方法脂信，由于我們之前是直接重first開始取癣蟋，現(xiàn)在改為虛擬頭節(jié)點(diǎn)后，應(yīng)該重first的下一個節(jié)點(diǎn)開始取

       private Node<E> node(int index) {
           rangeCheck(index);
           Node<E> node = first.next;
           for (int i = 0; i < index; i++) {
               node = node.next;
           }
           return node;
       }
   

3. 由于現(xiàn)在增加虛擬頭節(jié)點(diǎn)后狰闪，為0節(jié)點(diǎn)疯搅，前面又一個虛擬頭節(jié)點(diǎn)，因此埋泵，在add(int index, E element)幔欧、remove(int index)等函數(shù)中罪治，就不需要處理index == 0 的情況，源碼查看LinkedList2類

這種方式礁蔗，不是很常見觉义，也不是很推薦，主要是對處理問題思路的拓展

• 復(fù)雜度分析

我們來針對前面ArrayList和LinkedList兩個類中浴井，E get(int index)晒骇、void add(int index, E element)、E set(int index, E element)磺浙、E remove(int index)洪囤、E remove(int index)方法進(jìn)行復(fù)雜度的分析

ArrayList中E get(int index)

    public E get(int index) {
        //對索引進(jìn)行判斷
        rangeCheck(index); //時間復(fù)雜度O(1)
        return elements[index];//時間復(fù)雜度O(1)
    }

E get(int index)的時間復(fù)雜度為O(1)

E set(int index, E element)

    public E set(int index,E element) {
        rangeCheck(index);//時間復(fù)雜度O(1)
        E old = elements[index];//時間復(fù)雜度O(1)
        elements[index] = element;//時間復(fù)雜度O(1)
        return old;
    }

E set(int index, E element)的時間復(fù)雜度為O(1)

void add(int index, E element)

void add(int index, E element) {
        //對索引進(jìn)行判斷
       rangeCheckForAdd(index);//時間復(fù)雜度O(1)
        //對數(shù)組進(jìn)行擴(kuò)容
        ensureCapacity(size + 1);//時間復(fù)雜度O(1)
    //在這個地方，數(shù)據(jù)規(guī)模為size
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

在add函數(shù)這個地方撕氧，數(shù)據(jù)規(guī)模為size箍鼓，并且由于復(fù)雜度與size和index有關(guān)，因此就復(fù)雜度會有多種情況呵曹，即下方表示的

復(fù)雜度一般分為以下幾種

• [ ] 最好情況復(fù)雜度

最好情況就是在最后添加元素款咖，這個時候不需要執(zhí)行循環(huán)，那么復(fù)雜度為O(1)

• [ ] 最壞情況復(fù)雜度

最壞的情況是在最前面添加元素奄喂，這個時候循環(huán)執(zhí)行的次數(shù)為數(shù)據(jù)規(guī)模铐殃，那么復(fù)雜度為O(n)

• [ ] 平均情況復(fù)雜度

在本例中，由于情況比較特殊跨新，假設(shè)傳入index的概率都一樣時富腊，那么index的平均值為（1 + 2 + 3 + . ... + n）/ n,那么復(fù)雜度為O(n / 2) -> O(n)

E remove(int index)

public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
    return old;
    }

同樣的，在刪除元素時域帐，也存在最好和最壞的情況赘被，最好的情況即為刪除最后一個元素，則復(fù)雜度為O(1)肖揣，最壞即為刪除最前面的一個元素民假，則復(fù)雜度為O(n)，平均復(fù)雜度也為O(n)

接下來我們來看LinkedList中的E get(int index)

    public E get(int index) {
        //該地方的復(fù)雜度取決于node(int index)的復(fù)雜度
        return node(index).element;
    }

鏈表的結(jié)構(gòu)如下所示

1566310888924.png

因此在查找元素的時候龙优，需要一個一個的往下進(jìn)行遍歷羊异，那么復(fù)雜度也就和ArrayList中的E remove(int index)相同，因此彤断，也存在最好和最壞的情況野舶，最好的情況即為刪除最后一個元素，則復(fù)雜度為O(1)宰衙，最壞即為刪除最前面的一個元素平道，則復(fù)雜度為O(n)，平均復(fù)雜度也為O(n)

E set(int index, E element)

    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

在set(int index, E element)里面供炼，也調(diào)用了node(int index)一屋，那么復(fù)雜度和LinkedList中的E get(int index)相同

void add(int index, E element)

 public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == 0) {
          first =  new Node<E>(element,first);
        } else  {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element,prev.next);
        }
        size++;
    }

可以看出句伶，最好的情況為index == 0的情況，最壞的情況陆淀，則是找到最后一個元素，復(fù)雜度為O(n)先嬉，平均復(fù)雜度也為O(n)

E remove(int index)

    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        } else  {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

刪除節(jié)點(diǎn)的情況轧苫，最終也和添加節(jié)點(diǎn)的情況一樣，復(fù)雜度相同

所以最終的結(jié)果為下圖

1566992841371.png

• 動態(tài)數(shù)組add(E element)復(fù)雜度分析

    public void add(E element) {
        add(size,element);
    }

在這種情況下疫蔓，我們看到含懊，永遠(yuǎn)都是在size的位置進(jìn)行添加元素，這種情況不需要挪動元素衅胀，那么復(fù)雜度為O(1),不過也存在最壞復(fù)雜度的情況岔乔，就是擴(kuò)容的時候，即是O(n)滚躯，但是絕大多數(shù)情況是O(1),則平均復(fù)雜度可以視為O(1)雏门，在這種情況下，純在均攤復(fù)雜度掸掏，其均攤復(fù)雜度為O(1)

分析

假設(shè)此時有一個數(shù)組茁影，最大容量為4，那么在前面4次添加操作時丧凤，復(fù)雜度均為O(1)

1566993703821.png

但是當(dāng)我們繼續(xù)往下添加的時候募闲，就會擴(kuò)容，在擴(kuò)容時愿待，復(fù)雜度為O(4)

1566993749648.png

所以在此時浩螺，擴(kuò)容操作的復(fù)雜度就會均攤到前面4次添加操作中去，應(yīng)為擴(kuò)容與前面的添加操作存在關(guān)系

1566993895040.png

相當(dāng)于是每次add操作的次數(shù)為2仍侥，那么復(fù)雜度還是為O(1)

• 雙向鏈表

此前所介紹的鏈表要出，也叫做單向鏈表

使用雙向鏈表，可以提升鏈表的綜合性能

再前面單向鏈表的時候农渊，示意圖是這樣的

1567824839951.png

單向鏈表只有一條線厨幻，當(dāng)前節(jié)點(diǎn)指向的永遠(yuǎn)是其下一個節(jié)點(diǎn)，所以其缺點(diǎn)是只能重頭部往后面搜索

然而雙向鏈表腿时，當(dāng)中有一個指向上一個節(jié)點(diǎn)的指針况脆，可以通過下一個節(jié)點(diǎn)，找到上一個節(jié)點(diǎn)批糟，其示意圖是這樣的

1567825075829.png

如果當(dāng)前節(jié)點(diǎn)為頭節(jié)點(diǎn)格了，則該節(jié)點(diǎn)的prev指針指向null

同樣的，鏈表對象中徽鼎，就對應(yīng)的多了一個last指針盛末，該指針指向鏈表的位節(jié)點(diǎn)弹惦，鏈表對象如下所示

1567825194902.png

整個鏈表的示意圖這應(yīng)該是這樣的

1567825581248.png

有了雙向鏈表，那么我們查找元素可能會從兩個方向來進(jìn)行擦找悄但，一個是從頭節(jié)點(diǎn)開始查找棠隐，一個是從尾節(jié)點(diǎn)開始擦找

??什么時候從左往右開始找，什么時候從右往左開始找檐嚣，如何進(jìn)行判斷助泽？

查找節(jié)點(diǎn)

可以通過定位節(jié)點(diǎn)的索引，通過size進(jìn)行判斷嚎京，判斷方式如下

Node<E> node(int index) {
        rangeCheck(index);
        if (index < (size >> 1)) {
            //在左邊
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            //在右邊
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

清空鏈表

在單向鏈表時嗡贺，我們清空節(jié)點(diǎn)是直接將first指針置為null，那我們在雙向鏈表中鞍帝，如果同樣的把last置為null的話诫睬，會有問題存在嗎？我們先通過圖片進(jìn)行分析帕涌，清空鏈表的代碼如下

public void clear() {
    size = 0;
    first = null;
    last = null;
}

首先一個完整的鏈表是這樣的

1567825581248.png

當(dāng)我們把first和last都置為null之后摄凡，是這樣的

1567827407159.png

置空以后，就存在一個問題蚓曼，那么鏈表中的節(jié)點(diǎn)會被釋放掉嗎架谎？因為我們看到，現(xiàn)在每個節(jié)點(diǎn)辟躏，都有指針被上一個節(jié)點(diǎn)或者下一個節(jié)點(diǎn)引用著谷扣，其實在Java當(dāng)中，這種情況是會被釋放的捎琐，應(yīng)為在Java虛擬機(jī)當(dāng)中会涎，存在一個gc root對象，凡是沒有被gc root對象所引用的內(nèi)存瑞凑，都會被系統(tǒng)回收掉末秃。

那問題來了，什么樣的對象是gc root對象呢籽御？

在Java中练慕，只要被棧空間對象指向的對象技掏，屬于gc root對象铃将，由于我們在創(chuàng)建鏈表對象是是通過這種方式進(jìn)行創(chuàng)建的

List<Integer> list = new LinkedList<>();

其中通過new LinkedList<>()創(chuàng)建的對象，其內(nèi)存在堆空間當(dāng)中哑梳，而方法內(nèi)創(chuàng)建的局部變量List<Integer> list在椌⒀郑空間中，此時在楌妫空間的list引用著new LinkedList<>()內(nèi)存地址悯仙，那么通過new LinkedList<>()創(chuàng)建出來的對象龄毡，就叫做gc root對象。

知道什么叫做gc root對象以后锡垄，當(dāng)我們清空鏈表時沦零，將first和last引用都置為null之后，鏈表節(jié)點(diǎn)就不再有g(shù)c root對象引用著货岭，因此節(jié)點(diǎn)的內(nèi)存就會被系統(tǒng)回收掉路操，這就是Java虛擬機(jī)的做法。

鏈表的添加 add(int index, E element)

現(xiàn)在如下的一個雙向鏈表茴她，假設(shè)我們需要在節(jié)點(diǎn)為2的地方，添加節(jié)點(diǎn)

1567845965610.png

添加過程中的引用發(fā)生了如下變化

1567846273387.png

上面這種過程程奠，通過代碼表示為

Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev,element,next);
prev.next = node;
next.prev = node;

不過這種添加是比較通用的一種情況丈牢，那么假設(shè)我們現(xiàn)在添加的位置為序號為0的位置，那么應(yīng)該做特殊的處理瞄沙，應(yīng)為節(jié)點(diǎn)為0的prev為null己沛，因此需要特殊的處理

通過代碼表示為

Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev,element,next);
next.prev = node;
if (prev == null) {
    first = node;
} else  {
    prev.next = node;
}

1567847021486.png

同樣的，如果往最有一個位置添加元素距境，則需要特殊處理申尼，因此特殊處理代碼如下

Node<E> oldLast = last;
last = new Node<>(oldLast,element,null);
oldLast.next = last;

1567847631345.png

但是，這樣寫垫桂，還是存在問題师幕，即為鏈表當(dāng)中不純在任何節(jié)點(diǎn)的時候，Node<E> oldLast = last;為null诬滩，這種情況需要特俗處理霹粥，代碼為

Node<E> oldLast = last;
last = new Node<>(oldLast,element,null);
if (oldLast == null) {
    first = last;
} else  {
    oldLast.next = last;
}

1567847970263.png

完整的代碼邏輯是這樣的

public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast,element,null);
            if (oldLast == null) {
                first = last;
            } else  {
                oldLast.next = last;
            }
        } else  {
            Node<E> next = node(index);
            Node<E> prev = next.prev;
            Node<E> node = new Node<>(prev,element,next);
            next.prev = node;
            if (prev == null) {
                first = node;
            } else  {
                prev.next = node;
            }
        }
        size++;
    }

鏈表的刪除 E remove(int index)

同樣的，假設(shè)現(xiàn)在有如下的鏈表疼鸟，我們想要刪除下標(biāo)為2的節(jié)點(diǎn)

1567848382053.png

首先我們找到即將被刪除的節(jié)點(diǎn)后控，我們將即將被刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)中的next指向被刪除節(jié)點(diǎn)的next，被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)的prev指向被刪除節(jié)點(diǎn)的prev空镜，通過圖示表示為

1567848579979.png

通過這樣修改以后浩淘，node為2的節(jié)點(diǎn)，就從鏈表中成功的刪除吴攒，并且該節(jié)點(diǎn)不再有引用指向它张抄，其內(nèi)存最終被系統(tǒng)回收

1567848684927.png

代碼表示為：

public E remove(int index) {
        rangeCheck(index);
        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null) {//等價于index == 0
            first = next;
        } else  {
            prev.next = next;
        }
        if (next == null) {//等價于index == size - 1
            last = prev;
        } else  {
            next.prev = prev;
        }
        size--;
        return node.element;
    }

雙向鏈表 VS 單向鏈表

1567850759251.png

雙向鏈表 VS 動態(tài)數(shù)組

動態(tài)數(shù)組

• 開辟、銷毀內(nèi)存空間的次數(shù)相對較少洼怔，但是可能造成內(nèi)存空間的浪費(fèi)(可以通過縮容解決)

雙向鏈表

• 開辟欣鳖、銷毀內(nèi)存空間的次數(shù)相對較多，但不會造成內(nèi)存空間的浪費(fèi)

• 如果頻繁在尾部進(jìn)行添加茴厉、刪除操作泽台，動態(tài)數(shù)組什荣、雙向鏈表均可選擇
• 如果頻繁在頭部進(jìn)行添加、刪除操作怀酷， 建議選擇使用雙向鏈表
• 如果有頻繁的(在任意位置)進(jìn)行添加稻爬、刪除操作， 建議選擇使用雙向鏈表
• 如果有頻繁的查詢操作(隨機(jī)訪問操作)蜕依，建議選擇使用動態(tài)數(shù)組

不過桅锄，看到這里，我們不禁有疑問样眠，有了雙向鏈表友瘤，單向鏈表是否就沒有任何用處了呢？

并非如此檐束，在哈希表中的設(shè)計就用到了單向鏈表辫秧，至于原因，我會在哈希表章節(jié)中詳細(xì)說明被丧。

demo源碼下載地址

本節(jié)完盟戏！