1.數組

1.1：概念

數組是一種線性表數據結構，它用一組連續的內存空間，來存儲一組具有相同類型的數據。這里我們要抽取出三個跟數組相關的關鍵詞：線性表，連續內存空間，相同數據類型；數組具有連續的內存空間，存儲相同類型的數據，正是該特性使得數組具有一個特性：隨機訪問。但是有利有弊，這個特性雖然使得訪問數組邊得非常容易但是也使得數組插入和刪除操作會變得很低效，插入和刪除數據后為了保證連續性，要做很多數據搬遷工作。

1.2：邏輯結構和物理結構

所謂的數組的邏輯結構指的是我們可以用什么的表示方式來描述數組元素，比如有一個數組 a,數組中有 n 個元素，我們可以用(a1,a2,a3,.....an)來描述數組中的每個元素，當然后面我們會將具體如何訪問數組中的每個元素。數組的物理結構指的是數組元素實際的存儲形式，當然了從概念我們可以看出數組的物理存儲空間是一塊連續的內存單已，為了說明白這個事情，這里給大家準備了一副圖

?

從圖中我們可以看出訪問數組中的元素是通過下標來訪問的，那是如何做到的呢？

1.2.1：數組元素的訪問

我們拿一個長度為 10 的數組來舉例，int [] a= new int[10]，在下面的圖中，計算機給數組分配了一塊連續的空間，100-139，其中內存的起始地址為baseAddress=100

?

我們知道，計算機給每個內存單元都分配了一個地址，通過地址來訪問其數據，因此要訪問數組中的某個元素時，首先要經過一個尋址公式計算要訪問的元素在內存中的地址：

a[i] = baseAddress + i * dataTypeSize

其中 dataTypeSize 代表數組中元素類型的大小，在這個例子中，存儲的是 int 型的數據，因此 dataTypeSize=4 個字節

1.2.2：數組下標為什么從 0 開始

數組的下標為什么要從 0 開始而不是從 1 開始呢？

從數組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用 array 來表示數組的首地址，array[0] 就是偏移為 0 的位置，也就是首地址，array[k] 就表示偏移 k 個 type_size 的位置，所以計算 array[k] 的內存地址只需要用這個公式:

array[k]_address = base_address + k * type_size

但是如果下標從 1 開始，那么計算 array[k]的內存地址會變成：

array[k]_address = base_address + (k-1)*type_size

對比兩個公式，不難發現從數組下標從 1 開始如果根據下標去訪問數組元素，對于 CPU 來說，就多了一次減法指令。

當然另一方面也是由于歷史原因，c 語言設計者使用 0 開始作為數組的下標，后來的高級語言沿用了這一設計。

1.3：數組的特點

1.3.1：高效的隨機訪問

通過前面的學習我們已經知道，數組元素的訪問是通過下標來訪問的，計算機通過數組的首地址和尋址公式能夠很快速的找到想要訪問的元素

1.3.2：低效插入和刪除

前面我們已經講到數組是一段連續的內存空間，因此為了保證數組的連續性會使得數組的插入和刪除的效率變的很低，下面我們來分析一下

• 插入

假設數組的長度為 n，現在如果我們需要將一個數據插入到數組中的第 k 個位置。為了把第 k 個位置騰出來給新來的數據，我們需要將第 k～n 這部分的元素都順序地往后挪一位。如下圖所示：

?

那數組插入有沒有相對優化的方案呢？

如果數組中的數據是有序的，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移 k 之后的數據。但是，如果數組中存儲的數據并沒有任何規律，數組只是被當作一個存儲數據的集合。在這種情況下，如果要將某個數組插入到第 k 個位置，為了避免大規模的數據搬移，我們還有一個簡單的辦法就是，直接將第 k 位的數據搬移到數組元素的最后，把新的元素直接放入第 k 個位置。這種處理思想會在快排中用到

• 刪除

如果我們要刪除第 k 個位置的數據，為了內存的連續性，也需要搬移數據，不然中間就會出現空洞，內存就不連續了。

實際上，在某些特殊場景下，我們并不一定非得追求數組中數據的連續性。如果我們將多次刪除操作集中在一起執行，刪除的效率是不是會提高很多呢？舉個例子

