寫給我自己看的資料結構筆記-LinkedList
這篇文章會簡單介紹 LinkedList，一個左手握著資料，右手握著下一個 Node 的結構。
LinkedList
何謂 LinkedList ? 是一種常見的數據結構，通常由一系列 Node 組成，Node 包含兩個部分：
- 數據：很直白，就是數據啦
- 指針：用來指向下一個 Node，這樣我才知道接下來找誰。
HEAD TAIL
↓ ↓
[1] -> [2] -> [3] -> [4] -> null
類型
在 Java 的 LinkedList 中，主要分為以下兩種類型：
-
單向鏈接串列（Singly Linked List）： 每個節點包含數據和指向下一個節點的引用。由於只有一個方向的引用，插入和刪除節點的操作相對簡單，需要的記憶體空間也比較少。
-
雙向鏈接串列（Doubly Linked List）： 每個節點同時包含指向上一個節點和指向下一個節點的引用。這樣的結構使得在某些情況下操作更加方便，例如反向查詢。然而，相對於單向鏈接串列，雙向鏈接串列需要更多的內存空間。
通常還會在網路上還會看到一種 環狀鏈接串列，其實就是把 TAIL 原先指向 null 的改為 HEAD，這樣看起來就像一個圓圈，故稱為環狀鏈接串列。
這邊我再以 Node 方式說明，我先說明 Node :
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
在這個結構中：
- Node 是一個表示 linkedlist 中單一元素的類別。
- data 是整數，儲存節點的值。當然你也可以依據你的需求來定義類型。
- next 是對 linkedlist 中下一個節點的 reference。 如果沒有下一個節點，則 next 為 null。
public class Main {
public static void main(String[] args) {
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second;
second.next = third;
System.out.println(head); // Output: 1 -> 2 -> 3
}
}
在這個範例中，我建立了三個 Node，並設定好 Node 的 reference，這樣就是一個簡單的 LinkedList，不過這是單向的，雙向的話就是要再多一個 reference。
內部實現
我們可以去翻翻看原始碼：Link
其中你會發現：
private static final class Entry<T> {
/** The element in the list. */
T data;
/** The next list entry, null if this is last. */
Entry<T> next;
/** The previous list entry, null if this is first. */
Entry<T> previous;
/**
* Construct an entry.
* @param data the list element
*/
Entry(T data) {
this.data = data;
}
} // class Entry
他給了兩個 reference，代表 Java 的 linkedlist是雙向的。
操作方式
LinkedList 提供了許多操作的方法，例如添加、刪除、獲取元素等。以下是一些常見的操作方式：
// 添加元素到列表尾部
linkedList.add("Date");
// 在指定位置插入元素
linkedList.add(2, "Grape");
// 獲取指定位置的元素
String fruit = linkedList.get(1);
// 刪除指定位置的元素
linkedList.remove(3);
// 獲取列表的大小
int size = linkedList.size();
// 檢查列表是否包含某個元素
boolean containsBanana = linkedList.contains("Banana");
結論
LinkedList 是一種靈活的數據結構，具有動態大小和方便插入、刪除的特性。它可以用於各種場景，但在某些操作效率上可能不如其他數據結構高效，例如隨機訪問元素。
因此，我們在使用時需要根據實際應用場景選擇適當的數據結構。
這篇因為自己近期有點忙又有點想休息，寫得比較簡略一點，以後有時間會再回來新增的