• C++

  • C++双向循环链表：带哨兵节点的实现

  • @ 2025-6-9 22:31:41

C++双向循环链表教程：带哨兵节点的实现

一、什么是哨兵节点？

哨兵节点（Sentinel Node）是一种特殊的节点，它不存储实际数据，仅作为链表的边界标记。在双向循环链表中使用头尾哨兵节点可以简化插入和删除操作，避免处理边界条件。

二、双向循环链表的结构设计

下面是带哨兵节点的双向循环链表的基本结构：

#include <iostream>

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

template<typename T>
class CircularDoublyLinkedList {
private:
    Node<T>* head;  // 头哨兵节点
    Node<T>* tail;  // 尾哨兵节点
    int count;      // 链表中实际元素的数量

public:
    // 构造函数
    CircularDoublyLinkedList();
    
    // 析构函数
    ~CircularDoublyLinkedList();
    
    // 判断链表是否为空
    bool empty() const;
    
    // 返回链表中元素的数量
    int size() const;
    
    // 在链表头部插入元素
    void push_front(const T& value);
    
    // 在链表尾部插入元素
    void push_back(const T& value);
    
    // 删除链表头部元素
    void pop_front();
    
    // 删除链表尾部元素
    void pop_back();
    
    // 获取链表头部元素
    T& front();
    
    // 获取链表尾部元素
    T& back();
    
    // 在指定位置插入元素
    void insert(int index, const T& value);
    
    // 删除指定位置的元素
    void erase(int index);
    
    // 清空链表
    void clear();
    
    // 打印链表中的所有元素
    void print() const;
};

三、哨兵节点的初始化与链表构造

在构造函数中，我们需要初始化头尾哨兵节点并建立循环连接：

template<typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList() {
    // 创建头哨兵节点
    head = new Node<T>();
    
    // 创建尾哨兵节点
    tail = new Node<T>();
    
    // 初始化循环连接
    head->next = tail;
    tail->prev = head;
    
    // 初始元素数量为0
    count = 0;
}

链表初始状态下，头哨兵节点的next指向尾哨兵节点，尾哨兵节点的prev指向头哨兵节点，形成一个空的循环。

四、基本操作实现

下面是链表的一些基本操作的实现：

// 判断链表是否为空
template<typename T>
bool CircularDoublyLinkedList<T>::empty() const {
    return head->next == tail;  // 当且仅当head的next是tail时链表为空
}

// 返回链表中元素的数量
template<typename T>
int CircularDoublyLinkedList<T>::size() const {
    return count;
}

// 在链表头部插入元素
template<typename T>
void CircularDoublyLinkedList<T>::push_front(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    
    // 连接新节点和头哨兵节点之后的节点
    newNode->next = head->next;
    newNode->prev = head;
    
    // 更新头哨兵节点和原第一个节点
    head->next->prev = newNode;
    head->next = newNode;
    
    // 增加元素计数
    count++;
}

// 在链表尾部插入元素
template<typename T>
void CircularDoublyLinkedList<T>::push_back(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    
    // 连接新节点和尾哨兵节点之前的节点
    newNode->prev = tail->prev;
    newNode->next = tail;
    
    // 更新尾哨兵节点和原最后一个节点
    tail->prev->next = newNode;
    tail->prev = newNode;
    
    // 增加元素计数
    count++;
}

五、删除操作实现

删除操作同样需要注意维护循环结构：

// 删除链表头部元素
template<typename T>
void CircularDoublyLinkedList<T>::pop_front() {
    if (empty()) return;  // 链表为空时不执行操作
    
    Node<T>* toDelete = head->next;  // 要删除的节点
    
    // 更新指针，跳过要删除的节点
    head->next = toDelete->next;
    toDelete->next->prev = head;
    
    // 删除节点并减少计数
    delete toDelete;
    count--;
}

// 删除链表尾部元素
template<typename T>
void CircularDoublyLinkedList<T>::pop_back() {
    if (empty()) return;  // 链表为空时不执行操作
    
    Node<T>* toDelete = tail->prev;  // 要删除的节点
    
    // 更新指针，跳过要删除的节点
    tail->prev = toDelete->prev;
    toDelete->prev->next = tail;
    
    // 删除节点并减少计数
    delete toDelete;
    count--;
}

六、访问操作实现

通过头尾哨兵节点，我们可以方便地访问链表的首尾元素：

