鏈表和數(shù)組是數(shù)據(jù)類型中兩個(gè)重要又常用的基礎(chǔ)數(shù)據(jù)類型。

數(shù)組是連續(xù)存儲(chǔ)在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，因此它的優(yōu)勢(shì)是可以通過(guò)下標(biāo)迅速的找到元素的位置，而它的缺點(diǎn)則是在插入和刪除元素時(shí)會(huì)導(dǎo)致大量元素的被迫移動(dòng)，為了解決和平衡此問(wèn)題于是就有了鏈表這種數(shù)據(jù)類型。

看過(guò)某些抗日神劇我們都知道，某些秘密組織為了防止組織的成員被“一窩端”，通常會(huì)采用上下級(jí)單線聯(lián)系的方式來(lái)保護(hù)其他成員，而這種“行為”則是鏈表的主要特征。

簡(jiǎn)介

鏈表（Linked List）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針（Pointer）。

復(fù)雜度分析

由于鏈表無(wú)需按順序存儲(chǔ)，因此鏈表在插入的時(shí)可以達(dá)到 O(1) 的復(fù)雜度，比順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要 O(n) 的時(shí)間，而順序表插入和查詢的時(shí)間復(fù)雜度分別是 O(log n) 和 O(1)。

優(yōu)缺點(diǎn)分析

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷比較大。

分類

鏈表通常會(huì)分為以下三類：

• 單向鏈表
• 雙向鏈表
• 循環(huán)鏈表
• 單循鏈表
• 雙循環(huán)鏈表

1.單向鏈表

單鏈表的遍歷方向單一，只能從鏈頭一直遍歷到鏈尾。它的缺點(diǎn)是當(dāng)要查詢某一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)時(shí)，只能再次從頭進(jìn)行遍歷查詢，因此效率比較低，而雙向鏈表的出現(xiàn)恰好解決了這個(gè)問(wèn)題。

接下來(lái)，我們用代碼來(lái)實(shí)現(xiàn)一下單向鏈表的節(jié)點(diǎn)：

private?static?class?Node<E>?{
????E?item;
????Node?next;

????Node(E?element,?Node?next)?{
????????this.item?=?element;
????????this.next?=?next;
????}
}

2.雙向鏈表

接下來(lái)，我們用代碼來(lái)實(shí)現(xiàn)一下雙向鏈表的節(jié)點(diǎn)：

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

????Node(Node?prev,?E?element,?Node?next)?{
????????this.item?=?element;
????????this.next?=?next;
????????this.prev?=?prev;
????}
}

3.循環(huán)鏈表

循環(huán)鏈表又分為單循環(huán)鏈表和雙循環(huán)鏈表，也就是將單向鏈表或雙向鏈表的首尾節(jié)點(diǎn)進(jìn)行連接，這樣就實(shí)現(xiàn)了單循環(huán)鏈表或雙循環(huán)鏈表了，如下圖所示：

Java中的鏈表

學(xué)習(xí)了鏈表的基礎(chǔ)知識(shí)之后，我們來(lái)思考一個(gè)問(wèn)題：Java 中的鏈表 LinkedList 是屬于哪種類型的鏈表呢？單向鏈表還是雙向鏈表？

要回答這個(gè)問(wèn)題，首先我們要來(lái)看 JDK 中的源碼，如下所示：

package?java.util;

import?java.util.function.Consumer;

