双向链表的操作代码实现

1. 引言

在数据结构中，双向链表是一种常用的数据结构，它不仅能够向前访问节点元素，还能通过指针指向前一个节点进行逆序访问。本文将详细介绍如何使用C++语言来实现双向链表的基本操作，包括添加、删除和遍历等方法。

2. 双向链表的定义

首先，我们先定义双向链表以及其中结点的数据结构：

template <typename T>
struct Node {
    T data;
    Node<T>* prev;
    Node<T>* next;

    Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};

template <typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList();
    ~DoublyLinkedList();

    void addFront(const T& value);
    void addBack(const T& value);
    bool remove(const T& value);
    void printList() const;

private:
    Node<T>* head;
    Node<T>* tail;
};

3. 双向链表的基本操作

3.1 添加节点

3.1.1 在头部添加（addFront）

template <typename T>
void DoublyLinkedList<T>::addFront(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (head == nullptr) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

3.1.2 在尾部添加（addBack）

template <typename T>
void DoublyLinkedList<T>::addBack(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (tail == nullptr) {
        head = tail = newNode;
    } else {
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
}

3.2 删除节点

3.2.1 根据值删除（remove）

template <typename T>
bool DoublyLinkedList<T>::remove(const T& value) {
    Node<T>* current = head;

    while (current != nullptr) {
        if (current->data == value) {
            if (current->prev != nullptr)
                current->prev->next = current->next;
            else
                head = current->next; // 如果删除的是头结点

            if (current->next != nullptr)
                current->next->prev = current->prev;
            else
                tail = current->prev; // 如果删除的是尾节点

            delete current;
            return true; // 成功移除元素
        }
        current = current->next;
    }

    return false; // 未找到该值，未移除任何元素
}

3.3 遍历链表

3.3.1 打印链表（printList）

template <typename T>
void DoublyLinkedList<T>::printList() const {
    Node<T>* current = head;

    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

4. 完整的双向链表类实现

#include <iostream>

template <typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList();
    ~DoublyLinkedList();

    void addFront(const T& value);
    void addBack(const T& value);
    bool remove(const T& value);
    void printList() const;

private:
    Node<T>* head;
    Node<T>* tail;
};

template <typename T>
DoublyLinkedList<T>::DoublyLinkedList() : head(nullptr), tail(nullptr) {}

template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
    while (head != nullptr) {
        Node<T>* temp = head->next;
        delete head;
        head = temp;
    }
}

template <typename T>
void DoublyLinkedList<T>::addFront(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (head == nullptr) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

template <typename T>
void DoublyLinkedList<T>::addBack(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (tail == nullptr) {
        head = tail = newNode;
    } else {
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
}

template <typename T>
bool DoublyLinkedList<T>::remove(const T& value) {
    Node<T>* current = head;

    while (current != nullptr) {
        if (current->data == value) {
            if (current->prev != nullptr)
                current->prev->next = current->next;
            else
                head = current->next; // 如果删除的是头结点

            if (current->next != nullptr)
                current->next->prev = current->prev;
            else
                tail = current->prev; // 如果删除的是尾节点

            delete current;
            return true; // 成功移除元素
        }
        current = current->next;
    }

    return false; // 未找到该值，未移除任何元素
}

template <typename T>
void DoublyLinkedList<T>::printList() const {
    Node<T>* current = head;

    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

5. 使用示例

int main() {
    DoublyLinkedList<int> dll;

    // 添加元素到链表尾部
    for (int i = 1; i <= 4; ++i)
        dll.addBack(i);

    // 打印链表
    std::cout << "Initial List: ";
    dll.printList();

    // 在头部添加一个新节点
    dll.addFront(0);
    std::cout << "After adding to front: ";
    dll.printList();

    // 删除元素 2
    if (dll.remove(2))
        std::cout << "Removed element 2" << std::endl;
    else
        std::cout << "Element 2 not found." << std::endl;

    // 再次打印链表
    std::cout << "After removal: ";
    dll.printList();

    return 0;
}

以上就是双向链表的基本操作实现，包括添加、删除和遍历等基本功能。通过上述代码示例，我们能够进一步了解其具体使用方法，并为后续更复杂的操作打下基础。