一、list的介绍
std::list是C++标准模板库(STL)中的一个双向链表容器。与vector和deque不同，list不支持随机访问，但它在任何位置插入和删除元素都非常高效。
1.基本特性
(1)双向链表结构：每个元素都包含指向前驱和后继的指针
(2)非连续存储：元素分散存储在内存中，通过指针连接
(3)时间复杂度：
任意位置插入/删除：O(1)
随机访问：O(n)
遍历：O(n)
二、list常用操作
我这里就通过调试来带大家看一下每个函数的效果。
1.创建和构造
列举了一些list构造时的基础用法.
#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1; // 空listlist<int> l2(5); // 包含5个默认构造的元素(0)list<int> l3(5, 10); // 包含5个值为10的元素list<int> l4 = { 1, 2, 3 }; // 初始化列表list<int> l5(l4); // 拷贝构造list<int> l6(l5.begin(), l5.end()); // 通过迭代器范围构造return 0;
} 
2.迭代器
由于list不支持随机访问，只能通过迭代器或front/back方法访问元素：
list<int> l = { 1, 2, 3, 4, 5 };cout << l.front()<<endl; // 第一个元素 (1)
cout << l.back()<<endl; // 最后一个元素 (5)// 遍历list
for (auto it = l.begin(); it != l.end(); ++it) {cout << *it << " ";
}
cout << endl;
// C++11起可用范围for循环
for (int val : l) {cout << val << " ";
}
return 0;
迭代器构造：
3.拷贝构造
4.clear()
效果：清空链表中所有数据。
5.size()
返回链表中节点的个数
6.push_back(const T& x)
在链表尾部插入值为x的节点。
7.push_front(const T& x)
在链表头部插入值为x的节点。
8.insert(iterator pos, const T& x)
在第pos个位置插入值为x的节点。
9.pop_back()
删除尾部元素
10.pop_front()
删除头部元素
11.erase(iterator pos)
删除第pos位置的元素
三、list的模拟实现
1.构造函数
首先我们可以通过STL库学习一下list的基本实现方法，然后自己根据SLTL库中的代码模拟实现一个list。
通过库中代码，我们需要先实现出list底层节点的模板以及迭代器所需要的模板，然后在构造函数。代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>namespace lwf
{//创建模板结构体template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};//创建模板结构体template<class T, class Ref, class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}private:Node* _head;size_t _size;};
}2.迭代器
iterator begin(){//return iterator(_head->next);return _head->_next;}iterator end(){return _head;}const_iterator begin()const{//return iterator(_head->next);return _head->_next;}const_iterator end()const{return _head;}3.拷贝构造
拷贝构造的实现就是将原有的list变量拷贝给被拷贝对象深拷贝。
list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}void swap(list<T> It){std::swap(_head, It._head);std::swap(_size, It._size);}list<T>& operator=(list<T> It)//list& operator=(list<T> It) 这样写也可以{swap(It);return *this;}4.clear()
通过迭代器来将list中元素逐个删除
void clear(){iterator it=begin();while (it != end()){it = erase(it);}_size = 0;}5.size()
返回内部元素_size（_size一直是在统计list中元素的个数）即可。
size_t size(){return _size;}
6.insert(iterator pos, const T& x)
首先需要创建一个新节点，然后通过双链表结构的思路将节点插入所需要插入的位置，双链表在前面的博客中有实现过，需要的可自行查看。。
iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;++_size;//解决迭代器失效问题return newnode;}7.push_back(const T& x)
在list尾部插入x，此时我们这里可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。
void push_back(const T& x){/*Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}8.push_front(const T& x)
在list头部插入x，此时我们这里也可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。
void push_front(const T& x){insert(begin(), x);}9.erase(iterator pos)
删除list中pos位置的元素，这里的思路其实同双链表的删除操作一样，前面的博客中有实现过，需要的可自行查看。
iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//解决迭代器失效问题return next;}
10.pop_back()
删除list的尾部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。
void pop_back(){erase(--end());}11.pop_front()
删除list的头部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。
void pop_front(){erase(begin());}12.析构函数
这里我们可以直接调动clear()函数来清除链表中的节点，然后释放private中的_head节点即可。
~list(){clear();delete _head;_head = nullptr;}四、实现的整体代码。
这里是自我实现的所有代码的集合，需要的可自行拿取。
#pragma once#include<iostream>
using namespace std;
#include <assert.h>namespace lwf
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};/*template<class T>struct _list_const_iterator{typedef list_node<T> Node;Node* _node;_list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->val;}_list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}_list_const_iterator<T> operator++(int){_list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const _list_const_iterator<T>& it)const{return _node != it._node;}bool operator==(const _list_const_iterator<T>& it)const{return _node == it._node;}};*/template<class T>class list{typedef list_node<T> Node;public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->next);return _head->_next;}iterator end(){return _head;}const_iterator begin()const{//return iterator(_head->next);return _head->_next;}const_iterator end()const{return _head;}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}void swap(list<T> It){std::swap(_head, It._head);std::swap(_size, It._size);}list<T>& operator=(list<T> It)//list& operator=(list<T> It) 这样写也可以{swap(It);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it=begin();while (it != end()){it = erase(it);}_size = 0;}size_t size(){return _size;}void push_back(const T& x){/*Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;++_size;//解决迭代器失效问题return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//解决迭代器失效问题return next;}private:Node* _head;size_t _size;};void Test_1(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);It.push_front(5);It.push_front(6);It.push_front(7);It.push_front(8);for (auto& e : It){cout << e << " ";}cout << endl;It.pop_back();It.pop_front();for (auto& e : It){cout << e << " ";}cout << endl;}void Test_2(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);It.push_front(5);It.push_front(6);It.push_front(7);It.push_front(8);for (auto& e : It){cout << e << " ";}cout << endl;It.pop_back();It.pop_front();for (auto& e : It){cout << e << " ";}cout << endl;It.clear();It.push_front(50);It.push_front(60);It.push_front(70);It.push_front(80);for (auto& e : It){cout << e << " ";}cout << endl;cout << It.size() << endl;}void Test_3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);for (auto e : lt2){cout << e << " ";}cout << endl;lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;}
}五、感言
家人们创作不易，在这里感谢各位大佬和友友们的支持，如果各位有所收获，不介意的话给我点个赞再走吧，感谢大家！
