自定义高效链表容器的STL_list模拟
实现自定义高效链表容器类似于标准模板库(STL)中的std::list
,我们需要定义一个双向链表的数据结构,并实现基本的操作方法。以下是一个简单的实现示例:
#include <iostream>
// 定义节点结构
template<typename T>
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& data) : data(data), prev(nullptr), next(nullptr) {}
};
// 自定义链表类
template<typename T>
class MyList {
public:
MyList() : head(nullptr), tail(nullptr), size(0) {}
~MyList();
void push_back(const T& value);
void pop_back();
void push_front(const T& value);
void pop_front();
std::size_t getSize() const { return size; }
bool empty() const { return size == 0; }
void printList() const;
private:
Node<T>* head;
Node<T>* tail;
std::size_t size;
void clear();
};
// 析构函数,清空链表
template<typename T>
MyList<T>::~MyList() {
clear();
}
// 添加元素到链表尾部
template<typename T>
void MyList<T>::push_back(const T& value) {
Node<T>* newNode = new Node<T>(value);
if (empty()) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
++size;
}
// 移除链表尾部的元素
template<typename T>
void MyList<T>::pop_back() {
if (empty()) return;
Node<T>* toDelete = tail;
if (tail == head) {
head = tail = nullptr;
} else {
tail = tail->prev;
tail->next = nullptr;
}
delete toDelete;
--size;
}
// 添加元素到链表头部
template<typename T>
void MyList<T>::push_front(const T& value) {
Node<T>* newNode = new Node<T>(value);
if (empty()) {
head = tail = newNode;
} else {
head->prev = newNode;
newNode->next = head;
head = newNode;
}
++size;
}
// 移除链表头部的元素
template<typename T>
void MyList<T>::pop_front() {
if (empty()) return;
Node<T>* toDelete = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->next;
head->prev = nullptr;
}
delete toDelete;
--size;
}
// 输出链表中的元素
template<typename T>
void MyList<T>::printList() const {
Node<T>* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
// 清空链表
template<typename T>
void MyList<T>::clear() {
while (!empty()) {
pop_front();
}
}
// 示例用法
int main() {
MyList<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.printList(); // 输出: 1 2 3
list.pop_front();
list.printList(); // 输出: 2 3
list.push_front(0);
list.printList(); // 输出: 0 2 3
list.pop_back();
list.printList(); // 输出: 0 2
return 0;
}
这个示例自定义了一个模板类MyList
以实现一个简单的双向链表。它支持基本的push_back
、pop_back
、push_front
、pop_front
等操作。链表操作实行动态内存管理,并具有清理单独节点的方法。这种自定义类模拟了一部分std::list
的行为,适合了解链表的工作原理。