數組 a[6] 中存儲了 6 個元素：a1,a2,a3,a4,a5,a6。現在，我們要依次刪除 a1,a2 這兩個元素

?

為了避免 a3,a4,a5,a6 這幾個數據會被搬移兩次，我們可以先記錄下已經刪除的數據。每次的刪除操作并不是真正地搬移數據，只是記錄數據已經被刪除。當數組沒有更多空間存儲數據時，我們再觸發執行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數據搬移。

如果你了解 JVM，你會發現，這不就是 JVM 標記清除垃圾回收算法的核心思想嗎？沒錯，數據結構和算法的魅力就在于此，很多時候我們并不是要去死記硬背某個**數據結構或者算法，而是要學習它背后的思想和處理技巧，這些東西才是最有價值的**。如果你細心留意，不管是在軟件開發還是架構設計中，總能找到某些算法和數據結構的影子

1.4：數組的應用

針對數組類型，很多語言都提供了容器類，比如 Java 中的 ArrayList、C++ STL 中 的 vector。在項目開發中，什么時候適合用數組，什么時候適合用容器呢？

這里我拿 Java 語言來舉例。如果你是 Java 工程師，幾乎天天都在用 ArrayList，對它應該非常熟悉。那它與數組相比，到底有哪些優勢呢？

我個人覺得，ArrayList 最大的優勢就是可以將很多數組操作的細節封裝起來。比如前面提到的數組插入、刪除數據時需要搬移其他數據等。另外，它還有一個優勢，就是 支持動態擴容 。數組本身在定義的時候需要預先指定大小，因為需要分配連續的內存空間。如果我們申請了大小為 10 的數組，當第 11 個數據需要存儲到數組中時我們就需要重新分配一塊更大的空間，將原來的數據復制過去，然后再將新的數據插入。如果使用 ArrayList，我們就完全不需要關心底層的擴容邏輯，ArrayList 已經幫我們實現好了。每次存儲空間不夠的時候，它都會將空間自動擴容為 1.5 倍大小。不過，這里需要注意一點，因為擴容操作涉及內存申請和數據搬移，是比較耗時的。所以，如果事先能確定需要存儲的數據大小，最好在創建**ArrayList** 的時候事先指定數據大小。

作為高級語言編程者，是不是數組就無用武之地了呢？當然不是，有些時候，用數組會更合適些，我總結了幾點自己的經驗。

1.Java ArrayList 無法存儲基本類型，比如 int、long，需要封裝為 Integer、Long 類，而 Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關注性能，或者希望使用基本類型，就可以選用數組。

2.如果數據大小事先已知，并且對數據的操作非常簡單，用不到 ArrayList 提供的大部分方法，也可以直接使用數組。

我總結一下，對于業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟性能，完全不會影響到系統整體的性能。但如果你是做一些非常底層的開發，比如開發網絡框架，性能的優化需要做到極致，這個時候數組就會優于容器，成為首選。

2.鏈表

2.1：概念

鏈表（Linked list）是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。讀完這段對鏈表的解釋之后我們可能還是不太明白鏈表到底是怎么一回事，那接下來我們從底層的存儲結構開始解開鏈表的面紗

2.2：存儲結構

相比數組，鏈表是一種稍微復雜一點的數據結構。對于初學者來說，掌握起來也要比數組稍難一些。這兩個非常基礎、非常常用的數據結構，我們常常將會放到一塊兒來比較。所以我們先來看，這兩者有什么區別。

首先我們從底層存儲結構來看：

數組：需要一塊連續的存儲空間，對內存的要求比較高，比如我們要申請一個1000M 的數組，如果內存中沒有連續的足夠大的存儲空間則會申請失敗，即便內存的剩余可用空間大于 1000M，仍然會申請失敗。

鏈表：與數組相反，它并不需要一塊連續的內存空間，它通過指針將一組零散的**內存塊**串聯起來使用，所以如果我們申請一個 1000M 大小的鏈表，只要內存剩余的可用空間大于 1000M，便不會出現問題。

下方圖片對比了鏈表和數組的存儲結構

?

此時我們在來回顧我們剛剛提到的鏈表的概念：物理存儲單元上非連續、非順序，元素的邏輯順序是通過鏈表中的指針鏈接次序實現的，鏈表由一系列結點組成，每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域

