C++ 封裝鏈式表（Linked List）完整實現與測試

面向對象三大特性——封裝、繼承、多態——是 C++ 相較於面向過程語言的核心優勢。本文將以「鏈式表」為例，示範如何運用這三大特性，從零構建一個具備自動記憶體管理、迭代器遍歷、泛型支援的現代化 C++ 容器。

鏈式結構分析

鏈表與線性表（陣列）最大的不同在於邏輯結構不連續，而是透過「前驅-後繼」指標串聯節點。優點在於插入/刪除效率高（O(1)），適合頻繁增刪的場景；缺點是隨機訪問需 O(n)。鏈表節點通常在堆區動態分配，需手動管理記憶體。

核心類別設計

1. 節點類 ZLinkedListNode<T>

• 資料成員：_data、_nextNode
• 提供多種建構函數、資料存取（data() 回傳副本、ref() 回傳引用）、下一節點操作

2. 容器類 ZLinkedList<T> : public Sequence<T>

繼承抽象基類 Sequence，實現：

• 頭/尾指標（_list_head、_list_tail）加速尾插
• push_back、pop、at、remove、operator[]
• 長度管理 _length、空表判斷 isEmpty()
• 迭代器工廠方法 iterator()

3. 迭代器類 ZLinkedListIterator<T> : public Iterator<T>

• 支援 next()、hasNext()、data()、前置/後置 ++ 運算子
• 內部持有 _list 與游標 pointTo

關鍵實現細節

// 尾插優化：O(1)
void push_back(const T& val) {
    ++_length;
    if (!_list_head) _list_head = _list_tail = new Node(val);
    else _list_tail = new Node(val, *_list_tail);
}

// 刪除節點：處理頭節點與中間節點
bool remove(const rank pos) {
    if (pos >= _length) return false;
    --_length;
    if (pos == 0) { /* 刪頭 */ }
    else { /* 遍歷至 pos-1，重鏈接並 delete */ }
    return true;
}

完整測試驗證

基本型別測試

ZLinkedList<int> list;
list.push_back(2); list.push_back(3); list.push_back(5);
auto it = list.iterator();
while (it.hasNext()) cout << it.data() << endl, ++it;
list.remove(0);
it = list.iterator(); // 迭代器失效需重置
while (it.hasNext()) cout << it.data() << endl, ++it;

自訂類別測試

class Student { /* name, age, display() */ };
ZLinkedList<Student> list;
list.push_back(Student("zz", 19));
list.push_back(Student("ee", 20));
list.push_back(Student("ff", 21));
// 迭代遍歷並呼叫 display()

測試結果顯示：封裝正確、迭代器行為符合預期、記憶體管理無洩漏。

設計心得

1. 抽象基類（Sequence/Iterator）實現「面向介面編程」，容器與演算法解耦。
2. 模板泛型 讓同一份代碼支援任意型別，體現 STL 核心思想。
3. RAII：建構函數獲取資源，解構函數 ~ZLinkedList() 循環 remove(0) 釋放所有節點。
4. 迭代器失效：結構修改後必須重新獲取迭代器，避免懸空指標。

完整頭檔 ZLinkedList.hpp 已整理於文末，可直接納入專案使用。