带头结点的双向循环链表操作集
时间: 2024-03-25 14:14:47 浏览: 24
双向循环链表是一种特殊的链表,它的最后一个节点的 next 指针指向第一个节点,第一个节点的 prev 指针指向最后一个节点,因此可以实现循环遍历。带头结点的双向循环链表是在双向循环链表的基础上增加了一个头结点,可以方便地进行插入、删除等操作。以下是带头结点的双向循环链表的常见操作:
```c++
// 双向循环链表节点结构体
template <typename T>
struct Node {
T data;
Node<T>* prev;
Node<T>* next;
Node() : data(T()), prev(nullptr), next(nullptr) {}
Node(T _data, Node<T>* _prev = nullptr, Node<T>* _next = nullptr) : data(_data), prev(_prev), next(_next) {}
};
// 带头结点的双向循环链表类
template <typename T>
class DoubleLinkedList {
public:
DoubleLinkedList() : head(new Node<T>()), size(0) {
head->prev = head->next = head;
}
~DoubleLinkedList() {
clear();
delete head;
}
// 在 index 处插入元素
void insert(int index, const T& value) {
if (index < 0 || index > size) {
throw std::out_of_range("Index out of range.");
}
Node<T>* cur = head;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
Node<T>* node = new Node<T>(value, cur, cur->next);
cur->next->prev = node;
cur->next = node;
++size;
}
// 删除 index 处的元素
void remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range.");
}
Node<T>* cur = head->next;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
delete cur;
--size;
}
// 清空链表
void clear() {
while (size > 0) {
remove(0);
}
}
// 获取第 index 个元素
T& get(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range.");
}
Node<T>* cur = head->next;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->data;
}
// 获取链表长度
int getSize() const {
return size;
}
// 判断链表是否为空
bool isEmpty() const {
return size == 0;
}
private:
Node<T>* head; // 头结点
int size; // 链表长度
};
```
以上是带头结点的双向循环链表的常见操作,可以根据实际需求进行调整和扩展。