循环列表双向列表C++
时间: 2024-01-11 10:18:46 浏览: 17
循环双向链表是一种特殊的链表,它的最后一个节点指向第一个节点,同时每个节点还有一个指向前一个节点的指针。这种链表可以用于实现循环队列等数据结构。
下面是一个简单的循环双向链表的实现:
```c++
struct Node {
int val;
Node* prev;
Node* next;
Node(int v): val(v), prev(nullptr), next(nullptr) {}
};
class CircularDoublyLinkedList {
public:
CircularDoublyLinkedList(): head(nullptr), tail(nullptr) {}
void insert(int val) {
Node* node = new Node(val);
if (!head) {
head = tail = node;
head->prev = tail;
tail->next = head;
} else {
tail->next = node;
node->prev = tail;
tail = node;
tail->next = head;
head->prev = tail;
}
}
void remove(int val) {
if (!head) return;
Node* cur = head;
while (cur->val != val && cur != tail) {
cur = cur->next;
}
if (cur->val == val) {
if (cur == head) {
head = head->next;
head->prev = tail;
tail->next = head;
} else if (cur == tail) {
tail = tail->prev;
tail->next = head;
head->prev = tail;
} else {
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
}
delete cur;
}
}
private:
Node* head;
Node* tail;
};
```