从零开始手写STL库：List
从零开始手写STL库–List部分
Github链接：miniSTL
文章目录
- 从零开始手写STL库–List部分
- List是什么？
- List需要包含什么函数
- 1）基础成员函数
- 2）核心功能
- 3)其他功能
- 基础成员函数的编写
- 核心功能的编写
- 其他功能编写
- 总结
List是什么？
std::list是基于双向链表的的数据结构，与std::vector基于数组不同，list在频繁插入和删除的场景中更适合应用。
List需要包含什么函数
应当具有：
1）基础成员函数
构造函数：初始化List头节点
析构函数：释放内存，当运行结束后要摧毁这个List防止内存泄漏
不同于Vector，List这种以链表为基础的容器一般不需要去拷贝新的List，也就不用手动构建拷贝构造函数和拷贝赋值操作符
2）核心功能
push_back/push_front：在List的末尾/头部加入新元素
pop_back/pop_front：移除List末尾/头部元素
size：获取List长度
clear：清空List
get：获取List中某个元素的值
remove：删除某个节点
find：查找某个值对应的节点
empty：检查List是否为空
3)其他功能
迭代器、重载输出符等等
基础成员函数的编写
List的成员：
List本身是链表，那么每个节点应该包括本节点的数据、指向上/下一个节点的指针，而List是描述这一系列节点构成的双向链表，那么只需要记录头节点、尾节点以及List长度即可
template<typename T>
class myList
{
private:struct Node{T data;Node * next;Node * prev;Node(const T & data_, Node * next_ = nullptr, Node * prev_ = nullptr): data(data_), next(next_), prev(prev_) {} };Node * head;Node * tail;size_t current_size;
public:};
构造函数和析构函数就是
public:myList() : head(nullptr), tail(nullptr), current_size(0) {}~myList() {clear(); }
再次提示，这里的构造函数用current_size(0) 初始化才是合规的，放在中括号内会浪费掉这个初始化进程
析构函数调用一下清空函数即可
核心功能的编写
1、push_back/push_front函数：在List的末尾/头部加入新元素
链表不像动态数组需要考虑分配问题，所以直接加就行了
但是也需要判断List为空的清空，如果为空，head/tail是没法取出next指针的，此时就会报错
所以在push的时候检查一下
（在力扣算法题中避免这种复杂操作的方法是构建一个虚拟头节点，就可以统一处理）
void push_back(const T & value){Node * temp = new Node(value, nullptr, tail);if(tail) tail->next = temp;else head = temp;tail = temp;current_size ++;}void push_front(const T & value){Node * temp = new Node(value, head, nullptr);if(head) head->prev = temp;else tail = temp;head = temp;current_size ++;}
2、pop_back/pop_front函数：移除List末尾/头部元素
头尾节点的删除较为简单，注意一下空列表的情况特殊处理即可
void pop_back(){if(current_size > 0){Node * temp = tail->prev;delete tail;tail = temp;if(tail) tail->next = nullptr;else head = nullptr;current_size --;}}void pop_front(){if(current_size > 0){Node * temp = head->next;delete head;head = temp;if(head) head->prev = nullptr;else tail = nullptr;current_size --;}}
这里如果删除之后发现头/尾节点是空了，说明这个List已经空了，但是另一端还没处理，所以要让另一端也为nullptr，否则有可能发生指针越界问题。
3、size函数：获取List长度
int size(){return current_size;}
4、clear函数：清空List
不同于vector那样直接将size归零，List需要考虑节点占用的内存，所以实际上是需要循环释放的
void clear()
{ while (head) { Node * temp = head;head = head->next; delete temp; } tail = nullptr; current_size = 0;
}
5、get函数：获取List中某个元素的值
这里的实现方法不是给定一个get函数，而是重载符号“[]”，这样就能更加方便地访问了
T &operator[](size_t index){Node * curr = head;for(size_t i = 0; i < index; i ++){if(!curr) throw std::out_of_range("Index out of range!");curr = curr->next;}return curr->data;}const T & operator[](size_t index) const{Node * curr = head;for(size_t i = 0; i < index; i ++){if(!curr) throw std::out_of_range("Index out of range!");curr = curr->next;}return curr->data;}
这里返回值设置为引用是考虑到一下情况
myList testList;
testList[2] = 4;
如果返回的不是引用，那么这样的赋值就会失效，并不能真的修改掉List的节点元素
6、remove函数：删除某个节点
那么这里需要查找到该节点，再进行删除，而且需要注意它是头尾节点时的情况
void remove(const T & val){Node * temp = head;while (temp && temp->data != val){temp = temp->next;}if(!temp) return;if(temp != head && temp != tail){temp->prev->next = temp->next;temp->next->prev = temp->prev;}else if(temp == head && temp == tail){head = nullptr;tail = nullptr;}else if(temp == head){head = temp->next;head->prev = nullptr;}else{tail = temp->prev;tail->next = nullptr;}current_size --;delete temp;temp = nullptr;}
7、find函数：查找某个值对应的节点
循环遍历对比就行
Node * getNode(const T & val){Node * node = head;while (node && node->data != val){node = node->next;}return node;}T *find(const T &val){Node * node = getNode(val);if(!node) return nullptr;return & node->data;}
8、empty函数：检查List是否为空
bool empty(){return current_size == 0;}
其他功能编写
迭代器
Node * begin() { return head; }Node * end() { return nullptr; }const Node * begin() const { return head; }const Node * end() const { return nullptr; }
重载<<符号
template <typename T>
std::ostream &operator<<(std::ostream &os, myList<T> &pt)
{for (auto current = pt.begin(); current; current = current->next){os << " " << current->data;}os << std::endl;return os;
}
总结
List的编写中，难点在于考虑链表为空的情况，很多个函数都需要去考虑，并且处理头尾节点，实际上是个细致的工作，并不在于思路上有多难。
在经常增删的情况下，用List会比Vector更为合适，代价是内存用得比较多，空间换时间。