當然了這只是我們提到的鏈表的最基本的存儲形式，其實鏈表有很多種不同的類型，分別對應了不同的結構，接下來我們就來分析不同的鏈表類型

2.3：鏈表類型

2.3.1：單鏈表

所謂的單鏈表就是我們剛剛講到的鏈表的最基本的結構，鏈表通過指針將一組零散的內存塊串聯在一起。其中，我們把內存塊稱為鏈表的結點。為了將所有的結點串起來，每個鏈表的結點除了存儲數據之外，還需要記錄鏈上的下一個結點的地址。如圖所示，我們把這個記錄下個結點地址的指針叫作后繼指針 next ，如果鏈表中的某個節點為 p，p 的下一個節點為 q，我們可以表示為：p->next=q

下面的圖更加詳細的描述了單鏈表的存儲結構

?

從單鏈表圖中，你應該可以發現，其中有兩個結點是比較特殊的，它們分別是第一個結點和最后一個結點。我們習慣性地把第一個結點叫作頭結點，把最后**一個結點叫作尾結點。其中，頭結點用來記錄鏈表的基地址,有了它，我們就可以遍歷得到整條鏈表。而尾結點特殊的地方是：指針不是指向下一個結點，而是指向一個空地址** NULL，表示這是鏈表上最后一個結點。

與數組一樣，鏈表也支持數據的查找、插入和刪除操作。

我們知道，在進行數組的插入、刪除操作時，為了保持內存數據的連續性，需要做大量的數據搬移。而在鏈表中插入或者刪除一個數據，我們并不需要為了保持內存的連續性而搬移結點，因為鏈表的存儲空間本身就不是連續的。所以，在鏈表中插入和刪除一個數據是非常快速的。

從下圖中我們可以看出，針對鏈表的插入和刪除操作，我們只需要考慮相鄰結點的指針改變

?

但是，有利就有弊。鏈表要想隨機訪問第 k 個元素，就沒有數組那么高效了。因為鏈表中的數據并非連續存儲的，所以無法像數組那樣，根據首地址和下標，通過尋址公式就能直接計算出對應的內存地址，而是需要根據針一個結點一個結點地依次遍歷，直到找到相應的結點，所以，鏈表隨機訪問的性能沒有數組好。

2.3.2：循環鏈表

循環鏈表是一種特殊的單鏈表。實際上，循環鏈表也很簡單。它跟單鏈表唯一的區別就在尾結點。我們知道，單鏈表的尾結點指針指向空地址，表示這就是最后的結點了。而循環鏈表的尾結點指針是指向鏈表的頭結點。從我畫的循環鏈表圖中，你應該可以看出來，它像一個環一樣首尾相連，所以叫作“循環”鏈表，和單鏈表相比，循環鏈表的優點是從鏈尾到鏈頭比較方便。當要處理的數據具有環型結構特點時，就特別適合采用循環鏈表，循環鏈表的結構如圖所示

?

2.3.3：雙向鏈表

單向鏈表只有一個方向，結點只有一個后繼指針 next 指向后面的結點。而雙向鏈表，顧名思義，它支持兩個方向，每個結點不止有一個后繼指針 next 指向后面的結點，還有一個前驅指針 prev 指向前面的結點，如圖所示

?

從圖中可以看出來，雙向鏈表需要額外的兩個空間來存儲后繼結點和前驅結點的地址。所以，如果存儲同樣多的數據，雙向鏈表要比單鏈表占用更多的內存空間。雖然兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。

2.3.4：雙向循環鏈表

了解了循環鏈表和雙向鏈表，如果把這兩種鏈表整合在一起就是一個雙向循環鏈表

?

2.4：鏈表和數組性能比較

通過前面內容的學習，你應該已經知道，數組和鏈表是兩種截然不同的內存組織方式。正是因為內存存儲的區別，它們插入、刪除、隨機訪問操作的性能正好相反數組簡單易用，在實現上使用的是連續的內存空間,缺點是大小固定，一經聲明就要占用整塊連續內存空間。如果聲明的數組過大，系統可能沒有足夠的連續內存空間分配給它，導致“內存不足（out of memory）”。如果聲明的數組過小，則可能出現不夠用的情況。這時只能再申請一個更大的內存空間，把原數組拷貝進去，非常費時。

