C++
C++ 循环双链表学习笔记教程
admin SU @ 2025-8-10 14:09:02

C++ 循环双链表学习笔记教程

1. 循环双链表的概念

循环双链表是一种特殊的链表结构，它具有以下特点：

每个节点包含数据域和两个指针域（前驱指针和后继指针）
尾节点的后继指针指向头节点
头节点的前驱指针指向尾节点
可以从任意节点出发遍历整个链表
支持双向遍历

2. 节点结构设计

循环双链表的节点需要包含三个部分：

数据域：存储节点数据
前驱指针：指向当前节点的前一个节点
后继指针：指向当前节点的后一个节点

template <typename T>
struct Node {
    T data;          // 数据域
    Node* prev;      // 前驱指针
    Node* next;      // 后继指针
    
    // 构造函数
    Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

3. 循环双链表类的设计

我们设计一个CircularDoublyLinkedList类来封装循环双链表的操作：

#include <iostream>
using namespace std;

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

template <typename T>
class CircularDoublyLinkedList {
private:
    Node<T>* head;  // 头指针
    int size;       // 链表长度
    
public:
    // 构造函数
    CircularDoublyLinkedList();
    
    // 析构函数
    ~CircularDoublyLinkedList();
    
    // 拷贝构造函数
    CircularDoublyLinkedList(const CircularDoublyLinkedList& other);
    
    // 赋值运算符重载
    CircularDoublyLinkedList& operator=(const CircularDoublyLinkedList& other);
    
    // 判断链表是否为空
    bool isEmpty() const;
    
    // 获取链表长度
    int getSize() const;
    
    // 在链表头部插入元素
    void insertAtHead(const T& val);
    
    // 在链表尾部插入元素
    void insertAtTail(const T& val);
    
    // 在指定位置插入元素
    bool insertAtPosition(int pos, const T& val);
    
    // 删除头节点
    bool deleteAtHead();
    
    // 删除尾节点
    bool deleteAtTail();
    
    // 删除指定位置的节点
    bool deleteAtPosition(int pos);
    
    // 查找元素
    int find(const T& val) const;
    
    // 获取指定位置的元素
    T get(int pos) const;
    
    // 修改指定位置的元素
    bool set(int pos, const T& val);
    
    // 遍历链表（正向）
    void traverseForward() const;
    
    // 遍历链表（反向）
    void traverseBackward() const;
    
    // 清空链表
    void clear();
    
private:
    // 辅助函数：获取指定位置的节点
    Node<T>* getNodeAt(int pos) const;
    
