概念

鏈表的插入，只需要上一個節(jié)點的指針指向這個新增的節(jié)點，新增的節(jié)點指向下一個節(jié)點。
刪除類似操作。

鏈表當(dāng)前節(jié)點只知道下個節(jié)點是誰，也并非連續(xù)存儲，隨機訪問元素時需要將整個鏈表遍歷來查找元素。

添加和刪除時間復(fù)雜度：O(1)，隨機查詢時間復(fù)雜度：O(n)

單鏈表

單鏈表有頭結(jié)點和尾結(jié)點。頭結(jié)點用來記錄鏈表的基地址，尾結(jié)點指向空地址null。

循環(huán)鏈表

跟單鏈表的區(qū)別就在于尾結(jié)點，單鏈表的尾結(jié)點指針指向空地址，表示這就是最后的結(jié)點了。而循環(huán)鏈表的尾結(jié)點指針是指向鏈表的頭結(jié)點。
當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點時，就特別適合采用循環(huán)鏈表。

雙向鏈表

雙向鏈表需要額外的兩個空間來存儲后繼結(jié)點和前驅(qū)結(jié)點的地址。所以，如果存儲同樣多的數(shù)據(jù)，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。雖然兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。

跳表

思路：升維思想，空間換時間

如果要插入一個值是4的新節(jié)點，就不用8，7，6，5，3這樣的查詢.可以7，5，3這樣的查詢。
這是一層節(jié)點，還可以繼續(xù)擴充成多層節(jié)點，提取的極限就是同一層就有兩個節(jié)點的時候。
這種方式隨機訪問的時間復(fù)雜度降到了O(logn)
空間復(fù)雜度O(n)

鏈表的優(yōu)缺點

優(yōu)點：
鏈表本身沒有大小的限制，天然地支持動態(tài)擴容。
缺點：
鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法有效預(yù)讀。
對鏈表進行頻繁的插入、刪除操作，還會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，有可能會導(dǎo)致頻繁的 GC。
鏈表中的每個結(jié)點都需要消耗額外的存儲空間去存儲一份指向下一個結(jié)點的指針，所以內(nèi)存消耗會翻倍。

不同鏈表比較

鏈表刪除

• 刪除結(jié)點中“值等于某個給定值”的結(jié)點；
• 刪除給定指針指向的結(jié)點。

雖然單純的刪除時間復(fù)雜度是O(1)，但是要查找刪除的元素是個比較麻煩的問題，鏈表的隨機訪問元素時間復(fù)雜度是O(n)。
第一種情況，需要從頭開始遍歷鏈表來找到值等于給定值的結(jié)點。
第二種情況，我們已經(jīng)找到了要刪除的結(jié)點，但是刪除某個結(jié)點q需要知道其前驅(qū)結(jié)點，進行尾結(jié)點指向改變來控制刪除操作。這種情況單鏈表不知道前驅(qū)節(jié)點，查詢時間復(fù)雜度是O(n)，而對于雙向鏈表時間復(fù)雜度是O(1)。
插入也是一致。

有序列表的查詢

對于一個有序鏈表，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因為，我們可以記錄上次查找的位置p，每次查詢時，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。

如何選取用單向鏈表還是雙向鏈表

當(dāng)內(nèi)存空間充足的時候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對較高、但時間復(fù)雜度相對很低的算法或者數(shù)據(jù)結(jié)構(gòu)。相反，如果內(nèi)存比較緊缺，比如代碼跑在手機或者單片機上，這個時候，就要反過來用時間換空間的設(shè)計思路。
使用緩存就是空間換時間的設(shè)計思想。

如何寫鏈表代碼

理解指針或引用的含義

p->next=q。這行代碼是說，p結(jié)點中的next指針存儲了q結(jié)點的內(nèi)存地址。
p->next=p->next->next。這行代碼表示，p結(jié)點的next指針存儲了p結(jié)點的下下一個結(jié)點的內(nèi)存地址。

