C++模板实现高性能双向链表

双向链表是一种重要的数据结构，它允许在链表的任意位置进行高效的插入和删除操作。本文将介绍如何使用C++模板实现一个通用的双向链表，并提供详细的代码示例和解释。

代码实现

以下是使用 C++ 实现的双向链表类的示例代码：

#include <iostream>

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

    Node* head;
    Node* tail;
    int size;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}

    ~DoublyLinkedList() {
        clean();
    }

    bool isEmpty() const {
        return size == 0;
    }

    int getSize() const {
        return size;
    }

    void clean() {
        Node* current = head;
        while (current != nullptr) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
        head = nullptr;
        tail = nullptr;
        size = 0;
    }

    void insert(const T& value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }

    void remove(const T& value) {
        if (isEmpty()) {
            return;
        }
        Node* current = head;
        while (current != nullptr && current->data != value) {
            current = current->next;
        }
        if (current == nullptr) {
            return;
        }
        if (current == head && current == tail) {
            head = nullptr;
            tail = nullptr;
        } else if (current == head) {
            head = current->next;
            head->prev = nullptr;
        } else if (current == tail) {
            tail = current->prev;
            tail->next = nullptr;
        } else {
            current->prev->next = current->next;
            current->next->prev = current->prev;
        }
        delete current;
        size--;
    }

    void print() const {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << ' ';
            current = current->next;
        }
        std::cout << std::endl;
    }

    DoublyLinkedList(const DoublyLinkedList& other) : head(nullptr), tail(nullptr), size(0) {
        Node* current = other.head;
        while (current != nullptr) {
            insert(current->data);
            current = current->next;
        }
    }

    DoublyLinkedList& operator=(const DoublyLinkedList& other) {
        if (this != &other) {
            clean();
            Node* current = other.head;
            while (current != nullptr) {
                insert(current->data);
                current = current->next;
            }
        }
        return *this;
    }
};

int main() {
    DoublyLinkedList<int> list;
    std::cout << 'Is list empty? ' << (list.isEmpty() ? 'Yes' : 'No') << std::endl;
    std::cout << 'Size of list: ' << list.getSize() << std::endl;

    list.insert(5);
    list.insert(10);
    list.insert(15);
    list.insert(20);

    std::cout << 'Print list: ';
    list.print();

    std::cout << 'Is list empty? ' << (list.isEmpty() ? 'Yes' : 'No') << std::endl;
    std::cout << 'Size of list: ' << list.getSize() << std::endl;

    list.remove(10);
    std::cout << 'Print list after removing 10: ';
    list.print();

    DoublyLinkedList<int> newList = list;
    std::cout << 'Print new list after copy: ';
    newList.print();

    DoublyLinkedList<int> anotherList;
    anotherList = list;
    std::cout << 'Print another list after assignment: ';
    anotherList.print();

    return 0;
}

代码说明

• 模板类型 T: 该代码使用模板来实现一个通用的双向链表，可以存储任何数据类型。
• Node 结构体: 表示链表中的一个节点，包含数据 data、指向前一个节点的指针 prev 和指向后一个节点的指针 next。
• head 和 tail 指针: 分别指向链表的第一个节点和最后一个节点。
• size 成员变量: 存储链表中节点的数量。
• 构造函数、析构函数和拷贝构造函数: 用于创建、销毁和复制链表对象。
• isEmpty() 函数: 检查链表是否为空。
• getSize() 函数: 返回链表的大小。
• clean() 函数: 清空链表，释放所有节点占用的内存。
• insert() 函数: 在链表尾部插入一个新节点。
• remove() 函数: 从链表中删除指定值的节点。
• print() 函数: 打印链表中所有节点的数据。

总结

本文介绍了如何使用 C++ 模板实现一个通用的双向链表，并提供了详细的代码示例和说明。双向链表是一种非常有用的数据结构，可以用于实现各种应用程序，例如列表、队列和堆栈。