    // 辅助函数：复制链表
    void copyFrom(const CircularDoublyLinkedList& other);
};

4. 成员函数实现

下面实现循环双链表类的核心成员函数：

#include "circular_doubly_linked_list.h"

// 构造函数
template <typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList() : head(nullptr), size(0) {}

// 析构函数
template <typename T>
CircularDoublyLinkedList<T>::~CircularDoublyLinkedList() {
    clear();
}

// 拷贝构造函数
template <typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList(const CircularDoublyLinkedList& other) {
    copyFrom(other);
}

// 赋值运算符重载
template <typename T>
CircularDoublyLinkedList<T>& CircularDoublyLinkedList<T>::operator=(const CircularDoublyLinkedList& other) {
    if (this != &other) {
        clear();
        copyFrom(other);
    }
    return *this;
}

// 判断链表是否为空
template <typename T>
bool CircularDoublyLinkedList<T>::isEmpty() const {
    return size == 0;
}

// 获取链表长度
template <typename T>
int CircularDoublyLinkedList<T>::getSize() const {
    return size;
}

// 在链表头部插入元素
template <typename T>
void CircularDoublyLinkedList<T>::insertAtHead(const T& val) {
    Node<T>* newNode = new Node<T>(val);
    
    if (isEmpty()) {
        head = newNode;
        head->prev = head;
        head->next = head;
    } else {
        newNode->next = head;
        newNode->prev = head->prev;
        head->prev->next = newNode;
        head->prev = newNode;
        head = newNode;
    }
    size++;
}

// 在链表尾部插入元素
template <typename T>
void CircularDoublyLinkedList<T>::insertAtTail(const T& val) {
    if (isEmpty()) {
        insertAtHead(val);
        return;
    }
    
    Node<T>* newNode = new Node<T>(val);
    Node<T>* last = head->prev;
    
    newNode->next = head;
    newNode->prev = last;
    last->next = newNode;
    head->prev = newNode;
    
    size++;
}

// 获取指定位置的节点
template <typename T>
Node<T>* CircularDoublyLinkedList<T>::getNodeAt(int pos) const {
    if (isEmpty() || pos < 0 || pos >= size) {
        return nullptr;
    }
    
    Node<T>* current = head;
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    return current;
}

// 在指定位置插入元素
template <typename T>
bool CircularDoublyLinkedList<T>::insertAtPosition(int pos, const T& val) {
    if (pos < 0 || pos > size) {
        return false;
    }
    
    if (pos == 0) {
        insertAtHead(val);
        return true;
    }
    
    if (pos == size) {
        insertAtTail(val);
        return true;
    }
    
    Node<T>* prevNode = getNodeAt(pos - 1);
    Node<T>* newNode = new Node<T>(val);
    
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    prevNode->next->prev = newNode;
    prevNode->next = newNode;
    
    size++;
    return true;
}

// 删除头节点
template <typename T>
bool CircularDoublyLinkedList<T>::deleteAtHead() {
    if (isEmpty()) {
        return false;
    }
    
    Node<T>* temp = head;
    
    if (size == 1) {
        head = nullptr;
    } else {
        head->prev->next = head->next;
        head->next->prev = head->prev;
        head = head->next;
    }
    
    delete temp;
    size--;
    return true;
}

// 删除尾节点
template <typename T>
bool CircularDoublyLinkedList<T>::deleteAtTail() {
    if (isEmpty()) {
        return false;
    }
    
    if (size == 1) {
        return deleteAtHead();
    }
    
    Node<T>* last = head->prev;
    last->prev->next = head;
    head->prev = last->prev;
    
    delete last;
    size--;
    return true;
}

// 删除指定位置的节点
template <typename T>
bool CircularDoublyLinkedList<T>::deleteAtPosition(int pos) {
    if (isEmpty() || pos < 0 || pos >= size) {
        return false;
    }
    
    if (pos == 0) {
        return deleteAtHead();
    }
    
    if (pos == size - 1) {
        return deleteAtTail();
    }
    
    Node<T>* toDelete = getNodeAt(pos);
    toDelete->prev->next = toDelete->next;
    toDelete->next->prev = toDelete->prev;
    
    delete toDelete;
    size--;
    return true;
}

// 查找元素
template <typename T>
int CircularDoublyLinkedList<T>::find(const T& val) const {
    if (isEmpty()) {
        return -1;
    }
    
    Node<T>* current = head;
    for (int i = 0; i < size; i++) {
        if (current->data == val) {
            return i;
        }
        current = current->next;
    }
    return -1;
}

// 获取指定位置的元素
template <typename T>
T CircularDoublyLinkedList<T>::get(int pos) const {
    Node<T>* node = getNodeAt(pos);
    if (node) {
        return node->data;
    }
    // 实际应用中应该抛出异常或使用其他错误处理机制
    throw out_of_range("Position out of range");
}

// 修改指定位置的元素
template <typename T>
bool CircularDoublyLinkedList<T>::set(int pos, const T& val) {
    Node<T>* node = getNodeAt(pos);
    if (node) {
        node->data = val;
        return true;
    }
    return false;
}

// 正向遍历链表
template <typename T>
void CircularDoublyLinkedList<T>::traverseForward() const {
    if (isEmpty()) {
        cout << "List is empty" << endl;
        return;
    }
    
    Node<T>* current = head;
    for (int i = 0; i < size; i++) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

// 反向遍历链表
template <typename T>
void CircularDoublyLinkedList<T>::traverseBackward() const {
    if (isEmpty()) {
        cout << "List is empty" << endl;
        return;
    }
    
    Node<T>* current = head->prev;  // 从尾节点开始
    for (int i = 0; i < size; i++) {
        cout << current->data << " ";
        current = current->prev;
    }
    cout << endl;
}

// 清空链表
template <typename T>
void CircularDoublyLinkedList<T>::clear() {
    while (!isEmpty()) {
        deleteAtHead();
    }
}

// 复制链表
template <typename T>
void CircularDoublyLinkedList<T>::copyFrom(const CircularDoublyLinkedList& other) {
    head = nullptr;
    size = 0;
    
    Node<T>* current = other.head;
    for (int i = 0; i < other.size; i++) {
        insertAtTail(current->data);
        current = current->next;
    }
}

// 实例化常用类型，避免链接错误
template class CircularDoublyLinkedList<int>;
template class CircularDoublyLinkedList<double>;
template class CircularDoublyLinkedList<string>;

5. 使用示例

下面是一个使用循环双链表的示例程序：

#include "circular_doubly_linked_list.h"

int main() {
    // 创建一个循环双链表
    CircularDoublyLinkedList<int> list;
    
    // 插入元素
    list.insertAtHead(10);
    list.insertAtTail(20);
    list.insertAtPosition(1, 15);
    list.insertAtTail(25);
    
    cout << "链表长度: " << list.getSize() << endl;
    cout << "正向遍历: ";
    list.traverseForward();  // 输出: 10 15 20 25
    
    cout << "反向遍历: ";
    list.traverseBackward();  // 输出: 25 20 15 10
    
    // 查找元素
    int pos = list.find(20);
    if (pos != -1) {
        cout << "元素 20 位于位置: " << pos << endl;  // 输出: 2
    }
    
    // 修改元素
    list.set(2, 200);
    cout << "修改后正向遍历: ";
    list.traverseForward();  // 输出: 10 15 200 25
    
    // 删除元素
    list.deleteAtPosition(1);
    cout << "删除位置1的元素后: ";
    list.traverseForward();  // 输出: 10 200 25
    
    list.deleteAtHead();
    cout << "删除头元素后: ";
    list.traverseForward();  // 输出: 200 25
    
    list.deleteAtTail();
    cout << "删除尾元素后: ";
    list.traverseForward();  // 输出: 200
    
    // 清空链表
    list.clear();
    cout << "清空后链表是否为空: " << (list.isEmpty() ? "是" : "否") << endl;  // 输出: 是
    
    return 0;
}

6. 循环双链表的优缺点

优点

可以从任意节点开始遍历整个链表
支持双向遍历，操作灵活
头节点和尾节点的插入删除操作效率高（O(1)）
不需要判断是否为NULL指针，简化了边界条件处理

缺点

比单链表占用更多的内存空间（需要存储两个指针）
插入和删除操作比单链表更复杂，需要同时维护两个指针
不支持随机访问，访问指定位置元素需要O(n)时间

7. 应用场景

循环双链表适用于以下场景：

需要频繁进行首尾元素操作的场景
需要双向遍历的场景
实现循环队列、循环缓冲区等数据结构
操作系统中的进程调度链表
音乐播放器的播放列表（可以循环播放，向前/向后切换）

通过本教程，你应该已经掌握了C++中循环双链表的基本概念、实现方法和使用技巧。循环双链表是一种非常灵活的数据结构，掌握它对于理解更复杂的数据结构和算法有很大帮助。

目前还没有评论...

C++ 循环双链表学习笔记教程

C++ 循环双链表学习笔记教程

1. 循环双链表的概念

2. 节点结构设计

3. 循环双链表类的设计

4. 成员函数实现

5. 使用示例

6. 循环双链表的优缺点

优点

缺点

7. 应用场景

0 条评论

状态

开发

支持

C++ 循环双链表学习笔记教程

C++ 循环双链表学习笔记教程

1. 循环双链表的概念

2. 节点结构设计

3. 循环双链表类的设计

4. 成员函数实现

5. 使用示例

6. 循环双链表的优缺点

优点

缺点

7. 应用场景

0 条评论

状态

开发

支持

还没有账户？

登录