防止指針丟失的情況

指針p指向節(jié)點A，需求想要在節(jié)點A，B中插入節(jié)點X。

p->next = x;  // 將p的next指針指向x結(jié)點；
x->next = p->next;  // 將x的結(jié)點的next指針指向b結(jié)點；

這種寫法是錯誤的，因為第一行代碼，P節(jié)點下一個節(jié)點位置已經(jīng)指向到x，不再指向B了。所以第二行變成了X節(jié)點指向了自己，鏈表從此斷了。
正確寫法是1和2顛倒過來，先把x的下一個節(jié)點指向B，再把A的下一個節(jié)點指向x。

如果是刪除，注意C的話要釋放內(nèi)存，防止內(nèi)存泄漏。

特殊節(jié)點的添加和刪除

1.正常節(jié)點的添加

// 新建的節(jié)點尾節(jié)點指向p的下一個節(jié)點 
new_node->next = p->next;
// p的尾節(jié)點指向新節(jié)點
p->next = new_node;

2.添加頭節(jié)點

if (head == null) {
  head = new_node;
}

3.正常節(jié)點的刪除

p->next = p->next->next;

4.刪除最后一個節(jié)點

if (head->next == null) {
   head = null;
}

這種方式很容易出錯，需要引入哨兵節(jié)點，在任何時候，不管鏈表是不是空，head指針都會一直指向這個哨兵結(jié)點。我們也把這種有哨兵結(jié)點的鏈表叫帶頭鏈表。相反，沒有哨兵結(jié)點的鏈表就叫作不帶頭鏈表。哨兵結(jié)點是不存儲數(shù)據(jù)的。

// 在數(shù)組a中，查找key，返回key所在的位置
// 其中，n表示數(shù)組a的長度
// 我舉2個例子，你可以拿例子走一下代碼
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 這里因為要將a[n-1]的值替換成key，所以要特殊處理這個值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把a[n-1]的值臨時保存在變量tmp中，以便之后恢復(fù)。tmp=6。
  // 之所以這樣做的目的是：希望find()代碼不要改變a數(shù)組中的內(nèi)容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中，此時a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循環(huán)比起代碼一，少了i<n這個比較操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢復(fù)a[n-1]原來的值,此時a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果i == n-1說明，在0...n-2之間都沒有key，所以返回-1
    return -1;
  } else {
    // 否則，返回i，就是等于key值的元素的下標(biāo)
    return i;
  }
}

重點留意邊界條件處理

如果鏈表為空時，代碼是否能正常工作？
如果鏈表只包含一個結(jié)點時，代碼是否能正常工作？
如果鏈表只包含兩個結(jié)點時，代碼是否能正常工作？
代碼邏輯在處理頭結(jié)點和尾結(jié)點的時候，是否能正常工作？

LinkedList源碼

底層數(shù)據(jù)結(jié)構(gòu)雙向鏈表。鏈表中的元素是Node。

private static class Node<E> {
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

    Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
        this.item = var2;
        this.next = var3;
        this.prev = var1;
    }
}

增加

可以從頭部增加，也可以從尾部增加。默認(rèn)add從尾部增加。
1.從頭部增加節(jié)點

private void linkFirst(E var1) {
    LinkedList.Node var2 = this.first;
    // 創(chuàng)建的節(jié)點，前一個是null，當(dāng)前節(jié)點是var1，尾節(jié)點是var2
    LinkedList.Node var3 = new LinkedList.Node((LinkedList.Node)null, var1, var2);
    // 新建的節(jié)點作為頭節(jié)點
    this.first = var3;
    // 如果之前沒有頭節(jié)點，意味著之前鏈表為空，當(dāng)前添加元素，頭節(jié)點，尾節(jié)點都是同一個節(jié)點
    if (var2 == null) {
        this.last = var3;
    } else {
        var2.prev = var3;
    }

    ++this.size;
    ++this.modCount;
}

