由于前面已經模擬實現了vector，所以這里關于一些函數實現就不會講的過于細致。

成員變量

template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}
};template<class T>
class list
{typedef ListNode<T> Node;
public:list(){_head = new Node;_head->_next = _head->_prev = _head;_size = 0;}size_t size()const{return _size;}
private:Node* _head;size_t _size;
};

迭代器（重點）

我們想要迭代器能實現以下的功能：

void test_1()
{list<int>lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}cout << endl;
}

實際上迭代器模擬的是指針的功能，然而鏈表的指針++并不會得到下一個元素的指針。但我們卻希望迭代器++能得到下一個元素的迭代器。

那么我們是不是需要對++進行一個修改，也就是運算符重載。

再仔細想想，重載后的運算符是對這一個類生效的，但我們只需要對迭代器生效。那是不是意味著我們的迭代器需要是一個獨立的類：

ListIterator

template<class T>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;//內置類型指針ListIterator(Node* node):_node(node){}
}

注意不需要析構函數，實際上我們的迭代器就是原數組結點指針的一個類，怎么可以用過一次后就析構掉呢？

運算符重載

前置++：

Self& operator++()//前置++
{_node = _node->_next;return *this;
}

后置++：

Self operator++(int)//后置++
{Self tmp(*this);//淺拷貝_node = _node->_next;return tmp; 
}

值得注意的是，前后++的重載函數名都是operator++，那么如何區分他們呢？

C++語法規定：后置++的函數參數里面需要有一個int。

此外，我這的tmp是一個淺拷貝，這樣做有沒有問題呢？
我們需要的是指針，那么對于指針自然應該采用淺拷貝。
事實上，我們一般有一個規律：如果類需要重載析構函數，那么一般就要深拷貝，反之一般就需要淺拷貝。

剩余運算符：

Self& operator*()
{return _node->_data;
}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;
}

begin、end

注意到我們的begin是返回首元素迭代器，而end是返回最后一個元素的下一個位置的迭代器：

typedef ListIterator<T> iterator;
iterator begin() 
{return _head->_next;
}iterator end()
{return iterator(_head);
}

注意到，begin這里我返回的是_head->_next，因為單參數會隱式類型轉換：自動調用單參數的構造函數，也就是等價于iterator(_head->_next).

插入、刪除

insert

void insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

erase

iterator erase(iterator pos)//返回iterator防止迭代器失效
{Node* cur = pos->_node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);
}

值得注意的是，為了防止迭代器失效，我們這里要返回最后一個刪除的元素的下一個元素的迭代。

頭插、尾插、頭刪、尾刪

void push_back(const T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}void pop_back()
{erase(end()--);//沒有重載-1，所以要用--
}void pop_front()
{erase(begin());
}

尾刪這里需要注意一定要是end()–，而不能是end()-1.理由很簡單，因為我們沒有重載-。

operator->

對于非內置類型如下：

struct A
{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}
};void test_2()
{list<A>lt;A aa1(1, 1);lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2, 2));lt.push_back({ 3,3 });lt.push_back({ 4,4 });list<A>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';//不支持流插入++it;}}

不難發現cout << *it << ’ ';這里會報錯，因為自定義類型沒有重載<<。
因此我們需要改寫為：

cout << (*it)._a1 << ' ' << (*it)._a2 << endl;

不難發現這有些許繁瑣，正常來說對于類指針功能我們更希望用->這個操作符，也就是：

cout << it->_a1 << ' ' << it->_a2 << endl;

那就需要重載->：

Self* operator->()
{return &_node->_data;
}

這時候就有人發出疑問了，怎么返回值是一個指針，那要調用_a1，不應該是it->->_a1嗎？
沒錯，這是原生寫法，但是我們C++語法給他優化掉了，現在it->_a1等價于it.operator->()->_a1

const_iterator

const_iterator為什么不是const iterator?
這個問題其實前面學習類的時候已經解答過了，事實上我們的const_iterator是不能改變迭代器呢，還是不能改變迭代器指向的元素的值呢？
事實上const_iterator也是可以++的，否則怎么遍歷數組元素。
那也就是說const_iterator只是不能改變指向的元素的值，而不是不能改變迭代器本身。

經過上述分析我們得知，我們只需要對*和->重載的返回值作出修改即可：

const T& operator*()
{return _node->_data;
}const T* operator->()
{return &_node->_data;
}

但是，只有返回值不同是無法重載函數的！！
那么我們是不是需要再多寫一個const_iterator類呢？
可以，但有更好的方法。
注意到我們只有這兩個函數不同，并且只有返回值不同，那是不是可以寫一個模板將返回值不同分成不同的類呢？

template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}}
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

這樣我們就省去了CV再寫一個類的功夫。

拷貝構造

一樣是復用push_back

void empty_init()
{_head = new Node;_head->_next = _head->_prev = _head;_size = 0;
}
list(const T& lt)// 復用push_back來深拷貝
{empty_init();for (auto& e : lt){push_back(e);}
}

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;
}

析構函數

同樣復用erase

void clear()//沒清除頭結點
{iterator it = begin();while (it != end()){it = erase(it);}}~list()
{clear();delete _head;_head = nullptr;}

完整代碼

template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}
};template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;//內置類型指針ListIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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 ListNode<T> Node;
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin() //const{return iterator(_head->_next);}iterator end(){return iterator(_head);}//const_iterator而不是const iterator，因為是指向內容不能被修改，而非迭代器本身不能被修改。如果是const iterator就不能it++const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head->_prev = _head;_size = 0;}list(){empty_init();}list(const T& lt)// 復用push_back來深拷貝{empty_init();for (auto& e : lt){push_back(e);}}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;}void clear()//沒清除頭結點{iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//void push_back(const T& x)//{//	Node* newnode = new Node(x);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	newnode->_next = _head;//	_head->_prev = newnode;//}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(end()--);//沒有重載-1，所以要用--}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos)//返回iterator防止迭代器失效{Node* cur = pos->_node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size()const{return _size;}bool empty()const{return _size == 0;}private:Node* _head;size_t _size;
};