从零开始手写STL库：List

从零开始手写STL库–List部分

Github链接：miniSTL

---

---

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更为合适，代价是内存用得比较多，空间换时间。