C++ Linked List 實作完整指南

,

C++ Linked List 實作完整指南

簡介

Linked List 是一個基礎但重要的資料結構，特別適合需要頻繁插入刪除以及動態調整大小的場景。理解 Array 和 Linked List 之間的差異，以及如何在 C++ 中實作它們，是每位程式設計師必經的學習歷程。

與 Array 的比較

記憶體與效能特性

特性 Array Linked List
記憶體配置 連續空間 非連續空間
存取時間 O(1) O(n)
插入時間 O(n) O(1)
刪除時間 O(n) O(1)
大小彈性 固定 動態

使用時機

Array 適合的情況：

  • 需要頻繁隨機存取
  • 記憶體使用需要可預測
  • Cache 效能很重要
  • 大小固定且已知

Linked List 適合的情況：

  • 需要頻繁插入/刪除
  • 需要動態調整大小
  • 記憶體碎片化是個考量
  • 主要是循序存取

基本結構

Linked List 由節點（Node）組成，每個節點包含：

  • 資料欄位（Data field）
  • 指向下一個節點的指標（Next pointer）

alt text

實作方式

Node 結構定義

1
2
3
4
5
struct Node {
    int data;
    Node* next;
    Node(int val): data(val), next(nullptr) {}
};

基本操作流程

alt text

基本操作

1. 插入操作

在開頭插入

alt text

1
2
3
4
5
void insertAtHead(Node* head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

在尾部插入

alt text

1
2
3
4
5
6
7
8
9
10
void insertAtTail(Node* head, int val) {
    Node* newNode = new Node(val);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
}

2. 刪除操作

alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void deleteNode(Node* head, int val) {
    if (!head) return;
    
    if (head->data == val) {
        Node* toDelete = head;
        head = head->next;
        delete toDelete;
        return;
    }
    
    Node* temp = head;
    while (temp->next && temp->next->data != val) {
        temp = temp->next;
    }
    
    if (temp->next) {
        Node* toDelete = temp->next;
        temp->next = temp->next->next;
        delete toDelete;
    }
}

3. 遍歷print操作

1
2
3
4
5
6
7
8
void display(Node* head) {
    Node* temp = head;
    while (temp) {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    }
    std::cout << "NULL" << std::endl;
}

記憶體管理

在 Linked List 的實作中，記憶體管理是最容易出錯，也是最重要的部分。不當的記憶體管理可能導致：

  • 程式崩潰（Program Crash）
  • 記憶體洩漏（Memory Leak）
  • 不可預期的行為（Undefined Behavior）
  • 系統資源浪費

1. Memory Leak（記憶體洩漏）

問題描述

當我們使用 new 配置記憶體但忘記使用 delete 釋放時，就會發生記憶體洩漏。

常見的記憶體洩漏情況

1
2
3
4
5
6
7
8
9
10
11
// 錯誤示範
void wrongDelete(Node* head) {
    head = head->next;  // 原始的 head 節點記憶體永遠無法被釋放
}

// 正確做法
void correctDelete(Node*& head) {
    Node* temp = head;
    head = head->next;
    delete temp;  // 適當釋放記憶體
}

預防方法

  1. 確保每個 new 都對應到一個 delete
  2. 實作解構子（Destructor）來清理整個串列
1
2
3
4
5
6
7
8
9
10
11
12
class LinkedList {
private:
    Node* head;
public:
    ~LinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

2. Dangling Pointer（懸空指標 or 迷途指標）

問題描述

當指標指向的記憶體已經被釋放，但指標本身還未更新時，就會產生懸空指標。

常見的懸空指標情況

1
2
3
4
5
6
7
8
9
10
11
12
// 錯誤示範
void dangerousOperation(Node* current) {
    delete current->next;  // 釋放記憶體
    // current->next 現在是懸空指標
    current->next->data = 5;  // 危險操作！存取已釋放的記憶體
}

// 正確做法
void safeOperation(Node* current) {
    delete current->next;
    current->next = nullptr;  // 立即將指標設為 nullptr
}

預防方法

  1. 釋放記憶體後立即將指標設為 nullptr
  2. 在操作指標前檢查其有效性

3. Smart Pointer（智慧指標）

Modern C++ 提供了智慧指標來自動管理記憶體，最常用於 Linked List 的是 std::unique_ptr。

使用 Smart Pointer 的好處

  1. 自動記憶體管理
  2. 避免記憶體洩漏
  3. 更安全的資源管理
  4. 符合 RAII 原則

完整實作範例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <memory>

struct ModernNode {
    int data;
    std::unique_ptr<ModernNode> next;
    
    ModernNode(int val) : data(val), next(nullptr) {}
};

class ModernLinkedList {
private:
    std::unique_ptr<ModernNode> head;

public:
    // 插入節點
    void insert(int val) {
        auto newNode = std::make_unique<ModernNode>(val);
        if (!head) {
            head = std::move(newNode);
        } else {
            newNode->next = std::move(head);
            head = std::move(newNode);
        }
    }

    // 不需要解構子！智慧指標會自動處理記憶體釋放
};

使用 Smart Pointer 時的注意事項

  1. std::unique_ptr 不能共享所有權，移動時原指標會變成 nullptr
  2. 需要使用 std::move 來轉移所有權
  3. 不能直接複製 unique_ptr，需要特別處理鏈結操作

除錯技巧

  1. 使用記憶體檢查工具

    • Valgrind（Linux）
    • Visual Studio 的記憶體檢查（Windows）
    • Address Sanitizer（跨平台）

  2. 建立測試案例

1
2
3
4
5
6
7
8
void testMemoryManagement() {
    LinkedList list;
    for (int i = 0; i < 1000; i++) {
        list.insert(i);
        list.remove(i/2);
    }
    // 如果沒有記憶體洩漏，程式正常結束
}

結論

Linked List 提供了一種靈活的方式來管理動態資料結構。雖然它可能不是每種情況下最佳的選擇，但理解其實作方式和特性對於軟體開發者來說非常重要。

在選擇資料結構時，要根據專案的具體需求來決定，同時確保在實作 Linked List 時做好適當的記憶體管理。