1，list的底层是双向链表结构，双向链表中，每个元素存储在互不相关的节点中，在节点中保存着指向前一个节点和后一个节点的指针。

2，与forward_list相似，forward_list是单链表，只能向前迭代。而list是双向链表，可以前后迭代。

3，list与vector相比，它的插入和删除元素效率更高，不需要遍历一遍原链表。

二，list的一些基本使用

2.1，list的构造函数

list()     //无参构造函数 list(size_t n,const value_type& val = value_type())    //n个va的构造 list(InputIterator first,InputIterator last)     //迭代器区间构造 list(const list& x)                  //拷贝构造

示例:

void Test_List1() {     list<int> lt1;              //无参构造，值为空     list<int> lt2(4, 100);   //4个100初始化     list<int> lt3(lt2.begin(), lt2.end());   //迭代器区间构造     list<int> lt4(lt2);            //拷贝构造 }

注：C++11提供了initializer_list的新类型，主要用于初始化。 

用法如下：

initializer_list<int> lt = { 1,2,3,4,5 }; list<int> lst(lt);          //用lt中的元素初始化lst

但一般在写的时候，可以使用隐式类型转化

list<int> lt = { 1,2,3,4,5 };     //和上面代码一样 

2.2，list的迭代器

list提供了双向迭代器，可用于遍历和操作容器中的数据。

1. begin()：返回指向第一个元素的迭代器。
2. end()：返回指向最后一个元素之后位置的迭代器。
3. rbegin()：返回指向最后一个元素的逆向迭代器。
4. rend()：返回指向第一个元素之前位置的逆向迭代器。

代码语言：javascript

AI代码解释

void Test_List2()
{
    list<int> myList = { 1, 2, 3, 4, 5 };

    // 正向迭代器遍历list
    cout << "正向遍历list: ";
    list<int>::iterator itr;
    for (itr = myList.begin(); itr != myList.end(); ++itr)
    {
        cout << *itr << " ";
    }
    cout << endl;

    // 逆向迭代器遍历list
    cout << "逆向遍历list: ";
    list<int>::reverse_iterator ritr;
    for (ritr = myList.rbegin(); ritr != myList.rend(); ++ritr)
    {
        cout << *ritr << " ";
    }
    cout << endl;

}

运行结果：

2.3，list的插入

对于插入操作，list实现了如下几个常用的接口

push_back(x)     //尾插 push_front(x)      //头插 insert(iterator it ,x)   //在迭代器位置之前插入x

示例： 

代码语言：javascript

AI代码解释

void Test_List3()
{
    list<int> lt;
    //尾插
    lt.push_back(1);
    lt.push_back(2);
    cout << "push_back:";
    for (auto e : lt)
        cout << e << " ";
    cout << endl;
    //头插
    lt.push_front(4);
    lt.push_front(5);
    cout << "push_front:";
    for (auto e : lt)
        cout << e << " ";
    cout << endl;
    //迭代器
    lt.insert(lt.begin(), 9);
    cout << "insert:";
    for (auto e : lt)
        cout << e << " ";
    cout << endl;
    
}

运行结果：

2.4，list的删除

对于删除，list提供的接口如下: 

pop_back()     //尾删 pop_front()     //头删 erase(iterator it)  //删除it位置 erase(iterator first,iterator last)  //删除[first,last)区间

 示例：

代码语言：javascript

AI代码解释

void Test_List4()
{
    list<int> it = { 1,2,3,4,5 };
    //尾删
    it.pop_back();
    cout << "pop_back:";
    for (auto e : it)
        cout << e << " ";
    cout << endl;
    //头删
    it.pop_front();
    cout << "pop_front:";
    for (auto e : it)
        cout << e << " ";
    cout << endl;
    //erase
    it.erase(it.begin());
    it.erase(it.begin(), it.end());
    cout << "erase:";
    for (auto e : it)
        cout << e << " ";
    cout << endl;
}

三，list的模拟实现

3.1，链表节点的定义

//定义节点 template<class T> struct list_node {     T _data;  //存储的数据     list_node<T>* prev;//指向前一个节点     list_node<T>* next;//指向后一个节点     //构造函数     list_node(const T& data=T())         :_data(data)         ,prev(nullptr)         ,next(nullptr)     {} };

 3.2，链表主体

3.2.1，链表的大致轮廓（含注释）

template<class T> class list { public:     typedef list_node<T> Node;     //构造函数     list()     {         //当只有一个节点时，为了保证满足双向链表的规则         //让新节点的next和prev指针指向自己         _head = new Node;         _head->_next = _head;         _head->_prev = _head;         _size = 0;     } private:     Node* _head;  //头节点     size_t _size; //记录数据个数 };

 3.2.2，常见接口的实现

插入操作

insert(iterator it,T x)  ,迭代器前插入

void insert(iterator pos, const T& x) {     Node* cur = pos._node;     Node* prev = cur->_prev;     Node* newnode = new Node(x);     //链接前一个指针和后一个指针     // prev newnode cur     newnode->_next = cur;     cur->_prev = newnode;     newnode->_prev = prev;     prev->_next = newnode;     ++_size; }

push_back(x），尾插。直接开辟一个新节点来存储x的值，让新节点链接到链表的最后。

注意：需要改变头节点和原链表最后一个节点指针的指向。

void push_back(const T& x) {     Node* newnode = new Node(x);//开辟新节点存储x     Node* tail = _head->_prev;  //插入之前，原链表的尾节点     tail->_next = newnode;     newnode->_prev = tail;     newnode->_next = _head;     _head->_prev = newnode;     ++_size;   //插入后，数据个数++ }

push_front,头插。这里可以直接复用上面写过的insert逻辑。在迭代器begin() 位置之前插入x，也就是头插。当然尾插操作也可以复用

void push_front(const T& x) {       insert(begin(), x); }

删除操作

erase(iterator it),删除迭代器位置

删除之前，需要将前一个节点和后一个节点链接起来

void erase(iterator pos) {     assert(pos != end());     Node* prev = pos._node->_prev;     Node* next = pos._node->_next;     //先将删除位置的前一个节点和后一个节点链接起来     prev->_next = next;     next->_prev = prev;     delete pos._node;  //释放当前节点     --_size;    //数据个数-- }

pop_back()  ,尾删 ,复用erase逻辑。end(),是最后一个节点的下一个位置，所以要--

void pop_back() {     erase(--end()); } 

pop_front(),头删，复用erase逻辑

void pop_front() {     erase(begin()); } 

返回链表的数据个数 

size_t size() const {     return _size; }

判断链表是否为空

 bool empty() const {     return _size == 0; }

3.2.3，迭代器的实现

对于list的迭代器，我们用来遍历链表。那么，我们需要实现对++，--，！=，*，->等操作符的重载，同时还需要节点。所以我们需要对链表的节点进行一次封装，实现对++，--，！=，*,->等操作符的重载