2.從尾部增加節(jié)點

void linkLast(E var1) {
    LinkedList.Node var2 = this.last;
    // 當(dāng)前節(jié)點上一個節(jié)點是之前鏈表的尾節(jié)點，下一個節(jié)點是null
    LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
    this.last = var3;

    if (var2 == null) {
        this.first = var3;
    } else {
        var2.next = var3;
    }

    ++this.size;
    ++this.modCount;
}

刪除

可以選擇從頭部刪除，也可以選擇從尾部刪除，給定index刪除節(jié)點，刪除給定節(jié)點。刪除操作會把節(jié)點的值，前后指向節(jié)點都置為null，幫助GC進行回收。
remove(Object o)
添加沒有特殊判斷，可以添加null，刪除也可以刪除null。
從頭節(jié)點向尾節(jié)點遍歷，刪除null，判斷節(jié)點數(shù)據(jù)是否為null。
刪除其余元素，通過equals判斷值是否相同。

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 刪除的節(jié)點就是頭節(jié)點
    if (prev == null) {
        // 下一個節(jié)點作為頭節(jié)點
        first = next;
    } else {
        // 前一個節(jié)點的尾指針指向下一個節(jié)點
        prev.next = next;
        // 當(dāng)前節(jié)點的頭節(jié)點置空
        x.prev = null;
    }

    if (next == null) {
        // 上一個節(jié)點置空
        last = prev;
    } else {
        next.prev = prev;
        // 當(dāng)前節(jié)點的尾節(jié)點為空
        x.next = null;
    }
    // 刪除的節(jié)點數(shù)據(jù)為空
    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(int index)
需要找到這個index對應(yīng)的節(jié)點信息，通過上面的刪除方式刪除節(jié)點。

Node<E> node(int index) {
    // 二分
    if (index < (size >> 1)) {
        // 獲取到頭節(jié)點，根據(jù)index一直向下獲取
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 獲取到尾節(jié)點根據(jù)index向上獲取
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

remove()
相當(dāng)于刪除鏈表頭節(jié)點元素

private E unlinkFirst(Node<E> f) {
    // 獲取要刪除節(jié)點的下個條目和當(dāng)前條目
    final E element = f.item;
    final Node<E> next = f.next;
    // 清空要刪除節(jié)點的內(nèi)容，把它的尾指針指空
    f.item = null;
    f.next = null; // help GC
    // 頭節(jié)點的下個節(jié)點成為頭節(jié)點
    first = next;
    // 當(dāng)個鏈表只有一個節(jié)點
    if (next == null)
        last = null;
    else
        // 頭節(jié)點的下個節(jié)點頭指針指向null，它要成為頭節(jié)點
        next.prev = null;
    size--;
    modCount++;
    return element;
}

迭代器

從頭到尾方式迭代。

hashNext方法

public boolean hasNext() {
    // 下一個節(jié)點的索引小于鏈表的大小
    return this.nextIndex < LinkedList.this.size;
}

next方法

public E next() {
    this.checkForComodification();
    if (!this.hasNext()) {
        throw new NoSuchElementException();
    } else {
        // 當(dāng)前要刪除的節(jié)點
        this.lastReturned = this.next;
        // next是下一個節(jié)點了，為下次迭代做準(zhǔn)備
        this.next = this.next.next;
        ++this.nextIndex;
        return this.lastReturned.item;
    }
}

remove方法

public void remove() {
    this.checkForComodification();
    if (this.lastReturned == null) {
        throw new IllegalStateException();
    } else {
        LinkedList.Node var1 = this.lastReturned.next;
        // 刪除當(dāng)前節(jié)點
        LinkedList.this.unlink(this.lastReturned);
        if (this.next == this.lastReturned) {
            this.next = var1;
        } else {
            --this.nextIndex;
        }

        this.lastReturned = null;
        ++this.expectedModCount;
    }
}