public?class?LinkedList<E>
????extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable
{
?//?鏈表大小
????transient?int?size?=?0;

????//?鏈表頭部
????transient?Node?first;

????//?鏈表尾部
????transient?Node?last;

????public?LinkedList()?{
????}

????public?LinkedList(Collection?c)?{
????????this();
????????addAll(c);
????}
?
????//?獲取頭部元素
????public?E?getFirst()?{
????????final?Node?f?=?first;
????????if?(f?==?null)
????????????throw?new?NoSuchElementException();
????????return?f.item;
????}

????//?獲取尾部元素
????public?E?getLast()?{
????????final?Node?l?=?last;
????????if?(l?==?null)
????????????throw?new?NoSuchElementException();
????????return?l.item;
????}

????//?刪除頭部元素
????public?E?removeFirst()?{
????????final?Node?f?=?first;
????????if?(f?==?null)
????????????throw?new?NoSuchElementException();
????????return?unlinkFirst(f);
????}

????//?刪除尾部元素
????public?E?removeLast()?{
????????final?Node?l?=?last;
????????if?(l?==?null)
????????????throw?new?NoSuchElementException();
????????return?unlinkLast(l);
????}

????//?添加頭部元素
????public?void?addFirst(E?e)?{
????????linkFirst(e);
????}
????
????//?添加頭部元素的具體執(zhí)行方法
????private?void?linkFirst(E?e)?{
????????final?Node?f?=?first;
????????final?Node?newNode?=?new?Node<>(null,?e,?f);
????????first?=?newNode;
????????if?(f?==?null)
????????????last?=?newNode;
????????else
????????????f.prev?=?newNode;
????????size++;
????????modCount++;
????}

????//?添加尾部元素
????public?void?addLast(E?e)?{
????????linkLast(e);
????}
????
????//?添加尾部元素的具體方法
????void?linkLast(E?e)?{
????????final?Node?l?=?last;
????????final?Node?newNode?=?new?Node<>(l,?e,?null);
????????last?=?newNode;
????????if?(l?==?null)
????????????first?=?newNode;
????????else
????????????l.next?=?newNode;
????????size++;
????????modCount++;
????}

????//?查詢鏈表個(gè)數(shù)
????public?int?size()?{
????????return?size;
????}

????//?清空鏈表
????public?void?clear()?{
????????for?(Node?x?=?first;?x?!=?null;?)?{
????????????Node?next?=?x.next;
????????????x.item?=?null;
????????????x.next?=?null;
????????????x.prev?=?null;
????????????x?=?next;
????????}
????????first?=?last?=?null;
????????size?=?0;
????????modCount++;
????}
??
????//?根據(jù)下標(biāo)獲取元素
????public?E?get(int?index)?{
????????checkElementIndex(index);
????????return?node(index).item;
????}

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

????????Node(Node?prev,?E?element,?Node?next)?{
????????????this.item?=?element;
????????????this.next?=?next;
????????????this.prev?=?prev;
????????}
????}
????//?忽略其他方法......
}

從上述節(jié)點(diǎn) Node? 的定義可以看出：LinkedList 其實(shí)是一個(gè)雙向鏈表，因?yàn)樗x了兩個(gè)指針 next?和 prev?分別用來(lái)指向自己的下一個(gè)和上一個(gè)節(jié)點(diǎn)。

鏈表常用方法

LinkedList 的設(shè)計(jì)還是很巧妙的，了解了它的實(shí)現(xiàn)代碼之后，下面我們來(lái)看看它是如何使用的？或者說(shuō)它的常用方法有哪些。

1.增加

接下來(lái)我們來(lái)演示一下增加方法的使用：

public?class?LinkedListTest?{
????public?static?void?main(String[]?a)?{
????????LinkedList?list?=?new?LinkedList();
????????list.add("Java");
????????list.add("中文");
????????list.add("社群");
????????list.addFirst("頭部添加");?//?添加元素到頭部
????????list.addLast("尾部添加");??//?添加元素到最后
????????System.out.println(list);
????}
}

以上代碼的執(zhí)行結(jié)果為：

[頭部添加, Java, 中文, 社群, 尾部添加]

出來(lái)以上的 3 個(gè)增加方法之外，LinkedList 還包含了其他的添加方法，如下所示：

• add(int index, E element)：向指定位置插入元素；
• offer(E e)：向鏈表末尾添加元素，返回是否成功；
• offerFirst(E e)：頭部插入元素，返回是否成功；
• offerLast(E e)：尾部插入元素，返回是否成功。

add 和 offer 的區(qū)別

它們的區(qū)別主要體現(xiàn)在以下兩點(diǎn)：

• offer 方法屬于 Deque 接口，add 方法屬于 Collection 的接口；
• 當(dāng)隊(duì)列添加失敗時(shí)，如果使用 add 方法會(huì)報(bào)錯(cuò)，而 offer 方法會(huì)返回 false。

2.刪除

刪除功能的演示代碼如下：

import?java.util.LinkedList;

public?class?LinkedListTest?{
????public?static?void?main(String[]?a)?{
????????LinkedList?list?=?new?LinkedList();
????????list.offer("頭部");
????????list.offer("中間");
????????list.offer("尾部");

????????list.removeFirst();?//?刪除頭部元素
????????list.removeLast();??//?刪除尾部元素

????????System.out.println(list);
????}
}

以上代碼的執(zhí)行結(jié)果為：

[中間]

除了以上刪除方法之外，更多的刪除方法如下所示：

• clear()：清空鏈表；
• removeFirst()：刪除并返回第一個(gè)元素；
• removeLast()：刪除并返回最后一個(gè)元素；
• remove(Object o)：刪除某一元素，返回是否成功；
• remove(int index)：刪除指定位置的元素；
• poll()：刪除并返回第一個(gè)元素；
• remove()：刪除并返回第一個(gè)元素。

