一、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; // 空list
list<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;
}
}五、感言
家人们创作不易，在这里感谢各位大佬和友友们的支持，如果各位有所收获，不介意的话给我点个赞再走吧，感谢大家！
