目录
list的成员变量
list的迭代器
迭代器的定义
迭代器*和->
迭代器的++和--
迭代器的==和!=
迭代器代码汇总
list的成员函数
迭代器的begin和end
构造函数
无参构造
迭代器构造
n的val构造
拷贝构造
尾插和头插
尾删和头删
指定位置插入，删除
swap交换
clear
返回首节点和尾节点
返回链表长度
判空
赋值运算符重载
补充练习
栈的压入和弹出
最小栈问题
在C++中list实际上是一个双向带头循环链表，所以list是不支持随机访问的。list的迭代器类型是双向迭代器，与string和vector不同的是，list不是简单的指针，list的迭代器是类。此处本文将会详细讲解。
list的成员变量
list的成员变量是指向哨兵位节点的指针，通过定义ListNode类来实现节点的定义及使用。注意：此处使用struct来声明ListNode而不用class的原因是：struct默认权限是public而private的默认权限是private，直接用struct可以让类外直接访问。
template<class T>
struct ListNode
{//初始化节点ListNode(const T& val=T()):_val(val),_next(this),_prev(this){}T _val;ListNode<T>* _next;ListNode<T>* _prev;
};template<class T>
class list
{
public:typedef ListNode<T> ListNode;private:ListNode* _phead;
};list的迭代器
list底层是节点所以list是不支持随机访问的，因此不能简单的对指针++或--来实现对迭代器的左移和右移。list迭代器底层也是一个类，这个类用来存放当前节点。重载++，--等等迭代器的基本功能。
迭代器的定义
此处的模板并不完善，后面还要添加其他模板。
//创建list迭代器
template<class T>
struct list_iterator
{typedef ListNode<T> ListNode;typedef list_iterator<T> list_iterator;//构造函数list_iterator(ListNode* node = nullptr):_node(node){}ListNode* _node;
};迭代器*和->
//重载解引用*
T& operator*()
{return _node->_val;
}
//重载->
T* operator->()
{return &(operator*); //此处直接调用*运算符重载来实现取地址
}注意：此处需要考虑只有读取权限的const_iterator不能对解引用的数据进行修改，所以再使用T&和T*是明显不够的。
因此需要添加模板参数来实现const_iterator。
template<class T,class Ref ,class Ptr>
//用ref来代替T&和const T&，同理用Ptr来代替T*和const T*
typedef list_iterator<T,Ref,Ptr> Self;//重载解引用*
Ref operator*()
{return _node->_val;
}//重载->
Ptr operator->()
{return &(operator*); //此处直接调用*运算符重载来实现取地址
}在list的类中iterator和const_iterator的声明如下；
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;迭代器的++和--
typedef list_iterator<T,Ref,Ptr> Self;//重载++,非const类型
Self operator++()
{_node = _node->_next;return *this;
}
//重载--，非const类型
Self operator--()
{_node = _node->_prev;return *this;
}//重载++,const类型
Self operator++()const
{_node = _node->_next;return *this;
}
//重载--，const类型
Self operator--()const
{_node = _node->_prev;return *this;
}此处前置++和--就不展示了。
迭代器的==和!=
//重载==
bool operator==(const Self& it)
{return _node == it._node;
}
//重载!=
bool operator!=(const Self& it)
{return !(*this==it); //此处直接调用==
}迭代器代码汇总
//创建list迭代器
template<class T,class Ref ,class Ptr>
//用ref来代替T&和const T&，同理用Ptr来代替T*和const T*
struct list_iterator
{typedef ListNode<T> ListNode;typedef list_iterator<T,Ref,Ptr> Self;//构造函数list_iterator(ListNode* node = nullptr):_node(node){}//重载++,非const类型Self operator++(){_node = _node->_next;return *this;}//重载--，非const类型Self operator--(){_node = _node->_prev;return *this;}//重载++,const类型Self operator++()const{_node = _node->_next;return *this;}//重载--，const类型Self operator--()const{_node = _node->_prev;return *this;}//重载解引用*Ref operator*(){return _node->_val;}//重载->Ptr operator->(){return &(operator*); //此处直接调用*运算符重载来实现取地址}//重载==bool operator==(const Self& it){return _node == it._node;}//重载!=bool operator!=(const Self& it){return !(*this==it); //此处直接调用==}ListNode* _node;
};list的成员函数
template<class T>
class list
{
public:typedef ListNode<T> ListNode;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;private:ListNode* _phead;
};迭代器的begin和end
//begin函数，非const类型
iterator begin()
{return _phead->_next; //此处使用了隐式类型转化，将ListNode*转化为了iterator
}
//end函数，非const类型
iterator end()
{return _phead;
}
//begin函数，const类型
const_iterator begin()const
{return _phead->_next;
}
//end函数，const类型
const_iterator end()const
{return _phead;
}构造函数
无参构造
//构造函数，无参初始化
list():_phead(new ListNode) //此处需要创建哨兵位，交给ListNode的构造函数
{}迭代器构造
此处偷懒直接调用了push_back尾插函数。
//迭代器构造函数
template<class T>
list(const T* first, const T* last): _phead(new ListNode) //还是创建哨兵位
{while (first != last){push_back(*first);++first;}
}n的val构造
//用n个val构造
list(size_t n, const T& val):_phead(new ListNode)
{while (n--){push_back(val);}
}拷贝构造
//拷贝构造
list(const list& l): _phead(new ListNode)
{for (auto& e : l) //范围for遍历原链表{push_back(e);}
}尾插和头插
尾插即创建新节点，对原有节点的指针进行修改。
//尾插
void push_back(const T& val)
{ListNode* newnode = new ListNode(val);newnode->_next = _phead;newnode->_prev = _phead->_prev;_phead->_prev->_next = newnode;_phead->_prev = newnode;
}//头插
void push_front(const T& val)
{ListNode* newnode = new ListNode(val);newnode->_next = _phead->_next;newnode->_prev = _phead;_phead->_next->_prev = newnode;_phead->_next = newnode;
}尾删和头删
删除就是记录需要删除的节点位置将其前后节点指向改变即可。
//尾删
void pop_back()
{ListNode* del = _phead->_prev;del->_prev->_next = _phead;_phead->_prev = del->_prev;delete[] del;
}
//头删
void pop_front()
{ListNode* del = _phead->_next;del->_next->_prev = _phead;_phead->_next = del->_next;delete[] del;
}指定位置插入，删除
通过迭代器实现指定位置的插入和删除。指定位置插入会返回插入节点的迭代器；指定位置删除会返回删除位置的下一个迭代器。
//指定位置之前插入
iterator insert(iterator it, const T& val)
{ListNode* newnode = new ListNode(val);ListNode* cur = it._node;newnode->_next = cur;newnode->_prev = cur->_prev;cur->_prev->_next = newnode;cur->_prev = newnode;return newnode;
}
//指定位置删除
iterator erase(iterator it)
{ListNode* del = it._node;ListNode* cur = del->_next;del->_prev->_next = cur;cur->_prev = del->_prev;return cur;
}swap交换
此处为了实现swap(l1,l2)，而不是l1.swap(l2)，需要使用友元函数而不是成员函数。
注意：编译器在解析友元函数的时候无法正确的匹配外部声明的模板函数，此时就需要在声明的时候也加上模板参数。
template<class T>
friend void swap(list<T>& l1, list<T>& l2);template<class T>
void swap(list<T>& l1, list<T>& l2)
{std::swap(l1._phead, l2._phead);
}clear
list::clear函数的作用是清空有效节点，只保留哨兵位。注意：清空节点之后还要将哨兵位指向本身。
void clear()
{ListNode* cur = _phead->_next;while (cur != _phead){ListNode* del = cur;cur = cur->_next;delete[] del;}//清空数据之后，将哨兵位指向哨兵位_phead->_next = _phead;_phead->_prev = _phead;
}返回首节点和尾节点
返回首尾节点的值。
//非const类型
T& front()
{return _phead->_next->_val;
}
T& back()
{return _phead->_prev->_val;
}
//const类型
const T& front()const
{return _phead->_next->_val;
}
const T& back()const
{return _phead->_prev->_val;
}返回链表长度
//返回链表长度
size_t size()
{ListNode* cur = _phead->_next;size_t sz = 0;while (cur != _phead){cur = cur->_next;++sz;}return sz;
}判空
//链表是否为空
bool empty()
{return _phead == _phead->_next;
}赋值运算符重载
进行赋值的是否需要先将原链表的所有数据清空。
//赋值运算符重载
list& operator=(const list& l)
{clear();ListNode* cur = l._phead->_next;while (cur != l._phead){push_back(cur->_val);cur = cur->_next;}return *this;
}