目錄
- 鏈表的資料結構的實作程序（Java 實作）
- 前言
- 基本概念
- 鏈表的基本結構
- 鏈表的基本操作的實作
- 在鏈表中添加元素
- 在鏈表頭添加元素
- 在鏈表指定位置處添加元素
- 在鏈表中添加元素
- 鏈表的虛擬頭節點
- 鏈表的查詢和修改操作
- 查詢操作的實作
- 修改操作的實作
- 鏈表的洗掉操作
- 重寫 toString 方法顯示鏈表中元素資訊
- 鏈表的時間復雜度簡單分析
- 鏈表的一些改進方式
- 使用鏈表實作堆疊
- 使用鏈表實作佇列
- 小結
鏈表的資料結構的實作程序（Java 實作）
前言
在前面實作的三種線性資料結構：動態陣列、堆疊和佇列 雖然對用戶而言實作了動態的功能，但在底層上還是依托著靜態陣列，使用 resize 方法解決固定容量的問題，從根本上來說還不是真正的動態，
而對于鏈表而言，則是真正的動態資料結構，
因為鏈表的實作是將一個個節點靠地址的指向將這些節點掛接起來而組成的，
簡單來說，每一次在鏈表上添加新資料就是在一個已有節點的指標域上指定它的下一個節點的地址為存放新資料的節點的地址，這樣子，不論是從底層上還是用戶的角度上，都不用擔心容量的問題，所以鏈表是真正的動態資料結構，
同樣，鏈表也是一個很重要的資料結構，對于鏈表而言，它是最簡單的動態資料結構，可以幫助我們更深入地理解參考（指標）、更深入地理解遞回以及可以用來輔助組成其他的資料結構，
基本概念
鏈表的基本結構
對鏈表而言，資料是存盤在“節點”（Node）中的，可以使用一個資料域來存盤資料，這里我稱為 element；然后節點中還有一個用來指向下一個節點位置的節點域，一般稱為 next，而對于鏈表的結尾，一般是以 NULL 作為結尾，所以鏈表中的最后一個節點的節點域 next 指向的是 NULL，
圖示如下:
所以可以先暫時設計鏈表的基本結構代碼如下：
/**
* 鏈表類
* 支持泛型
*
* @author 踏雪彡尋梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 鏈表的節點
* 對于用戶而言，不需要知道鏈表的底層結構是怎樣的，只需要知道鏈表是一種線性資料結構，可以增刪改查資料
*/
private class Node {
/**
* 節點存盤的資料
*/
public E element;
/**
* 用于指向下一個節點,使節點與節點之間掛接起來組成鏈表
*/
public Node next;
/**
* 建構式
* 構造一個存有資料并指向了下一個節點的節點
*
* @param element 存往該節點中的資料
* @param next 該節點的下一個節點
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 建構式
* 構造一個存有資料但沒有指向下一個節點的節點
*
* @param element 存往該節點中的資料
*/
public Node(E element) {
this(element, null);
}
/**
* 建構式
* 構造一個空節點
*/
public Node() {
this(null, null);
}
/**
* 重寫 toString 方法以顯示節點中存盤的資料資訊
*
* @return 回傳節點中存盤的資料資訊
*/
@Override
public String toString() {
return element.toString();
}
}
}
從以上設計也可簡單的分析鏈表的優缺點如下：
-
優點：真正的動態結構，不需要處理固定容量的問題，
-
缺點：喪失了隨機訪問的能力，即不像陣列一樣可以通過索引快速地獲取到資料，
綜上，可簡單對比陣列和鏈表的使用場景如下：
-
陣列最好用于索引有語意的情況，不適合用于索引沒有語意的情況，
-
有語意的情況：如一個班級中第二名的分數可這樣表示：score[2]，
-
陣列也可以沒有語意，并不是任何時候索引都是有語意的，不是所有有語意的這樣的一個標志就適合做索引，如身份證號：身份證號的保存會存在空間的浪費（有些索引不是身份證號碼），
- 如：身份證號為 41222197801015333 的某個人表示為：person[41222197801015333]
-
最大的優點：支持快速查詢，
-
-
相比陣列，將一個靜態陣列改變為一個動態陣列，就是在對于不方便使用索引的時候處理有關資料存盤的問題，對于這樣的存盤資料的需求使用鏈表是更合適的，所以鏈表不適合用于索引有語意的情況，更適合處理索引沒有語意的情況，
- 因為鏈表最大的優點是動態存盤，
另外，對于查看鏈表中的各個元素，也是需要一一遍歷過去的，那么此時就需要一個變數 head 來指向鏈表頭部的位置，以便查看鏈表資訊所用，同時因為有了這個變數 head 來指向鏈表頭的位置，那么往鏈表頭部添加新元素是十分方便的，這和之前實作的陣列資料結構在陣列尾部添加元素十分方便是同一個道理，陣列中有 size 變數指向下一個新元素位置跟蹤尾部，
此時鏈表的結構如下圖所示：
此時設計鏈表基本結構代碼如下，其中使用了一個變數 size 來實時記錄鏈表元素的個數以及增加了兩個基本方法用于獲取鏈表當前元素個數和判斷鏈表是否為空：
/**
* 鏈表類
* 支持泛型
*
* @author 踏雪彡尋梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 鏈表的節點
* 對于用戶而言，不需要知道鏈表的底層結構是怎樣的，只需要知道鏈表是一種線性資料結構，可以增刪改查資料
*/
private class Node {
/**
* 節點存盤的資料
*/
public E element;
/**
* 用于指向下一個節點,使節點與節點之間掛接起來組成鏈表
*/
public Node next;
/**
* 建構式
* 構造一個存有資料并指向了下一個節點的節點
*
* @param element 存往該節點中的資料
* @param next 該節點的下一個節點
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 建構式
* 構造一個存有資料但沒有指向下一個節點的節點
*
* @param element 存往該節點中的資料
*/
public Node(E element) {
this(element, null);
}
/**
* 建構式
* 構造一個空節點
*/
public Node() {
this(null, null);
}
/**
* 重寫 toString 方法以顯示節點中存盤的資料資訊
*
* @return 回傳節點中存盤的資料資訊
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 鏈表的頭節點
* 存盤第一個元素的節點
*/
private Node head;
/**
* 鏈表當前元素個數
*/
private int size;
/**
* 建構式
* 構造一個空鏈表
*/
public LinkedList() {
head = null;
size = 0;
}
/**
* 獲取鏈表中的當前元素個數
*
* @return 回傳鏈表當前元素個數
*/
public int getSize() {
return size;
}
/**
* 判斷鏈表是否為空
*
* @return 鏈表為慷訓傳 true;否則回傳 fasle
*/
public boolean isEmpty() {
return size == 0;
}
}
鏈表的基本操作的實作
在鏈表中添加元素
在鏈表頭添加元素
在上文介紹過，在鏈表頭部添加元素是十分方便的，所以先實作這個操作，
對于這個操作，實作的具體步驟如下：
-
創建一個新節點 newNode 存盤新元素 newElement，新節點的節點域 next 指向 NULL，
-
將 newNode 的 節點域 next 指向當前鏈表頭 head，使新節點掛接在鏈表頭部，即 newNode.next = head，
-
最后將 head 指向 newNode，使鏈表頭為新增的節點，即 head = newNode，
綜上，在鏈表頭添加程序如下圖所示：
設計在鏈表頭部添加元素代碼如下所示：
/**
* 在鏈表頭添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addFirst(E newElement) {
// 創建一個新節點存盤新元素,該節點的 next 指向 NULL
Node newNode = new Node(newElement);
// 使 newNode 的 next 指向鏈表頭
newNode.next = head;
// 將鏈表頭設為鏈表新添加的新節點
head = newNode;
// 以上三行代碼可使用 Node 的另一個建構式簡寫為：
// head = new Node(newElement, head);
// 維護 size,鏈表當前元素個數 + 1
size++;
}
在鏈表指定位置處添加元素
除了在鏈表頭部添加元素，還可以指定一個位置來進行添加元素，這個操作在鏈表的操作中不常使用，一般常出現在試題中，這里實作出來用來幫助深入理解鏈表的思維，
對于這個操作，指定的添加元素位置這里設計為用 index 表示（從 0 開始計數），實作的具體步驟如下：
-
判斷指定的添加位置 index 是否為合法值，
-
使用一個節點變數 prev 來找到指定插入位置 index 的前一個節點位置，初始時 prev 指向鏈表頭 head，
-
創建一個新節點 newNode 存盤新元素 newElement，新節點的節點域 next 指向 NULL，
-
使用 prev 找到指定位置 index 的前一個位置（index - 1 處，即插入位置的前一個節點）后，將 newNode 的 next 指向 prev 的 next 指向的節點，即將新節點掛接在插入位置的原節點前面，（newNode.next = prev.next）
-
將 prev 的 next 指向新節點 newNode，即將鏈表前后都掛接了起來，此時新節點處于 index 處，而原來處于 index 的節點和之后的節點都往后挪了一個位置，（prev.next = newNode）
對于以上步驟，關鍵在于找到要添加的節點的前一個節點，
而找到前一個節點這個操作有一個特殊情況，即指定添加位置 index 為 0 的時候，也就是將元素添加到鏈表頭，而鏈表頭是沒有前一個節點的（對于鏈表頭沒有前一個節點后續會實作一個虛擬頭節點放置到鏈表頭的前一個節點，方便鏈表的操作），
所以這個操作需要進行特殊處理：
使用一個判斷判斷 index 是否為 0，如果為 0 使用前面實作的 addFirst(E newElement) 方法將新節點添加到鏈表頭，
綜上，在鏈表指定位置處添加元素程序如下圖所示：
需要注意的是 newNode.next = prev.next 和 prev.next = newNode 的順序不能相反，否則將會出現錯誤，具體結果圖示如下：
設計在鏈表指定位置處添加元素代碼如下所示：
/**
* 在鏈表的指定位置 index（從 0 開始計數）處添加新元素 newElement
*
* @param index 指定的添加位置,從 0 開始計數
* @param newElement 新元素
*/
public void add(int index, E newElement) {
// 判斷 index 是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
if (index == 0) {
// 如果 index 為 0,使用 addFirst(E newElement) 方法將新元素添加到鏈表頭，
addFirst(newElement);
} else {
// 否則將新元素添加到 index 處
// 找到 index 的前一個節點
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// 創建一個新節點存盤新元素,該節點的 next 指向 NULL
Node newNode = new Node(newElement);
// 將新節點添加到 index 處
newNode.next = prev.next;
prev.next = newNode;
// 以上三行代碼可使用 Node 的另一個建構式簡寫為：
// prev.next = new Node(newElement, prev.next);
// 維護 size,鏈表當前元素個數 + 1
size++;
}
}
由以上實作可復用其實作一個在鏈表末尾添加新元素的方法 addLast：
/**
* 在鏈表末尾添加新的元素 newElement
* @param newElement 新元素
*/
public void addLast(E newElement) {
add(size, newElement);
}
鏈表的虛擬頭節點
在上面實作的在鏈表指定位置處添加元素中，可以發現有一個特殊情況為指定在頭部添加元素時，頭部元素沒有前一個節點，所以需要做一個特殊處理，為了讓這個操作統一為每個節點都可以找到前置節點，需要在鏈表中設定一個虛擬頭節點 dummyHead，這個節點這里設計為不存盤資料，只用于指向鏈表中的第一個元素，
添加虛擬頭節點后的鏈表基本結構圖示如下：
此時更改鏈表的實作代碼如下：
/**
* 鏈表類
* 支持泛型
*
* @author 踏雪彡尋梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 鏈表的節點
* 對于用戶而言，不需要知道鏈表的底層結構是怎樣的，只需要知道鏈表是一種線性資料結構，可以增刪改查資料
*/
private class Node {
/**
* 節點存盤的資料
*/
public E element;
/**
* 用于指向下一個節點,使節點與節點之間掛接起來組成鏈表
*/
public Node next;
/**
* 建構式
* 構造一個存有資料并指向了下一個節點的節點
*
* @param element 存往該節點中的資料
* @param next 該節點的下一個節點
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 建構式
* 構造一個存有資料但沒有指向下一個節點的節點
*
* @param element 存往該節點中的資料
*/
public Node(E element) {
this(element, null);
}
/**
* 建構式
* 構造一個空節點
*/
public Node() {
this(null, null);
}
/**
* 重寫 toString 方法以顯示節點中存盤的資料資訊
*
* @return 回傳節點中存盤的資料資訊
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 鏈表的虛擬頭節點
* 不存盤資料
* next 指向鏈表中的第一個元素
*/
private Node dummyHead;
/**
* 鏈表當前元素個數
*/
private int size;
/**
* 建構式
* 構造一個空鏈表
*/
public LinkedList() {
// 創建虛擬頭節點,存盤 null,初始時 next 指向 null
dummyHead = new Node(null, null);
size = 0;
}
/**
* 獲取鏈表中的當前元素個數
*
* @return 回傳鏈表當前元素個數
*/
public int getSize() {
return size;
}
/**
* 判斷鏈表是否為空
*
* @return 鏈表為慷訓傳 true;否則回傳 fasle
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在鏈表的指定位置 index（從 0 開始計數）處添加新元素 newElement
*
* @param index 指定的添加位置,從 0 開始計數
* @param newElement 新元素
*/
public void add(int index, E newElement) {
// 判斷 index 是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
// 將新元素添加到 index 處
// 找到 index 的前一個節點
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 創建一個新節點存盤新元素,該節點的 next 指向 NULL
Node newNode = new Node(newElement);
// 將新節點添加到 index 處
newNode.next = prev.next;
prev.next = newNode;
// 以上三行代碼可使用 Node 的另一個建構式簡寫為：
// prev.next = new Node(newElement, prev.next);
// 維護 size,鏈表當前元素個數 + 1
size++;
}
/**
* 在鏈表頭添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addFirst(E newElement) {
add(0, newElement);
}
/**
* 在鏈表末尾添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addLast(E newElement) {
add(size, newElement);
}
}
此時，在 add 方法的實作中添加新元素的操作就都統一為同一個步驟了，每一個節點都能找到其前置節點，
需要注意的是，和之前 prev 從鏈表的第一個元素開始遍歷尋找更改為了從虛擬頭節點開始遍歷尋找，所以遍歷的終止條件從 i < index - 1 變為了 i < index，為了方便理解這個程序，可以參考以下圖示：
-
原實作：
-
現實作：
在更改了 add 方法之后，addFirst 方法也可精簡為復用 add 方法就可實作在鏈表頭部添加元素的功能了，這也是使用了虛擬頭節點之后帶來的便利，
鏈表的查詢和修改操作
查詢操作的實作
對于此操作，這里實作兩個型別的方法用于查詢鏈表中的元素：
-
get 方法：獲得鏈表中某個位置的元素（位置從 0 開始計數），該操作在鏈表中不常使用，可以用來加強鏈表的理解，具體實作如下：
/** * 獲得鏈表的第 index 個位置的元素 * * @param index 需要獲取的元素的位置,從 0 開始計數 * @return 回傳鏈表中的 index 處的元素 */ public E get(int index) { // 判斷 index 的合法性 if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed.Illegal index."); } // 從鏈表中第一個元素開始遍歷,找到處于 index 的節點 Node currentElement = dummyHead.next; for (int i = 0; i < index; i++) { currentElement = currentElement.next; } // 回傳處于 index 的元素 return currentElement.element; }-
由以上實作可衍生出兩個方法分別用來獲取鏈表中第一個元素和鏈表中最后一個元素：
/** * 獲得鏈表的第一個元素 * * @return 回傳鏈表的第一個元素 */ public E getFirst() { return get(0); } /** * 獲得鏈表的最后一個元素 * * @return 回傳鏈表的最后一個元素 */ public E getLast() { // index 從 0 開始計數,size 為當前元素個數,所以最后一個元素的位置對應為 size - 1 return get(size - 1); }
-
-
contains 方法：判斷用戶給定的一個元素是否存在于鏈表中，存在回傳 true，不存在回傳 false，具體實作如下：
/** * 查找鏈表中是否含有元素 element * * @param element 需要查找的元素 * @return 如果包含 element 回傳 true;否則回傳 false */ public boolean contains(E element) { // 從鏈表中第一個元素開始遍歷,依次判斷是否包含有元素 element Node currentElement = dummyHead.next; while (currentElement != null) { if (currentElement.element.equals(element)) { // 相等說明鏈表中包含元素 element,回傳 true return true; } currentElement = currentElement.next; } // 整個鏈表遍歷完還沒有找到則回傳 false return false; }
修改操作的實作
對于此操作，實作的目的是修改鏈表中某個位置（位置從 0 開始計數）的元素為指定的新元素，該操作在鏈表中也不常使用，可以用來加強鏈表的理解，具體實作如下：
/**
* 修改鏈表的第 index 個位置的元素為 newElement
*
* @param index 需要修改的元素的位置,從 0 開始計數
* @param newElement 替換老元素的新元素
*/
public void set(int index, E newElement) {
// 判斷 index 的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed.Illegal index.");
}
// 從鏈表中第一個元素開始遍歷,找到處于 index 的節點
Node currentElement = dummyHead.next;
for (int i = 0; i < index; i++) {
currentElement = currentElement.next;
}
// 修改 index 的元素為 newElement
currentElement.element = newElement;
}
鏈表的洗掉操作
對于洗掉操作，目的為洗掉鏈表中某個位置的元素并回傳洗掉的元素，該操作在鏈表中也不常使用，可以用來加強鏈表的理解，實作的步驟如下：
-
找到待洗掉節點 delNode 的前置節點 prev，
-
將 prev 的 next 指向待洗掉節點 dalNode 的 next，即越過了 delNode，和它后面的節點掛接了起來，(prev.next = delNode.next)
-
將 delNode 的 next 指向 null，至此，delNode 和鏈表脫離關系，從鏈表中被洗掉，(delNode.next = null)
-
回傳 delNode 中存盤的元素 element，即回傳洗掉的元素，
洗掉程序圖示如下：
代碼具體實作如下：
/**
* 從鏈表中洗掉 index 位置的節點并回傳洗掉的元素
*
* @param index 要洗掉節點在鏈表中的位置,從 0 開始計數
* @return 回傳洗掉的元素
*/
public E remove(int index) {
// 判斷 index 的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed.Illegal index.");
}
// 從虛擬頭節點開始遍歷找到待洗掉節點的前置節點
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 記錄待洗掉節點
Node delNode = prev.next;
// 進行洗掉操作
prev.next = delNode.next;
delNode.next = null;
// 維護 size,鏈表當前元素個數 - 1
size--;
// 回傳洗掉的元素
return delNode.element;
}
由以上實作可衍生出兩個方法分別用于洗掉鏈表中的第一個元素和最后一個元素：
/**
* 從鏈表中洗掉第一個元素所在的節點并回傳洗掉的元素
*
* @return 回傳洗掉的元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 從鏈表中洗掉最后一個元素所在的節點并回傳洗掉的元素
*
* @return 回傳洗掉的元素
*/
public E removeLast() {
return remove(size - 1);
}
重寫 toString 方法顯示鏈表中元素資訊
實作到此，已經可以重寫 toString 方法顯示鏈表中元素資訊來測驗以上實作的基本操作了，以此驗證設計的邏輯沒有出錯，
對于此方法，這里設計為下：
/**
* 重寫 toString 方法,以便觀察鏈表中的元素
*
* @return 回傳當前鏈表資訊
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedList: size = %d, Elements: dummyHead -> ", size));
// 從鏈表中第一個元素開始遍歷,依次將鏈表中元素資訊添加到結果資訊中
Node currentElement = dummyHead.next;
while (currentElement != null) {
result.append(currentElement + " -> ");
currentElement = currentElement.next;
}
// 以上遍歷的等價寫法：
// for (Node currentElement = dummyHead.next; currentElement != null; currentElement = currentElement.next) {
// result.append(currentElement + " -> ");
// }
result.append("NULL");
return result.toString();
}
接著測驗以上實作的基本操作，測驗代碼如下：
/**
* 測驗 LinkedList
*/
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
// 測驗 isEmpty 方法
System.out.println("==== 測驗 isEmpty 方法 ====");
System.out.println("當前鏈表是否為空: " + linkedList.isEmpty());
// 測驗鏈表的添加操作
System.out.println("\n==== 測驗 addFirst 方法 ====");
for (int i = 0; i < 5; i++) {
linkedList.addFirst(i);
System.out.println(linkedList);
}
System.out.println("\n==== 測驗 add 方法 ====");
System.out.println("添加 888 到鏈表中的第 2 個位置(從 0 開始計數): ");
linkedList.add(2, 888);
System.out.println(linkedList);
System.out.println("\n==== 測驗 addLast 方法 ====");
linkedList.addLast(999);
System.out.println(linkedList);
// 測驗 contains 方法
System.out.println("\n==== 測驗 contains 方法 ====");
System.out.println(linkedList);
boolean flag = linkedList.contains(888);
System.out.println("鏈表中是否存在 888: " + flag);
flag = linkedList.contains(777);
System.out.println("鏈表中是否存在 777: " + flag);
// 測驗 get 方法
System.out.println("\n==== 測驗 get 方法 ====");
System.out.println(linkedList);
Integer element = linkedList.getFirst();
System.out.println("鏈表中的第一個元素為: " + element);
element = linkedList.getLast();
System.out.println("鏈表中的最后一個元素為: " + element);
element = linkedList.get(3);
System.out.println("鏈表中的第 3 個位置(從 0 開始計數)的元素為: " + element);
// 測驗 isEmpty 方法
System.out.println("\n==== 測驗 isEmpty 方法 ====");
System.out.println("當前鏈表是否為空: " + linkedList.isEmpty());
// 測驗 set 方法
System.out.println("\n==== 測驗 set 方法 ====");
System.out.println(linkedList);
linkedList.set(3, 12);
System.out.println("更改鏈表中的第 3 個位置(從 0 開始計數)的元素為 12 后: ");
System.out.println(linkedList);
// 測驗鏈表的洗掉操作
System.out.println("\n==== 測驗 remove 方法 ====");
Integer delElement = linkedList.remove(3);
System.out.println("洗掉鏈表中的第 3 個位置(從 0 開始計數)的元素后: ");
System.out.println(linkedList);
System.out.println("洗掉的元素為: " + delElement);
System.out.println("\n==== 測驗 removeFirst 方法 ====");
delElement = linkedList.removeFirst();
System.out.println("洗掉鏈表中的第一個元素后: ");
System.out.println(linkedList);
System.out.println("洗掉的元素為: " + delElement);
System.out.println("\n==== 測驗 removeLast 方法 ====");
delElement = linkedList.removeLast();
System.out.println("洗掉鏈表中的最后一個元素后: ");
System.out.println(linkedList);
System.out.println("洗掉的元素為: " + delElement);
}
測驗結果:
==== 測驗 isEmpty 方法 ====
當前鏈表是否為空: true
==== 測驗 addFirst 方法 ====
LinkedList: size = 1, Elements: dummyHead -> 0 -> NULL
LinkedList: size = 2, Elements: dummyHead -> 1 -> 0 -> NULL
LinkedList: size = 3, Elements: dummyHead -> 2 -> 1 -> 0 -> NULL
LinkedList: size = 4, Elements: dummyHead -> 3 -> 2 -> 1 -> 0 -> NULL
LinkedList: size = 5, Elements: dummyHead -> 4 -> 3 -> 2 -> 1 -> 0 -> NULL
==== 測驗 add 方法 ====
添加 888 到鏈表中的第 2 個位置(從 0 開始計數):
LinkedList: size = 6, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> NULL
==== 測驗 addLast 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
==== 測驗 contains 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
鏈表中是否存在 888: true
鏈表中是否存在 777: false
==== 測驗 get 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
鏈表中的第一個元素為: 4
鏈表中的最后一個元素為: 999
鏈表中的第 3 個位置(從 0 開始計數)的元素為: 2
==== 測驗 isEmpty 方法 ====
當前鏈表是否為空: false
==== 測驗 set 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
更改鏈表中的第 3 個位置(從 0 開始計數)的元素為 12 后:
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 12 -> 1 -> 0 -> 999 -> NULL
==== 測驗 remove 方法 ====
洗掉鏈表中的第 3 個位置(從 0 開始計數)的元素后:
LinkedList: size = 6, Elements: dummyHead -> 4 -> 3 -> 888 -> 1 -> 0 -> 999 -> NULL
洗掉的元素為: 12
==== 測驗 removeFirst 方法 ====
洗掉鏈表中的第一個元素后:
LinkedList: size = 5, Elements: dummyHead -> 3 -> 888 -> 1 -> 0 -> 999 -> NULL
洗掉的元素為: 4
==== 測驗 removeLast 方法 ====
洗掉鏈表中的最后一個元素后:
LinkedList: size = 4, Elements: dummyHead -> 3 -> 888 -> 1 -> 0 -> NULL
洗掉的元素為: 999
行程已結束，退出代碼 0
從結果可以看出以上實作的基本操作沒有出現錯誤，說明了實作的邏輯是正確的，接下來對以上實作的基本操作做一些簡單的時間復雜度分析，
鏈表的時間復雜度簡單分析
-
添加操作
-
addLast 方法：對于該方法，每次都要遍歷整個鏈表進行添加，所以該方法的時間復雜度是 O(n) 級別的，
-
addFirst 方法：對于該方法，每次都是在鏈表頭部做操作，所以該方法的時間復雜度是 O(1) 級別的，
-
add 方法：對于該方法，平均來說，每次添加元素需要遍歷 n/2 個元素，所以該方法的時間復雜度是 O(n/2) = O(n) 級別的，
-
綜上，添加操作的時間復雜度為 O(n)，
-
-
洗掉操作
-
removeLast 方法：對于該方法，每次都要遍歷整個鏈表進行洗掉，所以該方法的時間復雜度是 O(n) 級別的，
-
removeFirst 方法：對于該方法，每次都是在鏈表頭部做操作，所以該方法的時間復雜度是 O(1) 級別的，
-
remove 方法：對于該方法，平均來說，每次洗掉元素需要遍歷 n/2 個元素，所以該方法的時間復雜度是 O(n/2) = O(n) 級別的，
-
綜上，洗掉操作的時間復雜度為 O(n)，
-
-
修改操作
-
set 方法：對于該方法，平均來說，每次修改元素需要遍歷 n/2 個元素，所以該方法的時間復雜度是 O(n/2) = O(n) 級別的，
-
所以修改操作的時間復雜度也為 O(n)，
-
-
查找操作
-
getLast 方法：對于該方法，每次都要遍歷整個鏈表進行查找，所以該方法的時間復雜度是 O(n) 級別的，
-
getFirst 方法：對于該方法，每次都是在鏈表頭部做操作，所以該方法的時間復雜度是 O(1) 級別的，
-
get 方法：對于該方法，平均來說，每次查找元素需要遍歷 n/2 個元素，所以該方法的時間復雜度是 O(n/2) = O(n) 級別的，
-
contains 方法：對于該方法，平均來說，每次查找判斷元素是否存在也是需要遍歷 n/2 個元素，所以該方法的時間復雜度也是 O(n/2) = O(n) 級別的，
-
綜上，查找操作的時間復雜度為 O(n)，
-
-
所以對于鏈表而言，增刪改查的時間復雜度都是 O(n) 級別的，
-
但是如果不對鏈表中元素進行修改操作，添加和洗掉操作也只針對鏈表頭進行操作和查找操作也只查鏈表頭的元素的話，此時整體的時間復雜度就是 O(1) 級別的了，又由于鏈表整體是動態的，不會浪費大量的記憶體空間，此時具有一定的優勢，顯而易見滿足這些條件的資料結構為堆疊，此時就可以使用鏈表來實作堆疊發揮鏈表的優勢了，當然，對于鏈表而言，還有一些改進方式使其在一些應用場景具有優勢，比如給鏈表添加尾指標后使用鏈表來實作佇列，
鏈表的一些改進方式
使用鏈表實作堆疊
對于堆疊這個資料結構，它只針對一端進行操作，即針對堆疊頂進行操作，是一個后入先出的資料結構，
上文說到如果鏈表不使用修改操作，只使用添加、洗掉、查找鏈表頭的操作是滿足堆疊這個資料結構的特點的，所以可以使用鏈表頭作為堆疊頂，用鏈表作為堆疊的底層實作來實作堆疊這個資料結構，發揮鏈表的動態優勢，最后，再和之前基于動態陣列實作的堆疊進行一些效率上的對比，查看兩者的差距，接下來，開始實作使用鏈表實作堆疊，
對于使用鏈表實作堆疊，將使用一個 LinkedListStack 類實作之前實作陣列堆疊時定義的堆疊的介面 Stack 來實作堆疊的一系列的操作，
回顧堆疊的介面 Stack 的實作如下：
/**
* 定義堆疊支持的操作的介面
* 支持泛型
*
* @author 踏雪尋梅
* @date 2020/1/8 - 19:20
*/
public interface Stack<E> {
/**
* 獲取堆疊中元素個數
*
* @return 堆疊中如果有元素,回傳堆疊中當前元素個數;堆疊中如果沒有元素回傳 0
*/
int getSize();
/**
* 判斷堆疊是否為空
*
* @return 堆疊為空,回傳 true;堆疊不為空,回傳 false
*/
boolean isEmpty();
/**
* 入堆疊
* 將元素 element 壓入堆疊頂
*
* @param element 入堆疊的元素
*/
void push(E element);
/**
* 出堆疊
* 將當前堆疊頂元素出堆疊并回傳
*
* @return 回傳當前出堆疊的堆疊頂元素
*/
E pop();
/**
* 查看當前堆疊頂元素
*
* @return 回傳當前的堆疊頂元素
*/
E peek();
}
對于 LinkedListStack 類的實作，只需要復用鏈表類中的方法就可實作堆疊的這些基本操作了，具體實作如下：
/**
* 基于 LinkedList 實作的鏈表堆疊
* 支持泛型
*
* @author 踏雪彡尋梅
* @date 2020/2/5 - 12:22
*/
public class LinkedListStack<E> implements Stack<E> {
/**
* 基于該鏈表實作堆疊
*/
private LinkedList<E> linkedList;
/**
* 建構式
* 構造一個空的鏈表堆疊
*/
public LinkedListStack() {
linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(E element) {
linkedList.addFirst(element);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
/**
* 重寫 toString 方法顯示鏈表堆疊中的各資訊
*
* @return 回傳鏈表堆疊的資訊
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedListStack: size = %d, top [ ", getSize()));
for (int i = 0; i < getSize(); i++) {
E e = linkedList.get(i);
result.append(e);
// 如果不是最后一個元素
if (i != getSize() - 1) {
result.append(", ");
}
}
result.append(" ] bottom");
return result.toString();
}
}
接下來，對以上實作做一些測驗，檢測是否和預期結果不符，測驗代碼如下：
/**
* 測驗 LinkedListStack
*/
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
// 判斷堆疊是否為空
System.out.println("==== 測驗 isEmpty ====");
System.out.println("當前堆疊是否為空: " + stack.isEmpty());
System.out.println("\n==== 測驗鏈表堆疊的入堆疊,入堆疊 10 次 ====");
for (int i = 0; i < 10; i++) {
// 入堆疊
stack.push(i);
// 列印入堆疊程序
System.out.println(stack);
}
System.out.println("\n==== 測驗鏈表堆疊的出堆疊,出堆疊 1 次 ====");
// 進行一次出堆疊
stack.pop();
// 查看出堆疊后的狀態
System.out.println(stack);
// 查看當前堆疊頂元素
System.out.println("\n==== 測驗鏈表堆疊的查看堆疊頂元素 ====");
Integer topElement = stack.peek();
System.out.println("當前堆疊頂元素： " + topElement);
// 判斷堆疊是否為空
System.out.println("\n==== 測驗 isEmpty ====");
System.out.println("當前堆疊是否為空: " + stack.isEmpty());
}
測驗結果:
==== 測驗 isEmpty ====
當前堆疊是否為空: true
==== 測驗鏈表堆疊的入堆疊,入堆疊 10 次 ====
LinkedListStack: size = 1, top [ 0 ] bottom
LinkedListStack: size = 2, top [ 1, 0 ] bottom
LinkedListStack: size = 3, top [ 2, 1, 0 ] bottom
LinkedListStack: size = 4, top [ 3, 2, 1, 0 ] bottom
LinkedListStack: size = 5, top [ 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 6, top [ 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 7, top [ 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 8, top [ 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 9, top [ 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 10, top [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
==== 測驗鏈表堆疊的出堆疊,出堆疊 1 次 ====
LinkedListStack: size = 9, top [ 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
==== 測驗鏈表堆疊的查看堆疊頂元素 ====
當前堆疊頂元素： 8
==== 測驗 isEmpty ====
當前堆疊是否為空: false
行程已結束，退出代碼 0
從結果可以看出，實作的結果和預期是相符的，實作了堆疊的各個基本操作，整體的時間復雜度前面也分析過了，都是對鏈表頭部進行操作，時間復雜度是 O(1) 級別的，并且擁有了鏈表的整體動態性，接下來和之前實作的陣列堆疊進行一些效率上的對比：
測驗代碼:
import java.util.Random;
/**
* 對比陣列堆疊和鏈表堆疊的效率差距
*
* @author 踏雪彡尋梅
* @date 2020/2/5 - 12:52
*/
public class Main {
/**
* 測驗使用 stack 運行 opCount 個 push 和 pop 操作所需要的時間,單位: 秒
*
* @param stack 測驗使用的堆疊
* @param opCount 測驗的數量級
* @return 回傳測驗的運行時間,單位: 秒
*/
private static double testStack(Stack<Integer> stack, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
stack.push(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
stack.pop();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 10000;
ArrayStack<Integer> arrayStack = new ArrayStack<>();
double time1 = testStack(arrayStack, opCount);
System.out.println("ArrayStack, time: " + time1 + " s");
LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
double time2 = testStack(linkedListStack, opCount);
System.out.println("LinkedListStack, time: " + time2 + " s");
}
}
測驗結果-1（opCount 為 1 萬時）
測驗結果-2（opCount 為 10 萬時）
測驗結果-3（opCount 為 100 萬時）
測驗結果-4（opCount 為 1000 萬時）
從這幾個測驗結果可以看出在我這臺機器上當資料量較小時，鏈表堆疊耗時比陣列堆疊短，隨著資料量增大，陣列堆疊耗時比鏈表堆疊短，
但歸根結底，這兩個堆疊的入堆疊和出堆疊操作的時間復雜度是同一級別 O(1) 的，
這種有時快有時慢的情況主要跟內部實作相關：
-
對于陣列堆疊來說可能時不時需要重新分配陣列空間進行擴容或者減容，這一操作會消耗一些時間，
-
對于鏈表堆疊來說則是有很多 new 新節點 Node 的操作，這些 new Node 的操作也會消耗一些時間，
所以這兩種堆疊之間的時間對比會出現這種常數倍的差異，屬于正常的情況，它們之間沒有復雜度上的巨大的差異，總體上的時間復雜度還是同一級別的，具體的時間差異最多也就是幾倍的差異，不會產生巨大的差異，
當然，相比陣列堆疊需要時不時重新分配陣列空間達到動態伸縮容量的目的，鏈表堆疊的動態性將會顯得更有優勢一些，不需要我們像陣列堆疊一樣手動地進行伸縮容量處理，
使用鏈表實作佇列
對于佇列這個資料結構，它是針對兩端進行操作，即針對隊首和隊尾進行操作，是一個先入先出的資料結構，
而在之前的鏈表實作中，只有針對鏈表頭的操作是 O(1) 級別的，那么如果用來實作佇列這種資料結構的話，就會有一端的操作是 O(n) 級別的，為了解決這個問題，可以給鏈表添加一個尾指標 tail 用于追蹤鏈表尾部，達到對鏈表首尾兩端的操作都是 O(1) 級別進而實作佇列的目的，
當給鏈表添加尾指標 tail 后，可以發現在尾部洗掉元素是需要從頭遍歷找到前置節點的進行洗掉操作的，這個程序是 O(n) 的，不滿足我們的需求；而如果在尾部添加元素的話，就和在鏈表頭添加元素一個道理，是十分方便的，只需要 O(1) 的復雜度，再看回鏈表頭，由之前的實作可以發現在頭部洗掉元素非常方便，只需要 O(1) 的復雜度，
所以可以設計為在鏈表頭進行洗掉元素的操作，在鏈表尾進行添加元素的操作，即將鏈表頭作為隊首，鏈表尾作為隊尾，
由于在佇列中只需要對兩端進行操作，所以這里實作佇列時就不復用前面實作的鏈表類了，在之前實作的鏈表類中，設計了虛擬頭節點便于統一操作鏈表中的所有資料，而在現在的佇列實作中只需要在頭部洗掉元素在尾部添加元素，所以不需要使用虛擬頭節點，只需要兩個變數 head、tail 分別指向鏈表中的第一個元素和鏈表中的最后一個非 NULL 元素即可，
需要注意的是這樣設計后當佇列為空時，head 和 tail 都指向 NULL，
改進后的鏈表佇列基本結構如下圖所示：
和之前實作堆疊一樣，這里也是實作一個 LinkedListQueue 類實作之前實作陣列佇列時定義的佇列的介面 Queue 來實作佇列的一系列的操作，
回顧佇列的介面 Queue 的實作如下：
/**
* 定義佇列支持的操作的介面
* 支持泛型
*
* @author 踏雪尋梅
* @date 2020/1/9 - 16:52
*/
public interface Queue<E> {
/**
* 獲取佇列中元素個數
*
* @return 佇列中如果有元素,回傳佇列中當前元素個數;佇列中如果沒有元素回傳 0
*/
int getSize();
/**
* 判斷佇列是否為空
*
* @return 佇列為空,回傳 true;佇列不為空,回傳 false
*/
boolean isEmpty();
/**
* 入隊
* 將元素 element 添加到隊尾
*
* @param element 入隊的元素
*/
void enqueue(E element);
/**
* 出隊
* 將隊首的元素出隊并回傳
*
* @return 回傳當前出隊的隊首的元素
*/
E dequeue();
/**
* 查看當前隊首元素
*
* @return 回傳當前的隊首元素
*/
E getFront();
}
對于 LinkedListQueue 類的實作，具體實作如下：
/**
* 鏈表佇列
* 支持泛型
*
* @author 踏雪彡尋梅
* @date 2020/2/5 - 14:45
*/
public class LinkedListQueue<E> implements Queue<E> {
/**
* 鏈表的節點
* 對于用戶而言，不需要知道鏈表的底層結構是怎樣的，只需要知道鏈表是一種線性資料結構，可以增刪改查資料
*/
private class Node {
/**
* 節點存盤的資料
*/
public E element;
/**
* 用于指向下一個節點,使節點與節點之間掛接起來組成鏈表
*/
public Node next;
/**
* 建構式
* 構造一個存有資料并指向了下一個節點的節點
*
* @param element 存往該節點中的資料
* @param next 該節點的下一個節點
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 建構式
* 構造一個存有資料但沒有指向下一個節點的節點
*
* @param element 存往該節點中的資料
*/
public Node(E element) {
this(element, null);
}
/**
* 建構式
* 構造一個空節點
*/
public Node() {
this(null, null);
}
/**
* 重寫 toString 方法以顯示節點中存盤的資料資訊
*
* @return 回傳節點中存盤的資料資訊
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 用于指向鏈表佇列的第一個節點
*/
private Node head;
/**
* 用于指向鏈表佇列的最后一個非 NULL 節點
*/
private Node tail;
/**
* 鏈表佇列當前元素個數
*/
private int size;
/**
* 建構式
* 構造一個空的鏈表佇列
*/
public LinkedListQueue() {
// 鏈表佇列為空時, head 和 tail 都指向 null
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E element) {
if (tail == null) {
// 空隊時入隊
tail = new Node(element);
head = tail;
} else {
// 非空隊時入隊
tail.next = new Node(element);
tail = tail.next;
}
// 維護 size,佇列當前元素個數 + 1
size++;
}
@Override
public E dequeue() {
// 出隊時判斷佇列是否為空
if (isEmpty()) {
throw new IllegalArgumentException("Dequeue failed. Cannot dequeue from an empty queue.");
}
// 記錄要出隊的節點
Node dequeueNode = head;
// 將隊頭節點出隊
head = head.next;
dequeueNode.next = null;
// 如果出隊后佇列為空,維護 tail 指向 null,空隊時 head 和 tail 都指向 null
if (head == null) {
tail = null;
}
// 維護 size,佇列當前元素個數 - 1
size--;
// 回傳出隊元素
return dequeueNode.element;
}
@Override
public E getFront() {
// 獲取隊頭元素時判斷佇列是否為空
if (isEmpty()) {
throw new IllegalArgumentException("GetFront failed. Queue is empty.");
}
// 回傳隊頭元素
return head.element;
}
/**
* 重寫 toString 方法顯示鏈表佇列的詳細資訊
*
* @return 回傳鏈表佇列的詳細詳細
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedListQueue: size: %d, front [ ", getSize()));
// 從鏈表中第一個元素開始遍歷,依次將鏈表中元素資訊添加到結果資訊中
Node currentElement = head;
while (currentElement != null) {
result.append(currentElement + "->");
currentElement = currentElement.next;
}
result.append("NULL ] tail");
return result.toString();
}
}
在實作中需要注意的是在入隊時如果是空佇列需要維護 head 指向 tail，否則 head 會指向 null，以及在出隊時需要判斷出隊后佇列是否為空，如果為空需要維護 tail 指向 null，以及需要注意佇列為空時 head 和 tail 都指向 null，
接下來，對以上實作做一些測驗，檢測是否和預期結果不符，測驗代碼如下：
/**
* 測驗 LinkedListQueue
*/
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
// 判斷佇列是否為空
System.out.println("==== 測驗 isEmpty ====");
System.out.println("當前佇列是否為空: " + queue.isEmpty());
System.out.println("\n==== 測驗入隊和出隊, 10 次 入隊, 每 3 次入隊就出隊 1 次====");
for (int i = 0; i < 10; i++) {
// 入隊
queue.enqueue(i);
// 顯示入隊程序
System.out.println(queue);
// 每入隊 3 個元素就出隊一次
if (i % 3 == 2) {
// 出隊
queue.dequeue();
// 顯示出隊程序
System.out.println("\n" + queue + "\n");
}
}
// 判斷佇列是否為空
System.out.println("\n==== 測驗 isEmpty ====");
System.out.println("當前佇列是否為空: " + queue.isEmpty());
// 獲取隊首元素
System.out.println("\n==== 測驗 getFront ====");
System.out.println(queue);
Integer front = queue.getFront();
System.out.println("當前佇列隊首元素為: " + front);
}
測驗結果:
==== 測驗 isEmpty ====
當前佇列是否為空: true
==== 測驗入隊和出隊, 10 次 入隊, 每 3 次入隊就出隊 1 次====
LinkedListQueue: size: 1, front [ 0->NULL ] tail
LinkedListQueue: size: 2, front [ 0->1->NULL ] tail
LinkedListQueue: size: 3, front [ 0->1->2->NULL ] tail
LinkedListQueue: size: 2, front [ 1->2->NULL ] tail
LinkedListQueue: size: 3, front [ 1->2->3->NULL ] tail
LinkedListQueue: size: 4, front [ 1->2->3->4->NULL ] tail
LinkedListQueue: size: 5, front [ 1->2->3->4->5->NULL ] tail
LinkedListQueue: size: 4, front [ 2->3->4->5->NULL ] tail
LinkedListQueue: size: 5, front [ 2->3->4->5->6->NULL ] tail
LinkedListQueue: size: 6, front [ 2->3->4->5->6->7->NULL ] tail
LinkedListQueue: size: 7, front [ 2->3->4->5->6->7->8->NULL ] tail
LinkedListQueue: size: 6, front [ 3->4->5->6->7->8->NULL ] tail
LinkedListQueue: size: 7, front [ 3->4->5->6->7->8->9->NULL ] tail
==== 測驗 isEmpty ====
當前佇列是否為空: false
==== 測驗 getFront ====
LinkedListQueue: size: 7, front [ 3->4->5->6->7->8->9->NULL ] tail
當前佇列隊首元素為: 3
行程已結束，退出代碼 0
從結果可以看出，實作的結果和預期是相符的，實作了佇列的各個基本操作，整體的時間復雜度前面也簡單分析過了，針對鏈表頭部和尾部進行操作，時間復雜度都是 O(1) 級別的，并且擁有了鏈表的整體動態性，接下來和之前實作的陣列佇列和回圈佇列進行一些效率上的對比：
測驗代碼:
import java.util.Random;
/**
* 測驗 ArrayQueue、LoopQueue 和 LinkedListQueue 的效率差距
*
* @author 踏雪尋梅
* @date 2020/1/8 - 16:49
*/
public class Main2 {
public static void main(String[] args) {
// 測驗資料量
int opCount = 10000;
// 測驗陣列佇列所需要的時間
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double arrayQueueTime = testQueue(arrayQueue, opCount);
System.out.println("arrayQueueTime: " + arrayQueueTime + " s.");
// 測驗回圈佇列所需要的時間
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue, opCount);
System.out.println("loopQueueTime: " + loopQueueTime + " s.");
// 測驗鏈表佇列所需要的時間
LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
double linkedListQueueTime = testQueue(linkedListQueue, opCount);
System.out.println("linkedListQueueTime: " + linkedListQueueTime + " s.");
}
/**
* 測驗使用佇列 queue 運行 opCount 個 enqueue 和 dequeue 操作所需要的時間,單位: 秒
* @param queue 測驗的佇列
* @param opCount 測驗的資料量
* @return 回傳整個測驗程序所需要的時間,單位: 秒
*/
private static double testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.nanoTime();
// 用于生成亂數入隊
Random random = new Random();
// opCount 次 enqueue
for (int i = 0; i < opCount; i++) {
// 入隊
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
// opCount 次 dequeue
for (int i = 0; i < opCount; i++) {
// 出隊
queue.dequeue();
}
long endTime = System.nanoTime();
// 將納秒單位的時間轉換為秒單位
return (endTime - startTime) / 1000000000.0;
}
}
測驗結果-1（opCount 為 1 萬時）
測驗結果-2（opCount 為 10 萬時）
測驗結果-3（opCount 為 100 萬時）
從以上幾種結果可以看出，在我這臺機器上陣列佇列耗時比基于陣列的回圈佇列和鏈表佇列要大的多，基于陣列的回圈佇列耗時和鏈表佇列相差不大，是常數倍的差異，
對于陣列佇列而言它的入隊操作是 O(1) 級別的、出隊操作是 O(n) 級別的，所以在以上測驗中整體時間復雜度是 O(n2) 級別的（進行了 n 次入隊和出隊），
而基于陣列的回圈佇列和鏈表佇列的入隊操作和出隊操作都是 O(1) 級別的，所以在以上測驗中整體而言時間復雜度是 O(n) 級別的（都進行了 n 次入隊和出隊），但這兩者有時候也會出現一個快一點一個慢一點的情況，也是和前面的鏈表堆疊和陣列堆疊的情況是一樣的，這里不再闡述，
總而言之基于陣列實作的回圈佇列和鏈表佇列這兩者是同一級別的復雜度的，相比陣列佇列的時間復雜度快了很多，時間上的差異是巨大的，
最后，鏈表佇列在動態性上相比基于陣列實作的回圈佇列會更好一些，不需要手動進行伸縮容量的實作，
實作到此處，鏈表的常見基本操作也都實作完成了，對于鏈表而言，也還存在著一些改進方案，比如給節點增加一個前置指標域用于指向當前節點的前置節點，使鏈表變成雙鏈表等等，這里就不再實作了，具體程序還是大同小異的，
小結
-
鏈表是一種真正的動態的資料結構，不需要像陣列一樣手動地處理動態伸縮容量，
-
鏈表在針對頭部和尾部做特殊處理后，可以實作堆疊和佇列這兩種資料結構，極大地發揮了鏈表的動態特性，
如有寫的不足的，請見諒，請大家多多指教，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144285.html
標籤：其他
上一篇：0450. Delete Node in a BST (M)
下一篇：遞回的編譯優化(1)