C++ 模板類實現單鏈表 - 完整代碼與測試範例

設計目標

使用 C++ 模板實現泛型單鏈表，支援基本操作：尾插、尾刪、拷貝構造、賦值運算符、遍歷輸出。

核心類結構

// 節點類
template 
class ListNode {
public:
    DataType _data;
    ListNode* _next;
    ListNode(const DataType& x) : _data(x), _next(nullptr) {}
    ~ListNode() {}
};

// 單鏈表類
template 
class LinkList {
private:
    ListNode* _pHead;
    ListNode* _pTail;
    size_t _size;
public:
    LinkList() : _pHead(nullptr), _pTail(nullptr), _size(0) {}
    LinkList(const LinkList& other);           // 拷貝構造
    ~LinkList();                               // 析構
    void PushBack(const DataType& data);       // 尾插
    void PopBack();                            // 尾刪
    void operator=(const LinkList& other);     // 賦值運算符
    void Display() const;                      // 遍歷輸出
};

關鍵方法實現

尾插操作

template 
void LinkList::PushBack(const DataType& data) {
    if (!_pHead) {
        _pHead = _pTail = new ListNode(data);
    } else {
        _pTail->_next = new ListNode(data);
        _pTail = _pTail->_next;
    }
    ++_size;
}

尾刪操作

template 
void LinkList::PopBack() {
    if (!_pHead) return;
    if (_pHead == _pTail) {
        delete _pHead;
        _pHead = _pTail = nullptr;
    } else {
        ListNode* prev = _pHead;
        while (prev->_next != _pTail) prev = prev->_next;
        delete _pTail;
        _pTail = prev;
        _pTail->_next = nullptr;
    }
    --_size;
}

拷貝構造與賦值運算符（深拷貝）

template 
LinkList::LinkList(const LinkList& other) 
    : _pHead(nullptr), _pTail(nullptr), _size(0) {
    for (auto* cur = other._pHead; cur; cur = cur->_next)
        PushBack(cur->_data);
}

template 
void LinkList::operator=(const LinkList& other) {
    if (this == &other) return;
    // 清空當前鏈表
    while (_pHead) PopBack();
    // 深拷貝
    for (auto* cur = other._pHead; cur; cur = cur->_next)
        PushBack(cur->_data);
}

測試主程序

#include 
#include 
#include "LinkList.h"
using namespace std;

void test() {
    LinkList l1;
    l1.PushBack("帥哥 0");
    l1.PushBack("帥哥 1");
    l1.PushBack("帥哥 2");
    l1.Display();  // 帥哥 0-->帥哥 1-->帥哥 2-->NULL
    
    LinkList l2(l1);  // 拷貝構造
    l2.Display();
    
    l2.PopBack(); l2.PopBack();
    l2.Display();  // 帥哥 0-->NULL
    
    l2 = l1;  // 賦值運算符
    l2.Display();  // 帥哥 0-->帥哥 1-->帥哥 2-->NULL
}

int main() {
    test();
    return 0;
}

運行結果

帥哥 0-->帥哥 1-->帥哥 2-->NULL
帥哥 0-->帥哥 1-->帥哥 2-->NULL
帥哥 0-->NULL
帥哥 0-->帥哥 1-->帥哥 2-->NULL

設計要點總結

• 使用雙指針 _pHead/_pTail 實現 O(1) 尾插
• 深拷貝避免多對象共享節點導致的雙重釋放
• 析構函數遞歸刪除所有節點，防止記憶體洩漏
• 模板支援任意可拷貝類型（內建類型、std::string、自定義類等）