3.修改

修改方法的演示代碼如下：

import?java.util.LinkedList;

public?class?LinkedListTest?{
????public?static?void?main(String[]?a)?{
????????LinkedList?list?=?new?LinkedList();
????????list.offer("Java");
????????list.offer("MySQL");
????????list.offer("DB");
????????
????????//?修改
????????list.set(2,?"Oracle");

????????System.out.println(list);
????}
}

以上代碼的執(zhí)行結(jié)果為：

[Java, MySQL, Oracle]

4.查詢

查詢方法的演示代碼如下：

import?java.util.LinkedList;

public?class?LinkedListTest?{
????public?static?void?main(String[]?a)?{
????????LinkedList?list?=?new?LinkedList();
????????list.offer("Java");
????????list.offer("MySQL");
????????list.offer("DB");

????????//?---?getXXX()?獲取?---
????????//?獲取最后一個(gè)
????????System.out.println(list.getLast());
????????//?獲取首個(gè)
????????System.out.println(list.getFirst());
????????//?根據(jù)下標(biāo)獲取
????????System.out.println(list.get(1));

????????//?peekXXX()?獲取
????????System.out.println("---?peek()?---");
????????//?獲取最后一個(gè)
????????System.out.println(list.peekLast());
????????//?獲取首個(gè)
????????System.out.println(list.peekFirst());
????????//?根據(jù)首個(gè)
????????System.out.println(list.peek());
????}
}

以上代碼的執(zhí)行結(jié)果為：

DB

Java

MySQL

--- peek() ---

DB

Java

Java

5.遍歷

LinkedList 的遍歷方法包含以下三種。

遍歷方法一：

for?(int?size?=?linkedList.size(),?i?=?0;?i?????System.out.println(linkedList.get(i));
}

遍歷方法二：

for?(String?str:?linkedList)?{
????System.out.println(str);
}

遍歷方法三：

Iterator?iter?=?linkedList.iterator();
while?(iter.hasNext())?{
????System.out.println(iter.next());
}

鏈表應(yīng)用：隊(duì)列 & 棧

1.用鏈表實(shí)現(xiàn)棧

接下來(lái)我們用鏈表來(lái)實(shí)現(xiàn)一個(gè)先進(jìn)先出的“隊(duì)列”，實(shí)現(xiàn)代碼如下：

LinkedList?list?=?new?LinkedList();
//?元素入列
list.add("Java");
list.add("中文");
list.add("社群");

while?(!list.isEmpty())?{
????//?打印并移除隊(duì)頭元素
????System.out.println(list.poll());
}

以上程序的執(zhí)行結(jié)果如下：

Java

中文

社群

2.用鏈表實(shí)現(xiàn)隊(duì)列

然后我們用鏈表來(lái)實(shí)現(xiàn)一個(gè)后進(jìn)先出的“?！?，實(shí)現(xiàn)代碼如下：

LinkedList?list?=?new?LinkedList();
//?元素入棧
list.add("Java");
list.add("中文");
list.add("社群");

while?(!list.isEmpty())?{
????//?打印并移除棧頂元素
????System.out.println(list.pollLast());
}

以上程序的執(zhí)行結(jié)果如下：

社群

中文

Java

鏈表使用場(chǎng)景

鏈表作為一種基本的物理結(jié)構(gòu)，常被用來(lái)構(gòu)建許多其它的邏輯結(jié)構(gòu)，如堆棧、隊(duì)列都可以基于鏈表實(shí)現(xiàn)。

所謂的物理結(jié)構(gòu)是指可以將數(shù)據(jù)存儲(chǔ)在物理空間中，比如數(shù)組和鏈表都屬于物理數(shù)據(jù)結(jié)構(gòu)；而邏輯結(jié)構(gòu)則是用于描述數(shù)據(jù)間的邏輯關(guān)系的，它可以由多種不同的物理結(jié)構(gòu)來(lái)實(shí)現(xiàn)，比如隊(duì)列和棧都屬于邏輯結(jié)構(gòu)。

鏈表常見(jiàn)筆試題

鏈表最常見(jiàn)的筆試題就是鏈表的反轉(zhuǎn)了，之前的文章《鏈表反轉(zhuǎn)的兩種實(shí)現(xiàn)方法，后一種擊敗了100%的用戶！》我們提供了 2 種鏈表反轉(zhuǎn)的方法，而本文我們?cè)賮?lái)擴(kuò)充一下，提供 3 種鏈表反轉(zhuǎn)的方法。

實(shí)現(xiàn)方法 1：Stack

