1.list的底层结构是带头双向循环链表
2.类模板list的私有成员变量：节点指针,节点个数
template<class T>
class list
{
typedef list_node<T> Node;
public:
//.....
private:
Node* _head;
size_t _size;
};
3.为了便于存储节点的相关内容，要封装一个类模板list_node，又因为在后续的实现中需要频繁调用，故而选用struct将成员变量和成员函数均设为共有
1>成员变量：_data(该节点存储的数据),_next(下一个节点的地址),_prev(前一个结点的地址)
2>代码实现
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//将T的匿名对象，若T为自定义类型就去调用它的默认构造
list_node(const T& data=T())
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
};4.由于链表的结点地址不是连续的，无法完成*，++，--，!=等操作，所以为了实现迭代器，需要封装一个类模板list_iterator，又因为在类模板list中，迭代器需要被频繁调用，故而选用struct将成员变量和成员函数均设为共有
1>成员变量：节点指针
2>成员函数
(1)operator*
(2)operator++/operator--
(3)operator==/operator!=
3>代码实现
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T* operator->()
{
return &_node->_data;
}
T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator==(const self& s)
{
return _node==s._node ;
}
bool operator!=(const self& s)
{
return _node!=s._node;
}
};5.类模板list的成员函数
1>list的构造函数：list()
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}2>获取节点个数：size_t size() const
size_t size() const
{
return _size;
}3>迭代器的实现
(1)普通迭代器的实现
typedef list_iterator<T> iterator;
iterator begin()
{
/*iterator it(_head->_next);
return it;*/
//return iterator(_head->_next);
//发生隐式类型转换
return _head->_next;
}
iterator end()
{
return _head;
}
(2)const迭代器的实现：先实现const迭代器的封装，与list_iterator类似
template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator<T> self;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
const T* operator->()
{
return &_node->_data;
}
const T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
};typedef list_const_iterator<T> const_iterator;
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}4>判断节点是否为空：bool empty() const
(1)当只剩哨兵位时即为空
(2)代码实现
bool empty()
{
return _size==0;
}
5>在pos位置前插入数据：void insert(iterator pos,const T& x)
(1)将pos位置的节点，前一个节点分别记录下来，创建一个新节点，完成三个节点新的连接关系
(2)代码实现
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = pos._node->_prev;
Node* newnode = new Node(x);
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
return newnode;
}6>尾插/头插：直接调用insert函数
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}7>删除pos位置的数据：void erase(iterator pos)
(1)记录pos位置的前一个结点和后一个节点，完成两节点间新的连接关系，删除pos位置的节点
(2)代码实现
iterator 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;
return next;
}8>尾删，头删：直接调用erase函数
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}9>拷贝构造
(1)遍历链表，将节点一个一个插入，注意首先要现为未初始化的链表创建一个哨兵位
(2)代码实现
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
10>赋值：operator=
void swap(list<T> lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}11>析构
(1)遍历链表将每个节点删除出，最后删除_head
(2)代码实现
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
++it;
}
}