您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

單鏈表完整實現：插入、刪除、查找、長度、清空、連接運算符重載

編輯：程式設計綜合問答

需求覆蓋

插入（任意位置）
刪除（含中間節點）
查找（按值/位置）
計算長度
清空
鏈表連接（重載 `operator+` / `operator+=`）
驗證主程序

C++ 完整實現

#include <iostream>
#include <stdexcept>

template <typename T>
class List {
    struct Node {
        T data;
        Node* next;
        Node(const T& v, Node* n = nullptr) : data(v), next(n) {}
    };
    Node* head = nullptr;
    size_t sz = 0;

public:
    ~List() { clear(); }
    
    // 禁止拷貝，避免淺拷貝雙重釋放
    List(const List&) = delete;
    List& operator=(const List&) = delete;
    
    // 移動語義
    List(List&& other) noexcept : head(other.head), sz(other.sz) {
        other.head = nullptr; other.sz = 0;
    }
    List& operator=(List&& other) noexcept {
        if (this != &other) { clear(); head = other.head; sz = other.sz; other.head = nullptr; other.sz = 0; }
        return *this;
    }

    // 1. 插入：pos 為 0~size，頭插/尾插/中間插
    void insert(size_t pos, const T& val) {
        if (pos > sz) throw std::out_of_range("pos");
        if (pos == 0) { head = new Node(val, head); }
        else {
            Node* p = head;
            for (size_t i = 0; i < pos - 1; ++i) p = p->next;
            p->next = new Node(val, p->next);
        }
        ++sz;
    }
    
    // 2. 刪除：pos 為 0~size-1
    void erase(size_t pos) {
        if (pos >= sz) throw std::out_of_range("pos");
        Node* del;
        if (pos == 0) { del = head; head = head->next; }
        else {
            Node* p = head;
            for (size_t i = 0; i < pos - 1; ++i) p = p->next;
            del = p->next;
            p->next = del->next;
        }
        delete del;
        --sz;
    }
    
    // 3. 查找值（返回首個位置，未找到返回 npos）
    size_t find(const T& val) const {
        size_t i = 0;
        for (Node* p = head; p; p = p->next, ++i)
            if (p->data == val) return i;
        return static_cast<size_t>(-1); // npos
    }
    
    // 4. 長度
    size_t size() const { return sz; }
    
    // 5. 清空
    void clear() {
        while (head) { Node* t = head; head = head->next; delete t; }
        sz = 0;
    }
    
    // 6. 連接：this += other（移動 other 節點，other 變空）
    List& operator+=(List&& other) {
        if (!other.head) return *this;
        if (!head) { head = other.head; }
        else {
            Node* p = head;
            while (p->next) p = p->next;
            p->next = other.head;
        }
        sz += other.sz;
        other.head = nullptr; other.sz = 0;
        return *this;
    }
    friend List operator+(List a, List&& b) { return std::move(a += std::move(b)); }
    
    // 打印輔助
    void print() const {
        for (Node* p = head; p; p = p->next)
            std::cout << p->data << (p->next ? " -> " : "\n");
    }
};

// 驗證主程序
int main() {
    List<int> a, b;
    a.insert(0, 10); a.insert(1, 20); a.insert(2, 30);
    b.insert(0, 40); b.insert(1, 50);
    
    std::cout << "a: "; a.print();          // 10 -> 20 -> 30
    std::cout << "b: "; b.print();          // 40 -> 50
    std::cout << "a.size=" << a.size() << "\n"; // 3
    std::cout << "find 20: " << a.find(20) << "\n"; // 1
    
    a.erase(1);                              // 刪除 20
    std::cout << "after erase: "; a.print(); // 10 -> 30
    
    List<int> c = std::move(a) + std::move(b); // 連接
    std::cout << "c: "; c.print();          // 10 -> 30 -> 40 -> 50
    std::cout << "a empty? " << (a.size()==0) << " b empty? " << (b.size()==0) << "\n"; // 1 1
    
    c.clear();
    std::cout << "c cleared, size=" << c.size() << "\n"; // 0
    return 0;
}

關鍵設計決策

決策	理由
模板類	泛型復用，支持任意類型
禁止拷貝構造/賦值	鏈表擁有節點所有權，淺拷貝導致雙重 delete
提供移動語義	連接操作 `operator+=` 接收右值引用，零拷貝轉移所有權
`operator+` 返回值	利用 NRVO/移動構造，避免額外拷貝
析構函數調用 `clear()`	RAII 確保無內存洩漏
異常安全	`new` 失敗拋 `bad_alloc`，狀態不變