我們先用圖解的方式來(lái)演示一下，使用棧實(shí)現(xiàn)鏈表反轉(zhuǎn)的具體過(guò)程，如下圖所示。

全部入棧：因?yàn)闂Ｊ窍冗M(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，因此它的執(zhí)行過(guò)程如下圖所示：最終的執(zhí)行結(jié)果如下圖所示：實(shí)現(xiàn)代碼如下所示：

public?ListNode?reverseList(ListNode?head)?{
????if?(head?==?null)?return?null;
????Stack?stack?=?new?Stack<>();
????stack.push(head);?//?存入第一個(gè)節(jié)點(diǎn)
????while?(head.next?!=?null)?{
????????stack.push(head.next);?//?存入其他節(jié)點(diǎn)
????????head?=?head.next;?//?指針移動(dòng)的下一位
????}
????//?反轉(zhuǎn)鏈表
????ListNode?listNode?=?stack.pop();?//?反轉(zhuǎn)第一個(gè)元素
????ListNode?lastNode?=?listNode;?//?臨時(shí)節(jié)點(diǎn)，在下面的?while?中記錄上一個(gè)節(jié)點(diǎn)
????while?(!stack.isEmpty())?{
????????ListNode?item?=?stack.pop();?//?當(dāng)前節(jié)點(diǎn)
????????lastNode.next?=?item;
????????lastNode?=?item;
????}
????lastNode.next?=?null;?//?最后一個(gè)節(jié)點(diǎn)賦為null（不然會(huì)造成死循環(huán)）
????return?listNode;
}

實(shí)現(xiàn)方法 2：遞歸

同樣的，我們先用圖解的方式來(lái)演示一下，此方法實(shí)現(xiàn)的具體過(guò)程，如下圖所示。

實(shí)現(xiàn)代碼如下所示：

public?static?ListNode?reverseList(ListNode?head)?{
????if?(head?==?null?||?head.next?==?null)?return?head;
????//?從下一個(gè)節(jié)點(diǎn)開(kāi)始遞歸
????ListNode?reverse?=?reverseList(head.next);
????head.next.next?=?head;?//?設(shè)置下一個(gè)節(jié)點(diǎn)的?next?為當(dāng)前節(jié)點(diǎn)
????head.next?=?null;?//?把當(dāng)前節(jié)點(diǎn)的?next?賦值為?null，避免循環(huán)引用
????return?reverse;
}

LeetCode 驗(yàn)證結(jié)果如下圖所示：

可以看出這種實(shí)現(xiàn)方法在執(zhí)行效率方面已經(jīng)滿足我們的需求了，性能還是很高的。

實(shí)現(xiàn)方法 3：循環(huán)

我們也可以通過(guò)循環(huán)的方式來(lái)實(shí)現(xiàn)鏈表反轉(zhuǎn)，只是這種方法無(wú)需重復(fù)調(diào)用自身方法，只需要一個(gè)循環(huán)就搞定了，實(shí)現(xiàn)代碼如下：

class?Solution?{
????public?ListNode?reverseList(ListNode?head)?{
????????if?(head?==?null)?return?null;
????????//?最終排序的倒序鏈表
????????ListNode?prev?=?null;
????????while?(head?!=?null)?{
????????????//?循環(huán)的下個(gè)節(jié)點(diǎn)
????????????ListNode?next?=?head.next;
????????????//?反轉(zhuǎn)節(jié)點(diǎn)操作
????????????head.next?=?prev;
????????????//?存儲(chǔ)下個(gè)節(jié)點(diǎn)的上個(gè)節(jié)點(diǎn)
????????????prev?=?head;
????????????//?移動(dòng)指針到下一個(gè)循環(huán)
????????????head?=?next;
????????}
????????return?prev;
????}
}

LeetCode 驗(yàn)證結(jié)果如下圖所示：

從上述圖片可以看出，使用此方法在時(shí)間復(fù)雜度和空間復(fù)雜度上都是目前的最優(yōu)解，比之前的兩種方法更加理想。

總結(jié)

本文我們講了鏈表的定義，它是由數(shù)據(jù)域和指針域兩部分組成的。鏈表可分為：?jiǎn)蜗蜴湵?、雙向鏈表和循環(huán)鏈表，其中循環(huán)鏈表又可以分為單循鏈表和雙循環(huán)鏈表。通過(guò) JDK 的源碼可知，Java 中的 LinkedList 其實(shí)是雙向鏈表，我們可以使用它來(lái)實(shí)現(xiàn)隊(duì)列或者棧，最后我們講了反轉(zhuǎn)鏈表的 3 種實(shí)現(xiàn)方法，希望本文的內(nèi)容對(duì)你有幫助。