鏈表本身沒有大小的限制，天然地支持動態擴容，我覺得這也是它與數組最大的區別。你可能會說，我們 Java 中的 ArrayList 容器，也可以支持動態擴容啊？我們上一節課講過，當我們往支持動態擴容的數組中插入一個數據時，如果數組中沒有空閑空間了，就會申請一個更大的空間，將數據拷貝過去，而數據拷貝的操作是非常耗時的。

所以：數組的優勢是查詢速度非常快，但是增刪改慢；鏈表的優勢是增刪改快，但是查詢慢。

2.5：面試題

⑴、LinkedList 和 ArrayList 的比較

前面我們分析過 ArrayList 的源碼，現在又分析了 LinkedList 源碼，接下來將二者進行比較：

1：ArrayList 的實現基于數組，LinkedList 的實現基于雙向鏈表

2：對于隨機訪問，ArrayList 優于 LinkedList，ArrayList 可以根據下標對元素進行隨機訪問。而 LinkedList 的每一個元素都依靠地址指針和它后一個元素連接在一起，在這種情況下，查找某個元素只能從鏈表頭開始查詢直到找到為止

3：對于插入和刪除操作，LinkedList 優于 ArrayList，因為當元素被添加到LinkedList 任意位置的時候，不需要像 ArrayList 那樣重新計算大小或者是更新索引。

4：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節點除了存儲數據，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。

⑵、反轉單鏈表

?

public class ListNode {int val;ListNode next; ?ListNode(int x) {val = x;} } class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null; //前指針節點ListNode curr = head; //當前指針節點//每次循環，都將當前節點指向它前面的節點，然后當前節點和前節點后移while (curr != null) {ListNode nextTemp = curr.next; //臨時節點，暫存當前節點的下一節點，用于后移curr.next = prev; //將當前節點指向它前面的節點prev = curr; //前指針后移curr = nextTemp; //當前指針后移}return prev;} }

3.棧

3.1：概念

關于“棧”這種數據結構，它有一個典型的特點：先進后出，后進先出；只要滿足這種特點的數據結構我們就可以說這是典型的“棧”數據結構，我們一般將這個特點歸納為一個：后進先出,英文表示為：Last In First Out 即 LIFO。為了更好的理解棧這種數據結構，我們以一幅圖的形式來表示，如下：

?

我們從棧的操作特點上來看，似乎受到了限制，的確，棧就是一種操作受限的線性表，只允許在棧的一端進行數據的插入和刪除，這兩種操作分別叫做入棧和出棧。當某個數據集合如果只涉及到在其一端進行數據的插入和刪除操作，并且滿足先進后出，后進先出的特性時，我們應該首選棧這種數據結構來進行數據的存儲。

3.2：棧的實現

從對棧的定義中我們發現棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個元素和在棧底刪除一個元素，那理解了這個定義之后，我們來思考一個問題，如何來手動實現一個棧呢？

實際上，棧既可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫順序棧，用鏈表實現的叫鏈式棧。接下來我們就這兩種形式分別去實現一下。

支持動態擴容的順序棧