// 获取链表头部元素
template<typename T>
T& CircularDoublyLinkedList<T>::front() {
    if (empty()) throw std::out_of_range("List is empty");
    return head->next->data;  // 返回头哨兵节点之后的节点数据
}

// 获取链表尾部元素
template<typename T>
T& CircularDoublyLinkedList<T>::back() {
    if (empty()) throw std::out_of_range("List is empty");
    return tail->prev->data;  // 返回尾哨兵节点之前的节点数据
}

七、任意位置操作实现

在指定位置插入和删除元素：

// 在指定位置插入元素
template<typename T>
void CircularDoublyLinkedList<T>::insert(int index, const T& value) {
    if (index < 0 || index > count) throw std::out_of_range("Index out of range");
    
    Node<T>* current = head;
    
    // 移动到插入位置的前一个节点
    for (int i = 0; i < index; i++) {
        current = current->next;
    }
    
    // 创建新节点并插入
    Node<T>* newNode = new Node<T>(value);
    newNode->next = current->next;
    newNode->prev = current;
    current->next->prev = newNode;
    current->next = newNode;
    
    // 增加计数
    count++;
}

// 删除指定位置的元素
template<typename T>
void CircularDoublyLinkedList<T>::erase(int index) {
    if (index < 0 || index >= count) throw std::out_of_range("Index out of range");
    
    Node<T>* current = head->next;
    
    // 移动到要删除的节点
    for (int i = 0; i < index; i++) {
        current = current->next;
    }
    
    // 更新指针，跳过要删除的节点
    current->prev->next = current->next;
    current->next->prev = current->prev;
    
    // 删除节点并减少计数
    delete current;
    count--;
}

八、清理和打印操作

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

// 打印链表中的所有元素
template<typename T>
void CircularDoublyLinkedList<T>::print() const {
    Node<T>* current = head->next;
    
    while (current != tail) {
        std::cout << current->data << " ";
        current = current->next;
    }
    
    std::cout << std::endl;
}

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

九、使用示例

下面是一个使用这个双向循环链表的简单示例：

int main() {
    CircularDoublyLinkedList<int> list;
    
    // 在尾部插入元素
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    
    // 打印链表
    std::cout << "链表内容: ";
    list.print();  // 输出: 10 20 30
    
    // 在头部插入元素
    list.push_front(5);
    
    // 打印链表
    std::cout << "插入头部元素后的链表: ";
    list.print();  // 输出: 5 10 20 30
    
    // 删除尾部元素
    list.pop_back();
    
    // 打印链表
    std::cout << "删除尾部元素后的链表: ";
    list.print();  // 输出: 5 10 20
    
    // 在位置1插入元素
    list.insert(1, 15);
    
    // 打印链表
    std::cout << "在位置1插入元素后的链表: ";
    list.print();  // 输出: 5 15 10 20
    
    // 删除位置2的元素
    list.erase(2);
    
    // 打印链表
    std::cout << "删除位置2元素后的链表: ";
    list.print();  // 输出: 5 15 20
    
    return 0;
}

十、哨兵节点的优势

使用哨兵节点的主要优势：

  1. 简化边界条件：不需要特殊处理空链表或头尾节点的插入删除
  2. 代码简洁：减少了条件判断，使代码更易读和维护
  3. 避免空指针：永远不会有空指针引用，所有节点都有前驱和后继

这种结构在实现高级数据结构（如STL的list）时非常有用，能够提高代码的健壮性和性能。

3 条评论

  • @ 2025-6-9 22:50:24 
    #include <iostream>

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

template<typename T>
class CircularDoublyLinkedList {
private:
	Node<T>* head;  // 头哨兵节点
	Node<T>* tail;  // 尾哨兵节点
	int count;      // 链表中实际元素的数量
	
public:
	// 构造函数
	CircularDoublyLinkedList();
	
	// 析构函数
	~CircularDoublyLinkedList();
	
	// 判断链表是否为空
	bool empty() const;
	
	// 返回链表中元素的数量
	int size() const;
	
	// 在链表头部插入元素
	void push_front(const T& value);
	
	// 在链表尾部插入元素
	void push_back(const T& value);
	
	// 删除链表头部元素
	void pop_front();
	
	// 删除链表尾部元素
	void pop_back();
	
	// 获取链表头部元素
	T& front();
	
	// 获取链表尾部元素
	T& back();
	
	// 在指定位置插入元素
	void insert(int index, const T& value);
	
	// 删除指定位置的元素
	void erase(int index);
	
	// 清空链表
	void clear();
	
