实现一个双向链表的类模板
时间: 2023-05-12 18:04:34 浏览: 111
好的,以下是一个双向链表的类模板的实现:
```cpp
template <typename T>
class DoublyLinkedList {
private:
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& d = T{}, Node* p = nullptr, Node* n = nullptr)
: data{ d }, prev{ p }, next{ n } {}
};
Node* head;
Node* tail;
int size;
public:
DoublyLinkedList() : head{ nullptr }, tail{ nullptr }, size{ 0 } {}
~DoublyLinkedList() { clear(); }
DoublyLinkedList(const DoublyLinkedList& rhs) : head{ nullptr }, tail{ nullptr }, size{ 0 } {
for (auto it = rhs.begin(); it != rhs.end(); ++it) {
push_back(*it);
}
}
DoublyLinkedList& operator=(const DoublyLinkedList& rhs) {
DoublyLinkedList copy{ rhs };
std::swap(head, copy.head);
std::swap(tail, copy.tail);
std::swap(size, copy.size);
return *this;
}
int getSize() const { return size; }
bool isEmpty() const { return size == 0; }
void clear() {
while (!isEmpty()) {
pop_front();
}
}
T& front() { return head->data; }
const T& front() const { return head->data; }
T& back() { return tail->data; }
const T& back() const { return tail->data; }
void push_front(const T& data) {
head = new Node{ data, nullptr, head };
if (tail == nullptr) {
tail = head;
}
else {
head->next->prev = head;
}
++size;
}
void push_back(const T& data) {
tail = new Node{ data, tail, nullptr };
if (head == nullptr) {
head = tail;
}
else {
tail->prev->next = tail;
}
++size;
}
void pop_front() {
Node* oldHead = head;
head = head->next;
if (head == nullptr) {
tail = nullptr;
}
else {
head->prev = nullptr;
}
delete oldHead;
--size;
}
void pop_back() {
Node* oldTail = tail;
tail = tail->prev;
if (tail == nullptr) {
head = nullptr;
}
else {
tail->next = nullptr;
}
delete oldTail;
--size;
}
class Iterator {
private:
Node* current;
public:
Iterator(Node* n = nullptr) : current{ n } {}
T& operator*() const { return current->data; }
T* operator->() const { return ¤t->data; }
Iterator& operator++() {
current = current->next;
return *this;
}
Iterator operator++(int) {
Iterator old{ *this };
++(*this);
return old;
}
Iterator& operator--() {
current = current->prev;
return *this;
}
Iterator operator--(int) {
Iterator old{ *this };
--(*this);
return old;
}
bool operator==(const Iterator& rhs) const { return current == rhs.current; }
bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }
};
Iterator begin() const { return Iterator{ head }; }
Iterator end() const { return Iterator{ nullptr }; }
Iterator rbegin() const { return Iterator{ tail }; }
Iterator rend() const { return Iterator{ nullptr }; }
};
```
希望这个实现能够满足你的需求!
阅读全文
相关推荐
















