概念

鏈表的插入，只需要上一個(gè)節(jié)點(diǎn)的指針指向這個(gè)新增的節(jié)點(diǎn)篡腌，新增的節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)碱璃。
刪除類似操作弄痹。

鏈表當(dāng)前節(jié)點(diǎn)只知道下個(gè)節(jié)點(diǎn)是誰，也并非連續(xù)存儲嵌器，隨機(jī)訪問元素時(shí)需要將整個(gè)鏈表遍歷來查找元素肛真。

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

單鏈表

單鏈表有頭結(jié)點(diǎn)和尾結(jié)點(diǎn)爽航。頭結(jié)點(diǎn)用來記錄鏈表的基地址蚓让，尾結(jié)點(diǎn)指向空地址null庇谆。

循環(huán)鏈表

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

雙向鏈表

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

跳表

思路：升維思想饶囚，空間換時(shí)間

如果要插入一個(gè)值是4的新節(jié)點(diǎn)，就不用8鸠补，7萝风，6，5紫岩，3這樣的查詢.可以7规惰，5，3這樣的查詢泉蝌。
這是一層節(jié)點(diǎn)歇万，還可以繼續(xù)擴(kuò)充成多層節(jié)點(diǎn)，提取的極限就是同一層就有兩個(gè)節(jié)點(diǎn)的時(shí)候勋陪。
這種方式隨機(jī)訪問的時(shí)間復(fù)雜度降到了O(logn)
空間復(fù)雜度O(n)

鏈表的優(yōu)缺點(diǎn)

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

不同鏈表比較

鏈表刪除

• 刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)轧飞；
• 刪除給定指針指向的結(jié)點(diǎn)衅鹿。

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

有序列表的查詢

對于一個(gè)有序鏈表振愿，雙向鏈表的按值查詢的效率也要比單鏈表高一些捷犹。因?yàn)椋覀兛梢杂涗浬洗尾檎业奈恢胮冕末，每次查詢時(shí)伏恐，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找栓霜，所以平均只需要查找一半的數(shù)據(jù)翠桦。

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

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

如何寫鏈表代碼

理解指針或引用的含義

p->next=q呆馁。這行代碼是說桐经，p結(jié)點(diǎn)中的next指針存儲了q結(jié)點(diǎn)的內(nèi)存地址。
p->next=p->next->next浙滤。這行代碼表示阴挣，p結(jié)點(diǎn)的next指針存儲了p結(jié)點(diǎn)的下下一個(gè)結(jié)點(diǎn)的內(nèi)存地址。

防止指針丟失的情況

指針p指向節(jié)點(diǎn)A纺腊，需求想要在節(jié)點(diǎn)A畔咧，B中插入節(jié)點(diǎn)X茎芭。

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

這種寫法是錯(cuò)誤的梅桩，因?yàn)榈谝恍写a，P節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)位置已經(jīng)指向到x拜隧，不再指向B了宿百。所以第二行變成了X節(jié)點(diǎn)指向了自己，鏈表從此斷了虹蓄。
正確寫法是1和2顛倒過來，先把x的下一個(gè)節(jié)點(diǎn)指向B幸撕，再把A的下一個(gè)節(jié)點(diǎn)指向x薇组。

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

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

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

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

2.添加頭節(jié)點(diǎn)

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

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

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

4.刪除最后一個(gè)節(jié)點(diǎn)

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

這種方式很容易出錯(cuò)，需要引入哨兵節(jié)點(diǎn)貌矿，在任何時(shí)候炭菌，不管鏈表是不是空，head指針都會一直指向這個(gè)哨兵結(jié)點(diǎn)逛漫。我們也把這種有哨兵結(jié)點(diǎn)的鏈表叫帶頭鏈表黑低。相反，沒有哨兵結(jié)點(diǎn)的鏈表就叫作不帶頭鏈表酌毡。哨兵結(jié)點(diǎn)是不存儲數(shù)據(jù)的克握。

// 在數(shù)組a中，查找key枷踏，返回key所在的位置
// 其中菩暗，n表示數(shù)組a的長度
// 我舉2個(gè)例子，你可以拿例子走一下代碼
// 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;
  }
  
  // 這里因?yàn)橐獙[n-1]的值替換成key旭蠕，所以要特殊處理這個(gè)值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把a(bǔ)[n-1]的值臨時(shí)保存在變量tmp中停团，以便之后恢復(fù)。tmp=6掏熬。
  // 之所以這樣做的目的是：希望find()代碼不要改變a數(shù)組中的內(nèi)容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中佑稠，此時(shí)a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循環(huán)比起代碼一，少了i<n這個(gè)比較操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢復(fù)a[n-1]原來的值,此時(shí)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;
  }
}

重點(diǎn)留意邊界條件處理

如果鏈表為空時(shí)辆琅，代碼是否能正常工作漱办？
如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作婉烟？
如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)娩井，代碼是否能正常工作？
代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候似袁，是否能正常工作洞辣？

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é)點(diǎn)

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

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

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

void linkLast(E var1) {
    LinkedList.Node var2 = this.last;
    // 當(dāng)前節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)是之前鏈表的尾節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)是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é)點(diǎn)，刪除給定節(jié)點(diǎn)挺峡。刪除操作會把節(jié)點(diǎn)的值兼搏，前后指向節(jié)點(diǎn)都置為null，幫助GC進(jìn)行回收沙郭。
remove(Object o)
添加沒有特殊判斷佛呻，可以添加null，刪除也可以刪除null病线。
從頭節(jié)點(diǎn)向尾節(jié)點(diǎn)遍歷吓著，刪除null，判斷節(jié)點(diǎn)數(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é)點(diǎn)就是頭節(jié)點(diǎn)
    if (prev == null) {
        // 下一個(gè)節(jié)點(diǎn)作為頭節(jié)點(diǎn)
        first = next;
    } else {
        // 前一個(gè)節(jié)點(diǎn)的尾指針指向下一個(gè)節(jié)點(diǎn)
        prev.next = next;
        // 當(dāng)前節(jié)點(diǎn)的頭節(jié)點(diǎn)置空
        x.prev = null;
    }

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

remove(int index)
需要找到這個(gè)index對應(yīng)的節(jié)點(diǎn)信息惕耕，通過上面的刪除方式刪除節(jié)點(diǎn)纺裁。

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

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

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

迭代器

從頭到尾方式迭代栋豫。

hashNext方法

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

next方法

public E next() {
    this.checkForComodification();
    if (!this.hasNext()) {
        throw new NoSuchElementException();
    } else {
        // 當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)
        this.lastReturned = this.next;
        // next是下一個(gè)節(jié)點(diǎn)了，為下次迭代做準(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é)點(diǎn)
        LinkedList.this.unlink(this.lastReturned);
        if (this.next == this.lastReturned) {
            this.next = var1;
        } else {
            --this.nextIndex;
        }

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