	// 打印链表中的所有元素
	void print() const;
};
template<typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList() {
	// 创建头哨兵节点
	head = new Node<T>();
	
	// 创建尾哨兵节点
	tail = new Node<T>();
	
	// 初始化循环连接
	head->next = tail;
	tail->prev = head;
	
	// 初始元素数量为0
	count = 0;
}
// 判断链表是否为空
template<typename T>
bool CircularDoublyLinkedList<T>::empty() const {
	return head->next == tail;  // 当且仅当head的next是tail时链表为空
}

// 返回链表中元素的数量
template<typename T>
int CircularDoublyLinkedList<T>::size() const {
	return count;
}

// 在链表头部插入元素
template<typename T>
void CircularDoublyLinkedList<T>::push_front(const T& value) {
	Node<T>* newNode = new Node<T>(value);
	
	// 连接新节点和头哨兵节点之后的节点
	newNode->next = head->next;
	newNode->prev = head;
	
	// 更新头哨兵节点和原第一个节点
	head->next->prev = newNode;
	head->next = newNode;
	
	// 增加元素计数
	count++;
}

// 在链表尾部插入元素
template<typename T>
void CircularDoublyLinkedList<T>::push_back(const T& value) {
	Node<T>* newNode = new Node<T>(value);
	
	// 连接新节点和尾哨兵节点之前的节点
	newNode->prev = tail->prev;
	newNode->next = tail;
	
	// 更新尾哨兵节点和原最后一个节点
	tail->prev->next = newNode;
	tail->prev = newNode;
	
	// 增加元素计数
	count++;
}
// 删除链表头部元素
template<typename T>
void CircularDoublyLinkedList<T>::pop_front() {
	if (empty()) return;  // 链表为空时不执行操作
	
	Node<T>* toDelete = head->next;  // 要删除的节点
	
	// 更新指针，跳过要删除的节点
	head->next = toDelete->next;
	toDelete->next->prev = head;
	
	// 删除节点并减少计数
	delete toDelete;
	count--;
}

// 删除链表尾部元素
template<typename T>
void CircularDoublyLinkedList<T>::pop_back() {
	if (empty()) return;  // 链表为空时不执行操作
	
	Node<T>* toDelete = tail->prev;  // 要删除的节点
	
	// 更新指针，跳过要删除的节点
	tail->prev = toDelete->prev;
	toDelete->prev->next = tail;
	
	// 删除节点并减少计数
	delete toDelete;
	count--;
}
// 获取链表头部元素
template<typename T>
T& CircularDoublyLinkedList<T>::front() {
	if (empty()) throw std::out_of_range("List is empty");
	return head->next->data;  // 返回头哨兵节点之后的节点数据
}

// 获取链表尾部元素
template<typename T>
T& CircularDoublyLinkedList<T>::back() {
	if (empty()) throw std::out_of_range("List is empty");
	return tail->prev->data;  // 返回尾哨兵节点之前的节点数据
}
// 在指定位置插入元素
template<typename T>
void CircularDoublyLinkedList<T>::insert(int index, const T& value) {
	if (index < 0 || index > count) throw std::out_of_range("Index out of range");
	
	Node<T>* current = head;
	
	// 移动到插入位置的前一个节点
	for (int i = 0; i < index; i++) {
		current = current->next;
	}
	
	// 创建新节点并插入
	Node<T>* newNode = new Node<T>(value);
	newNode->next = current->next;
	newNode->prev = current;
	current->next->prev = newNode;
	current->next = newNode;
	
	// 增加计数
	count++;
}

// 删除指定位置的元素
template<typename T>
void CircularDoublyLinkedList<T>::erase(int index) {
	if (index < 0 || index >= count) throw std::out_of_range("Index out of range");
	
	Node<T>* current = head->next;
	
	// 移动到要删除的节点
	for (int i = 0; i < index; i++) {
		current = current->next;
	}
	
	// 更新指针，跳过要删除的节点
	current->prev->next = current->next;
	current->next->prev = current->prev;
	
	// 删除节点并减少计数
	delete current;
	count--;
}
// 清空链表
template<typename T>
void CircularDoublyLinkedList<T>::clear() {
	while (!empty()) {
		pop_front();
	}
}

// 打印链表中的所有元素
template<typename T>
void CircularDoublyLinkedList<T>::print() const {
	Node<T>* current = head->next;
	
	while (current != tail) {
		std::cout << current->data << " ";
		current = current->next;
	}
	
	std::cout << std::endl;
}

