【科技友瘋狂】Linked List：你還在用陣列？試試這個更靈活的資料結構！

寫程式時，陣列（Array）看似無敵——索引存取快，記憶體連續，CPU快取友善。

但當你開始頻繁插入、刪除資料時，陣列的弱點立刻浮現：

插入/刪除 = O(n)，因為每次都得搬動後面的元素。
大小固定，擴容時必須重新配置記憶體，效率低。

? 解法？改用 Linked List！
Linked List 透過指標（Pointer）將節點串連，不受記憶體連續性限制，動態調整大小，插入刪除只需 O(1)。

Singly Linked List（單向鏈結串列）實作

#include <iostream>


using namespace std;

struct Node {
int data;
Node* next;

Node(int val) : data(val), next(nullptr) {} // 建構子
};

class LinkedList {
public:
Node* head;

LinkedList() : head(nullptr) {}

// 頭部插入 O(1)
void insertFront(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}

// 刪除節點 O(n)
void deleteNode(int val) {
if (!head) return;
if (head->data == val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* curr = head;
while (curr->next && curr->next->data != val) {
curr = curr->next;
}
if (curr->next) {
Node* temp = curr->next;
curr->next = curr->next->next;
delete temp;
}
}

// 列印鏈結串列
void printList() {
Node* curr = head;
while (curr) {
cout << curr->data << " -> ";
curr = curr->next;
}
cout << "NULL\n";
}
};

int main() {
LinkedList list;
list.insertFront(3);
list.insertFront(5);
list.insertFront(7);

cout << "初始鏈結串列: ";
list.printList();

list.deleteNode(5);
cout << "刪除 5 後: ";
list.printList();

return 0;
}

Linked List 的優勢

✅ 插入/刪除快（O(1) 在頭部）
✅ 動態記憶體管理（不浪費空間）
✅ 無需搬動元素（適合頻繁變動的資料）

但它的缺點是…

❌ 隨機存取慢（O(n) 遍歷）
❌ 額外的記憶體開銷（每個節點多一個指標）

陣列 vs. Linked List，什麼時候該用？

? 用 Linked List：當插入/刪除頻繁，大小不固定。
? 用 Array：當需要隨機存取，且資料大小已知。

? 記住：Linked List ≠ 絕對優勢，但在對的場景，它就是無可取代的神器！

你更喜歡哪種資料結構？留言討論！?