public class ArrayStack {// 棧大小private int size;// 默認棧容量private int DEFAULT_CAPACITY = 10;// 棧數據private Object[] elements; ?private int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; ?/*** 默認構造創建大小為 10 的棧*/public ArrayStack() {elements = new Object[DEFAULT_CAPACITY];} ?/*** 通過指定大小創建棧** @param capacity*/public ArrayStack(int capacity) {elements = new Object[capacity];} ?/*** 入棧** @param element* @return*/public boolean push(Object element) {try {checkCapacity(size + 1);elements[size++] = element;return true;} catch (RuntimeException e) {return false;}} ?/*** 檢查棧容量是否還夠*/private void checkCapacity(int minCapacity) {if (elements.length - minCapacity < 0) {//throw new RuntimeException("棧容量不夠!");grow(elements.length);}} ?/*** 擴容** @param oldCapacity 原始容量*/private void grow(int oldCapacity) {int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - oldCapacity < 0) {newCapacity = DEFAULT_CAPACITY;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(newCapacity);}elements = Arrays.copyOf(elements, newCapacity);} ?private int hugeCapacity(int newCapacity) { ?return (newCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : newCapacity;} ?/*** 出棧** @return*/public Object pop() {if (size <= 0) {return null;//棧為空則直接返回 null}Object obj = elements[size - 1];elements[--size] = null;return obj;} ?/*** 獲取棧的大小** @return*/public int size() {return size;} ? } 添加測試代碼如下： public class ArrayStackTest {public static void main(String[] args) {ArrayStack stack = new ArrayStack(5);for (int i = 0; i < 40; i++) {boolean push = stack.push(i);System.out.println("第" + (i + 1) + "次存儲數據為:" + i + ",存儲結果是: " + push);}// stack.push(1);for (int i = 0; i < 11; i++) {Object pop = stack.pop();System.out.println(pop);}} }

基于鏈表的鏈式棧

public class StackBasedOnLinkedList {// 存儲鏈表頭節點private Node head; ?public StackBasedOnLinkedList() {this.head = null;} ?/*** 入棧** @param data* @return*/public boolean push(Object data) {Node newNode = new Node(data, head);head = newNode;return true;} ?/*** 出棧** @return*/public Object pop() {if (head == null) {return null;}Node topNode = head;head = topNode.next;topNode.next = null;return topNode.data;} ?/*** 節點對象*/private static class Node {//節點數據private Object data;// next 指針private Node next; ?public Node(Object data, Node next) {this.data = data;this.next = next;} ?public Object getData() {return data;}} } ?

添加測試代碼如下：

public class TestStackBasedOnLinkedList {public static void main(String[] args) {StackBasedOnLinkedList stack = new StackBasedOnLinkedList();for (int i = 0; i < 6; i++) {stack.push(i + "");System.out.println("第" + (i + 1) + "次入棧,入棧的值為:" + i);} ?for (int i = 0; i < 8; i++) {Object pop = stack.pop();System.out.println("取出的結果:" + pop);}} } ?

4.隊列

4.1：概念

隊列的概念非常容易理解，我們拿日常生活中的一個場景來舉例說明，我們去車站的窗口買票，那就要排隊，那先來的人就先買，后到的人就后買，先來的人排到隊頭，后來的人排在隊尾，不允許插隊，先進先出，這就是典型的隊列。 隊列先進先出的特點英文表示為：First In First Out 即 FIFO,為了更好的理解隊列這種數據結構，我們以一幅圖的形式來表示，并且我們將隊列的特點和棧進行比較，如下：

?

從圖中我們可以發現，隊列和棧一樣都屬于一種操作受限的線性表，棧只允許在一端進行操作，分別是入棧 push()和出棧 pop()，而隊列跟棧很相似，支持的操作也有限，最基本的兩個操作一個叫入隊列 enqueue()，將數據插入到隊列尾部，另一個叫出隊列 dequeue()，從隊列頭部取出一個數據。

隊列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎的數據結構，隊列的應用也非常廣泛，特別是一些具有某些額外特性的隊列，比如循環隊列、阻塞隊列、并發隊列。它們在很多偏底層系統、框架、中間件的開發中，起著關鍵性的作用。比如高性能隊列 Disruptor、Linux 環形緩存都用到了循環并發隊列，在 java 中，concurrent 并發包利用 ArrayBlockingQueue 來實現公平鎖等。

4.2：常見隊列及實現

4.2.1：順序隊列的實現

?

跟棧一樣，隊列可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫作順序棧，用鏈表實現的棧叫作鏈式棧。同樣，用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。

對于棧來說，我們只需要一個棧頂指針就可以了。但是隊列需要兩個指針(數組下標)：一個是 head 指針，指向隊頭；一個是 tail 指針，指向隊尾。每一次元素入隊列操作，我們的 tail 指針就需要向后移動一位；每一次出隊列操作，我們的 head指針就要向后移動一位。

但是當 tail 指針移動到數組末尾之后，由于入隊列操作都是從數組尾部存入數據，那此時數組尾部已不能在插入數據了，我們就要根據情況采取不同的措施，第一種情況是數組中已經沒有位置可以存儲數據了那就要對數組進行擴容，第二種情況是數組中還有位置可以存儲數據，只不過是數組尾端已不能再插入數據了，那此時就要將數組中的數據依次向前挪動，將數組尾部的位置空出來供入隊列操作。

下面進行代碼實現：

public class ArrayQueue {// 存儲數據的數組private Object[] elements;//隊列大小private int size;// 默認隊列容量private int DEFAULT_CAPACITY = 10;// 隊列頭指針private int head;// 隊列尾指針private int tail; ?private int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; ?/*** 默認構造函數 初始化大小為 10 的隊列*/public ArrayQueue() {elements = new Object[DEFAULT_CAPACITY];initPointer(0, 0);} ?/*** 通過傳入的容量大小創建隊列** @param capacity*/public ArrayQueue(int capacity) {elements = new Object[capacity];initPointer(0, 0);} ?/*** 初始化隊列頭尾指針** @param head* @param tail*/private void initPointer(int head, int tail) {this.head = head;this.tail = tail;} ?/*** 元素入隊列** @param element* @return*/public boolean enqueue(Object element) {ensureCapacityHelper();elements[tail++] = element;//在尾指針處存入元素且尾指針后移size++;//隊列元素個數加 1return true;} ?private void ensureCapacityHelper() {if (tail == elements.length) {//尾指針已越過數組尾端//判斷隊列是否已滿 即判斷數組中是否還有可用存儲空間//if (size < elements.length) {if (head == 0) {//擴容grow(elements.length);} else {//進行數據搬移操作 將數組中的數據依次向前挪動直至頂部for (int i = head; i < tail; i++) {elements[i - head] = elements[i];}//數據搬移完后重新初始化頭尾指針initPointer(0, tail - head);}}}} ?/*** 擴容** @param oldCapacity 原始容量*/private void grow(int oldCapacity) {int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - oldCapacity < 0) {newCapacity = DEFAULT_CAPACITY;}if (newCapacity - MAX_ARRAY_SIZE > 0) {newCapacity = hugeCapacity(newCapacity);}elements = Arrays.copyOf(elements, newCapacity);} ?private int hugeCapacity(int newCapacity) {return (newCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : newCapacity;} ?/*** 出隊列** @return*/public Object dequeue() {if (head == tail) {return null;//隊列中沒有數據}Object obj = elements[head++];//取出隊列頭的元素且頭指針后移size--;//隊列中元素個數減 1return obj;} ?/*** 獲取隊列元素個數** @return*/public int getSize() {return size;} }

4.2.2：鏈式隊列的實現

我們知道隊列是先進先出的，對于鏈表，我們能采用單鏈表盡量采用單鏈表，能方便盡量方便，同時還要兼顧效率。

• 方案一 如果隊頭設在鏈表尾，隊尾設在鏈表頭。那么隊尾進隊插入在鏈表頭部插入沒問題。容易實現，但是如果隊頭刪除在尾部進行，如果不設置尾指針要遍歷到隊尾，但是設置尾指針刪除需要將它指向前驅節點那么就需要雙向鏈表。都挺麻煩的。

• 方案二 但是如果隊頭設在鏈表頭，隊尾設在鏈表尾部，那么隊尾進隊插入在鏈表尾部插入沒問題(用尾指針可以直接指向next)。容易實現，如果隊頭刪除在頭部進行也很容易，就是我們前面常說的頭節點刪除節點。

• 所以我們最終采取的是方案2的帶頭節點，帶尾指針的單鏈表!

?

?

下面進行代碼實現：

public class LinkedListQueue {//隊列元素個數private int size;//頭節點private Node head;//尾節點private Node tail; ?public LinkedListQueue() {this.head = null;this.tail = null;} ?/*** 入隊列** @param data* @return*/public boolean enqueue(Object data) {Node newNode = new Node(data, null);if (tail == null) {tail = newNode;head = newNode;} else {tail.next = newNode;tail = newNode;}size++;return true;} ?/*** 出隊列** @return*/public Object dequeue() {if (head == null) {return null;}Object data = head.data;head = head.next;if (head == null) {tail = null;}size--;return data;} ? ?private static class Node {//節點數據private Object data;//后繼節點private Node next; ?public Node(Object data, Node next) {this.data = data;this.next = next;}} ?public int getSize() {return size;} }

?

總結

以上是生活随笔為你收集整理的数据结构之数组、链表、栈和队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。