// 析构函数
template<typename T>
CircularDoublyLinkedList<T>::~CircularDoublyLinkedList() {
	clear();
	delete head;
	delete tail;
}
int main() {
	CircularDoublyLinkedList<int> list;
	
	// 在尾部插入元素
	list.push_back(10);
	list.push_back(20);
	list.push_back(30);
	
	// 打印链表
	std::cout << "链表内容: ";
	list.print();  // 输出: 10 20 30
	
	// 在头部插入元素
	list.push_front(5);
	
	// 打印链表
	std::cout << "插入头部元素后的链表: ";
	list.print();  // 输出: 5 10 20 30
	
	// 删除尾部元素
	list.pop_back();
	
	// 打印链表
	std::cout << "删除尾部元素后的链表: ";
	list.print();  // 输出: 5 10 20
	
	// 在位置1插入元素
	list.insert(1, 15);
	
	// 打印链表
	std::cout << "在位置1插入元素后的链表: ";
	list.print();  // 输出: 5 15 10 20
	
	// 删除位置2的元素
	list.erase(2);
	
	// 打印链表
	std::cout << "删除位置2元素后的链表: ";
	list.print();  // 输出: 5 15 20
	
	return 0;
}
    • @ 2025-6-9 22:36:06

      C++ 双向循环链表（包含头尾哨兵节点）教程

      简介

      双向循环链表是一种特殊的链表结构，它的每个节点都有两个指针：

      • prev 指向前一个节点
      • next 指向后一个节点

      在这个实现中，我们会使用头尾哨兵节点（Sentinel Nodes），它们是不存储实际数据的特殊节点：

      • 头哨兵节点始终位于链表的最前面
      • 尾哨兵节点始终位于链表的最后面

      这种设计可以简化边界条件的处理，让代码更加简洁。

      节点类定义

      template<typename T>
class Node {
public:
    T data;        // 存储的数据
    Node* prev;    // 指向前一个节点
    Node* next;    // 指向后一个节点

    // 构造函数
    Node(const T& data = T(), Node* prev = nullptr, Node* next = nullptr)
        : data(data), prev(prev), next(next) {}
};

      链表类定义

      template<typename T>
class DoublyCircularLinkedList {
private:
    Node<T>* head;  // 头哨兵节点
    Node<T>* tail;  // 尾哨兵节点
    int size;       // 链表的实际元素个数（不含哨兵）

public:
    // 构造函数 - 初始化空链表（只有哨兵节点）
    DoublyCircularLinkedList() {
        // 创建头尾哨兵节点
        head = new Node<T>();  // 不存储实际数据
        tail = new Node<T>();  // 不存储实际数据

        // 初始时，头尾哨兵节点互相指向对方
        head->next = tail;
        head->prev = tail;
        tail->prev = head;
        tail->next = head;

        size = 0;
    }

    // 析构函数 - 释放所有节点内存
    ~DoublyCircularLinkedList() {
        clear();      // 清空链表
        delete head;  // 删除头哨兵
        delete tail;  // 删除尾哨兵
    }

    // 在指定位置插入新节点
    bool insert(int index, const T& data) {
        if (index < 0 || index > size) {
            return false; // 插入位置非法
        }

        Node<T>* newNode = new Node<T>(data);
        
        // 找到插入位置前后的节点
        Node<T>* current = head->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }

        // 插入新节点
        newNode->prev = current->prev;
        newNode->next = current;
        current->prev->next = newNode;
        current->prev = newNode;

