C++数据结构之双向链表

C++数据结构之双向链表完整攻略

1. 什么是双向链表

双向链表是一种特殊的链表结构，每个节点拥有两个指针域，分别指向前继和后继节点。

双向链表不需要像单向链表那样从头到尾遍历整个链表，可以通过前后指针直接访问前后节点，提高了查找、删除、插入等操作的效率。

双向链表有一些常用的操作，如插入节点、删除节点、查找节点等。

2. 双向链表的实现

2.1 节点定义

template <typename T>
struct DListNode {
    T data;
    DListNode<T> *prev; // 指向前继节点指针
    DListNode<T> *next; // 指向后继节点指针
};

2.2 双向链表类定义

template <typename T>
class DLinkedList {
public:
    DLinkedList() : _head(nullptr), _tail(nullptr), _size(0) {}
    ~DLinkedList() {}

    // 插入操作
    void insertFront(T value);          // 在头部插入节点
    void insertBack(T value);           // 在尾部插入节点
    void insertAt(DListNode<T> *node, T value); // 在指定位置之后插入节点

    // 删除操作
    void deleteFront();  // 删除头部节点
    void deleteBack();   // 删除尾部节点
    void deleteAt(DListNode<T> *node); // 删除单个节点

    // 查找操作
    DListNode<T> *find(T value); // 根据值查找节点
    DListNode<T> *findAt(int index); // 根据下标查找节点

    // 判空操作
    bool empty() { return _head == nullptr; }

    // 返回链表长度
    int size() { return _size; }

    // 输出链表
    void print();

private:
    DListNode<T> *_head; // 头指针
    DListNode<T> *_tail; // 尾指针
    int _size;           // 链表长度
};

2.3 插入节点操作

在头部插入节点，实现如下：

template <typename T>
void DLinkedList<T>::insertFront(T value) {
    DListNode<T> *newNode = new DListNode<T>();
    newNode->data = value;

    if (empty()) {
        _tail = newNode; // 如果链表为空，插入后的节点即为尾节点
    } else {
        _head->prev = newNode;
    }

    newNode->next = _head;
    _head = newNode;
    ++_size;
}

在尾部插入节点，实现如下：

template <typename T>
void DLinkedList<T>::insertBack(T value) {
    DListNode<T> *newNode = new DListNode<T>();
    newNode->data = value;

    if (empty()) {
        _head = newNode; // 如果链表为空，插入后的节点即为头节点
    } else {
        _tail->next = newNode;
    }

    newNode->prev = _tail;
    _tail = newNode;
    ++_size;
}

在指定位置插入节点，实现如下：

template <typename T>
void DLinkedList<T>::insertAt(DListNode<T> *node, T value) {
    DListNode<T> *newNode = new DListNode<T>();
    newNode->data = value;

    newNode->prev = node;
    newNode->next = node->next;
    node->next = newNode;

    if (node == _tail) {
        _tail = newNode;
    } else {
        newNode->next->prev = newNode;
    }

    ++_size;
}

2.4 删除节点操作

删除头部节点，实现如下：

template <typename T>
void DLinkedList<T>::deleteFront() {
    if (empty()) {
        return;
    }

    DListNode<T> *node = _head;

    _head = node->next;
    if (_head != nullptr) {
        _head->prev = nullptr;
    } else {
        _tail = nullptr;
    }

    delete node;
    --_size;
}

删除尾部节点，实现如下：

template <typename T>
void DLinkedList<T>::deleteBack() {
    if (empty()) {
        return;
    }

    DListNode<T> *node = _tail;
    _tail = node->prev;
    if (_tail != nullptr) {
        _tail->next = nullptr;
    } else {
        _head = nullptr;
    }

    delete node;
    --_size;
}

删除任意节点，实现如下：

template <typename T>
void DLinkedList<T>::deleteAt(DListNode<T> *node) {
    if (node == nullptr) {
        return;
    }

    if (node->prev == nullptr) {
        deleteFront();
    } else if (node->next == nullptr) {
        deleteBack();
    } else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
        --_size;
    }
}

2.5 查找节点操作

根据值查找节点，实现如下：

template <typename T>
DListNode<T> *DLinkedList<T>::find(T value) {
    DListNode<T> *node = _head;

    while (node != nullptr) {
        if (node->data == value) {
            return node;
        }
        node = node->next;
    }

    return nullptr;
}

根据下标查找节点，实现如下：

template <typename T>
DListNode<T> *DLinkedList<T>::findAt(int index) {
    if (index >= size()) {
        return nullptr;
    }

    DListNode<T> *node = _head;
    int i = 0;

    while (node != nullptr && i < index) {
        node = node->next;
        ++i;
    }

    return node;
}

2.6 输出链表操作

template <typename T>
void DLinkedList<T>::print() {
    DListNode<T> *node = _head;
    while (node != nullptr) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

3. 示例说明

3.1 实现双向链表并遍历

int main() {
    DLinkedList<int> list;

    // 在头尾插入节点
    list.insertFront(1);
    list.insertBack(2);

    // 在头部插入节点，使链表变为 3 1 2
    DListNode<int> *node = list.find(1);
    list.insertAt(node, 3);

    // 删除尾部节点，使链表变为 3 1
    list.deleteBack();

    // 遍历输出链表
    list.print();

    return 0;
}

输出结果：

3 1

3.2 按下标查找节点并删除

int main() {
    DLinkedList<int> list;

    // 在头尾插入节点
    list.insertFront(1);
    list.insertBack(2);

    // 在头部插入节点，使链表变为 3 1 2
    DListNode<int> *node = list.find(1);
    list.insertAt(node, 3);

    // 删除下标为 1 的节点，即 1，使链表变为 3 2
    node = list.findAt(1);
    list.deleteAt(node);

    // 遍历输出链表
    list.print();

    return 0;
}

输出结果：

3 2