C++ 實驗：手寫單向鏈表（深拷貝、記憶體管理、排序）完整實作

實驗目標

實作 list 類別，模擬 std::list 核心功能：動態配置節點、深拷貝建構/指派、插入/刪除任意位置、轉字串、排序。重點驗證指標操作、記憶體無洩漏、邊界條件處理。

介面定義 (list.hpp)

struct node {
    int data;
    node* next;
    node(int d=0, node* n=nullptr) : data(d), next(n) {}
};

class list {
    node* head;
    int _size;
public:
    list();                     // 預設建構
    list(const list&);          // 拷貝建構
    list& operator=(const list&); // 複製指派
    ~list();                    // 解構
    bool empty() const;
    int size() const;
    string toString() const;    // "1->2->3->NULL"
    void insert(int pos, const int& val);
    void erase(int pos);
    void clear();
    list& sort();               // 升序排序
};

核心難點與解法

1. 深拷貝 vs 淺拷貝

• 淺拷貝：直接複製 head 指標 → 兩物件共享節點 → 雙重釋放崩潰。
• 深拷貝：逐節點 new 新節點，複製資料 → 獨立記憶體。

2. 複製指派運算子

list& list::operator=(const list& rhs) {
    if (this != &rhs) {           // 自我指派檢查
        clear();                  // 釋放舊資源
        if (rhs.head) {
            head = new node(rhs.head->data);  // 複製首節點
            node* dst = head;
            for (node* src = rhs.head->next; src; src = src->next) {
                dst->next = new node(src->data);
                dst = dst->next;
            }
        }
        _size = rhs._size;
    }
    return *this;  // 返回 *this 支援鏈式指派
}

3. 插入/刪除邊界條件

4. 排序演算法選擇

• 插入排序：適合鏈表，原地重鏈節點，O(n²) 但無額外空間。
• 歸併排序：O(n log n)，需遞歸分割合併，較複雜。
• 教學版常用轉陣列排序再寫回 (O(n) 額外空間)，簡單易懂。

參考實作 (關鍵函數)

// toString: "1->2->3->NULL"
string list::toString() const {
    ostringstream oss;
    for (node* p = head; p; p = p->next) {
        oss << p->data << "->";
    }
    oss << "NULL";
    return oss.str();
}

// insert
void list::insert(int pos, const int& val) {
    if (pos < 0 || pos > _size) return;
    if (pos == 0) {
        head = new node(val, head);
    } else {
        node* p = head;
        for (int i = 0; i < pos-1; ++i) p = p->next;
        p->next = new node(val, p->next);
    }
    ++_size;
}

// erase
void list::erase(int pos) {
    if (pos < 0 || pos >= _size) return;
    node* del = nullptr;
    if (pos == 0) {
        del = head;
        head = head->next;
    } else {
        node* p = head;
        for (int i = 0; i < pos-1; ++i) p = p->next;
        del = p->next;
        p->next = del->next;
    }
    delete del;
    --_size;
}

// sort: 簡單選擇排序 (交換資料而非節點)
list& list::sort() {
    for (node* i = head; i; i = i->next) {
        node* min = i;
        for (node* j = i->next; j; j = j->next)
            if (j->data < min->data) min = j;
        if (min != i) swap(i->data, min->data);
    }
    return *this;
}

除錯與記憶體檢查建議

1. 使用 Valgrind / AddressSanitizer (-fsanitize=address) 檢測洩漏、越界、雙重釋放。
2. 每個 new 對應唯一 delete，畫圖追蹤指標變化。
3. 邊界測試：空表、單節點、頭/尾/中間操作、非法位置。
4. 拷貝建構/指派測試：修改副本不影響原表、自我指派安全。

學習心得

鏈表是理解指標、動態記憶體、擁有權語意的最佳練習。掌握深拷貝、RAII、邊界處理，為後續學習 STL 容器實作、智慧指標、資料結構打下堅實基礎。

1. 上一篇文章： C++ 智慧指標進階：shared_ptr 循環引用與自定義刪除器深度解析
2. 下一篇文章： C++ 實戰：支付寶用戶系統核心類實作 (格式驗證、資金操作、命名空間)

關於C++

動態多態與靜態多態：C++ 兩種多態機制的深度對比與工程選型

面向物件三大特性：封裝、繼承、多態。多態是實現擴展性與解耦的

Google Protobuf 網路傳輸方案：自動反射訊息類型的編碼與解碼

解決核心問題：接收 Protobuf 資料後，如何自動建立具

POJ 1375 Intervals：解析幾何求圓外切線投影區間

問題背景 給定一個光源點與若干圓形障礙物，求光源在 Y 軸上

C++ 進階程式設計：檔案流、異常處理、動態記憶體與命名空間實戰

檔案 I/O：<fstream> 完整指南 C+