Qt 中实现链表

Qt 中实现链表，我将使用模板类来支持泛型数据，并通过封装确保数据安全。

完整实现代码

#include <QCoreApplication>
#include <QDebug>
#include <functional> // 用于遍历时的回调函数

template<typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data) : data(data), next(nullptr) {}
    };

    Node* head;

public:
    // 构造函数
    LinkedList() : head(nullptr) {}

    // 析构函数：释放所有节点
    ~LinkedList() {
        clear();
    }

    // 禁止拷贝构造和赋值（或实现深拷贝）
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;

    // 清空链表
    void clear() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
    }

    // 在头部插入
    void prepend(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // 在尾部插入
    void append(const T& value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 删除第一个匹配项
    bool remove(const T& value) {
        Node* prev = nullptr;
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                if (prev == nullptr) {
                    head = current->next;
                } else {
                    prev->next = current->next;
                }
                delete current;
                return true;
            }
            prev = current;
            current = current->next;
        }
        return false;
    }

    // 判断是否为空
    bool isEmpty() const {
        return head == nullptr;
    }

    // 获取链表长度
    int size() const {
        int count = 0;
        Node* current = head;
        while (current != nullptr) {
            count++;
            current = current->next;
        }
        return count;
    }

    // 遍历链表，使用回调处理每个元素
    void traverse(const std::function<void(const T&)>& func) const {
        Node* current = head;
        while (current != nullptr) {
            func(current->data);
            current = current->next;
        }
    }
};

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);

    LinkedList<int> list;

    // 插入测试
    list.append(1);
    list.append(2);
    list.prepend(0);

    // 遍历打印
    qDebug() << "链表内容:";
    list.traverse([](int value) {
        qDebug() << value;
    });

    // 删除测试
    list.remove(2);
    qDebug() << "\n删除 2 后的链表:";
    list.traverse([](int value) {
        qDebug() << value;
    });

    return a.exec();
}

关键点说明

1. 节点结构：

   • 使用内部 Node 结构体封装链表节点，包含 data 和 next 指针。
   • 节点仅在链表类内部可见，确保数据封装。

2. 内存管理：

   • 析构函数：遍历链表并删除所有节点，避免内存泄漏。
   • clear() 方法：提供手动清空链表的功能。
   • 禁用拷贝：默认禁用拷贝构造和赋值，防止浅拷贝问题。如需深拷贝，需自定义实现。

3. 核心操作：

   • 插入：支持头部 (prepend) 和尾部 (append) 插入。
   • 删除：删除第一个匹配值 (remove)。
   • 遍历：通过 traverse 方法接受回调函数，安全访问每个元素。

4. 辅助功能：

   • isEmpty：检查链表是否为空。
   • size：获取链表长度。
   • 遍历输出：结合 Qt 的 qDebug 输出链表内容。

5. Qt 集成：

   • 虽然示例中没有使用 GUI 组件，但可通过信号槽机制扩展。例如，在数据修改时发射信号通知界面更新（需继承 QObject 并使用 Q_OBJECT 宏）。

扩展建议

• 迭代器支持：可实现迭代器类，支持基于范围的 for 循环。
• 异常处理：在内存分配失败时添加异常处理逻辑。
• 模板特化：针对特定类型（如 QString）优化操作。

此实现提供了一个健壮的链表基础结构，可直接在 Qt 项目中使用。