        ++size;
        return true;
    }

    // 在头部添加元素
    void push_front(const T& data) {
        insert(0, data);
    }

    // 在尾部添加元素
    void push_back(const T& data) {
        insert(size, data);
    }

    // 删除指定位置的节点
    bool remove(int index) {
        if (index < 0 || index >= size) {
            return false; // 删除位置非法
        }

        // 找到要删除的节点
        Node<T>* current = head->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }

        // 修改前后节点的指针
        current->prev->next = current->next;
        current->next->prev = current->prev;

        // 释放内存
        delete current;
        --size;
        return true;
    }

    // 删除头部元素
    void pop_front() {
        if (!empty()) {
            remove(0);
        }
    }

    // 删除尾部元素
    void pop_back() {
        if (!empty()) {
            remove(size - 1);
        }
    }

    // 获取指定位置的元素
    bool get(int index, T& data) const {
        if (index < 0 || index >= size) {
            return false; // 位置非法
        }

        // 找到对应节点
        Node<T>* current = head->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }

        data = current->data;
        return true;
    }

    // 查找元素的位置
    int find(const T& data) const {
        Node<T>* current = head->next;
        int index = 0;

        while (current != tail) {
            if (current->data == data) {
                return index;
            }
            current = current->next;
            ++index;
        }

        return -1; // 未找到
    }

    // 修改指定位置的元素值
    bool set(int index, const T& data) {
        if (index < 0 || index >= size) {
            return false; // 位置非法
        }

        // 找到对应节点
        Node<T>* current = head->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }

        current->data = data;
        return true;
    }

    // 判断链表是否为空
    bool empty() const {
        return size == 0;
    }

    // 获取链表长度
    int getSize() const {
        return size;
    }

    // 清空链表
    void clear() {
        Node<T>* current = head->next;
        // 释放所有实际数据节点
        while (current != tail) {
            Node<T>* next = current->next;
            delete current;
            current = next;
        }

        // 重置哨兵节点
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    // 打印链表内容
    void print() const {
        std::cout << "链表内容: ";
        Node<T>* current = head->next;
        while (current != tail) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // 从尾部打印链表内容
    void printReverse() const {
        std::cout << "逆序链表内容: ";
        Node<T>* current = tail->prev;
        while (current != head) {
            std::cout << current->data << " ";
            current = current->prev;
        }
        std::cout << std::endl;
    }
};

      使用示例

      #include <iostream>
using namespace std;

// 上面的Node和DoublyCircularLinkedList类定义放在这里

int main() {
    DoublyCircularLinkedList<int> list;

    // 添加元素
    list.push_back(10);
    list.push_back(20);
    list.push_front(5);
    list.insert(2, 15);  // 在索引2处插入15

    // 打印链表
    list.print();        // 输出: 5 10 15 20
    list.printReverse(); // 输出: 20 15 10 5

    int value;
    if (list.get(2, value)) {
        cout << "索引2处的值为: " << value << endl;  // 输出: 15
    }

    // 修改元素
    list.set(1, 25);

    // 删除元素
    list.pop_back();     // 删除尾部元素
    list.pop_front();    // 删除头部元素
    list.remove(1);      // 删除索引1处的元素

    // 清空链表
    list.clear();

    return 0;
}

      总结

      这个双向循环链表的主要特点包括：

      1. 头尾哨兵节点：简化了边界条件的处理
      2. 双向性：可以通过prev和next在两个方向上遍历
      3. 循环性：尾节点的next指向头节点，头节点的prev指向尾节点
      4. 常用操作：实现了插入、删除、查找、修改等基本功能

      使用头尾哨兵节点的设计可以让代码更清晰、减少边界条件判断，并且更容易实现循环特性。

      • @ 2025-6-9 22:32:59

        下面是完整的带哨兵节点的双向循环链表实现程序，包含详细注释和使用示例：

        #include <iostream>
#include <stdexcept>

// 链表节点结构
template<typename T>
struct Node {
    T data;         // 数据域
    Node* prev;     // 指向前驱节点的指针
    Node* next;     // 指向后继节点的指针
    
    // 构造函数
    Node(const T& value = T()) : data(value), prev(nullptr), next(nullptr) {}
};

// 双向循环链表类
template<typename T>
class CircularDoublyLinkedList {
private:
    Node<T>* head;  // 头哨兵节点
    Node<T>* tail;  // 尾哨兵节点
    int count;      // 链表中实际元素的数量

public:
    // 构造函数
    CircularDoublyLinkedList() {
        // 创建头哨兵节点
        head = new Node<T>();
        
        // 创建尾哨兵节点
        tail = new Node<T>();
        
        // 初始化循环连接
        head->next = tail;
        tail->prev = head;
        
        // 初始元素数量为0
        count = 0;
    }
    
    // 析构函数
    ~CircularDoublyLinkedList() {
        clear();
        delete head;
        delete tail;
    }
    
    // 判断链表是否为空
    bool empty() const {
        return head->next == tail;  // 当且仅当head的next是tail时链表为空
    }
    
    // 返回链表中元素的数量
    int size() const {
        return count;
    }
    
    // 在链表头部插入元素
    void push_front(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        
        // 连接新节点和头哨兵节点之后的节点
        newNode->next = head->next;
        newNode->prev = head;
        
        // 更新头哨兵节点和原第一个节点
        head->next->prev = newNode;
        head->next = newNode;
        
        // 增加元素计数
        count++;
    }
    
    // 在链表尾部插入元素
    void push_back(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        
        // 连接新节点和尾哨兵节点之前的节点
        newNode->prev = tail->prev;
        newNode->next = tail;
        
        // 更新尾哨兵节点和原最后一个节点
        tail->prev->next = newNode;
        tail->prev = newNode;
        
        // 增加元素计数
        count++;
    }
    
    // 删除链表头部元素
    void pop_front() {
        if (empty()) return;  // 链表为空时不执行操作
        
        Node<T>* toDelete = head->next;  // 要删除的节点
        
        // 更新指针，跳过要删除的节点
        head->next = toDelete->next;
        toDelete->next->prev = head;
        
        // 删除节点并减少计数
        delete toDelete;
        count--;
    }
    
    // 删除链表尾部元素
    void pop_back() {
        if (empty()) return;  // 链表为空时不执行操作
        
        Node<T>* toDelete = tail->prev;  // 要删除的节点
        
        // 更新指针，跳过要删除的节点
        tail->prev = toDelete->prev;
        toDelete->prev->next = tail;
        
        // 删除节点并减少计数
        delete toDelete;
        count--;
    }
    
    // 获取链表头部元素
    T& front() {
        if (empty()) throw std::out_of_range("List is empty");
        return head->next->data;  // 返回头哨兵节点之后的节点数据
    }
    
    // 获取链表尾部元素
    T& back() {
        if (empty()) throw std::out_of_range("List is empty");
        return tail->prev->data;  // 返回尾哨兵节点之前的节点数据
    }
    
    // 在指定位置插入元素
    void insert(int index, const T& value) {
        if (index < 0 || index > count) throw std::out_of_range("Index out of range");
        
        Node<T>* current = head;
        
        // 移动到插入位置的前一个节点
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        
        // 创建新节点并插入
        Node<T>* newNode = new Node<T>(value);
        newNode->next = current->next;
        newNode->prev = current;
        current->next->prev = newNode;
        current->next = newNode;
        
        // 增加计数
        count++;
    }
    
    // 删除指定位置的元素
    void erase(int index) {
        if (index < 0 || index >= count) throw std::out_of_range("Index out of range");
        
        Node<T>* current = head->next;
        
        // 移动到要删除的节点
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        
        // 更新指针，跳过要删除的节点
        current->prev->next = current->next;
        current->next->prev = current->prev;
        
        // 删除节点并减少计数
        delete current;
        count--;
    }
    
    // 清空链表
    void clear() {
        while (!empty()) {
            pop_front();
        }
    }
    
    // 打印链表中的所有元素
    void print() const {
        Node<T>* current = head->next;
        
        while (current != tail) {
            std::cout << current->data << " ";
            current = current->next;
        }
        
        std::cout << std::endl;
    }
};

// 使用示例
int main() {
    CircularDoublyLinkedList<int> list;
    
    // 在尾部插入元素
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    
    // 打印链表
    std::cout << "链表内容: ";
    list.print();  // 输出: 10 20 30
    
    // 在头部插入元素
    list.push_front(5);
    
    // 打印链表
    std::cout << "插入头部元素后的链表: ";
    list.print();  // 输出: 5 10 20 30
    
    // 删除尾部元素
    list.pop_back();
    
    // 打印链表
    std::cout << "删除尾部元素后的链表: ";
    list.print();  // 输出: 5 10 20
    
    // 在位置1插入元素
    list.insert(1, 15);
    
    // 打印链表
    std::cout << "在位置1插入元素后的链表: ";
    list.print();  // 输出: 5 15 10 20
    
    // 删除位置2的元素
    list.erase(2);
    
    // 打印链表
    std::cout << "删除位置2元素后的链表: ";
    list.print();  // 输出: 5 15 20
    
    return 0;
}

        这个程序实现了一个完整的带哨兵节点的双向循环链表，包括以下功能：

        1. 链表的创建和销毁
        2. 元素的插入（头部、尾部、任意位置）
        3. 元素的删除（头部、尾部、任意位置）
        4. 元素的访问（头部、尾部）
        5. 链表状态检查（是否为空、大小）
        6. 链表内容的打印

        你可以直接编译运行这个程序，也可以根据需要扩展更多功能，如迭代器支持、反转链表、查找元素等操作。

        • 1
        436
        已通过
        0
        题解被赞
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        4. 在线咨询
        5. Worker 0, 21ms
        6. Powered by Hydro v4.13.3 Community