? ? ? ? 接前面的手撕list(上)文章，由于本人對于list的了解再一次加深。本文再次對list進行深入的分析與實現。旨在再一次梳理思路，修煉代碼內功。

1、list 基礎架構

? ? ? ? list底層為雙向帶頭循環鏈表，問題是如何來搭建這個list類。可以進行下面的考慮：? ? ? ?

1、list為帶頭雙向循環鏈表，鏈表離不開節點。要能在list內部創建節點。

2、list內部沒有數據時，也應該存在哨兵位頭節點。

3、list內部的數據類型是未知的，需要寫成類模板。

4、list支持迭代器訪問數據，但是由于鏈表的結構來說，普通指針類型的迭代器不能實現++和解引用等基礎訪問操作，這就需要封裝一個迭代器對象。

? ? ? ? 由于鏈表是雙向的，所以節點的成員屬性主要為三個：??

1. 節點指針類型的_next:指向該節點的下一個節點。
2. 節點指針類型的_prev:指向該節點的前一個結點。
3. 未知數據類型的數據_val:鏈表中存放的數據。

? ? ? ? 那么list的成員屬性應該有什么？

1. 頭節點的指針_head:?作為鏈表的起始點，通過它可以訪問鏈表的第一個元素和最后一個元素。在雙向循環鏈表中，頭節點的_next?指針指向鏈表的第一個有效節點，_prev指針指向鏈表的最后一個有效節點。
2. 節點的個數_size:記錄鏈表中有效節點的數量，方便快速獲取鏈表的長度，而不需要遍歷整個鏈表來計算。在插入和刪除節點時，需要相應地更新這個計數器。

? ? ? ? 迭代器主要依賴于節點，利用節點才能找到節點當中的數據，并可以通過對運算符的重載實現迭代器本身的基礎操作。故迭代器的成員屬性為節點的指針。

? ? ? ? 由于在list當中要使用到節點當中的所有成員變量，所以這里直接就將節點類寫為struct主要就是在內部的訪問限定符默認為public，迭代器類型也是同樣的道理。

namespace ltq
{template<class T>struct __list_node{__list_node<T>* _prev;__list_node<T>* _next;T _val;};template<class T>struct __list_iterator{typedef __list_node<T> Node;Node* _node;};template<class T>class list{typedef __list_node<T> Node;public:typedef __list_iterator<T> iterator;private:Node* _head;size_t _size;};
}

? ? ? ? 下面需要完善的就是三個類型的構造函數，?首先需要明確關系：list要使用的是節點類和迭代器類，在list類中創建了節點和迭代器對象就會去調用它們自己的構造函數。當然，在外部要是使用到list創建了對象，那么也會調用list自身的構造函數。

		list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}

? ? ? ? new先開辟空間，然后調用Node的構造函數，由于list的哨兵位節點中可以不用存放數據，所以直接調用Node的默認構造即可。下面就需要完善Node的默認構造。

	template<class T>struct __list_node{__list_node<T>* _prev;__list_node<T>* _next;T _val;__list_node(const T& x = T()):_prev(nullptr),_next(nullptr),_val(x){}};

? ? ? ? 這里的默認構造使用缺省參數，當沒有形參傳過來時就創建T類型的匿名對象對節點中的數據進行初始化。?

2、void push_back(const T& x)

? ? ? ? 雙向帶頭循環鏈表的末尾插入需要找到末尾的節點，再創建新的節點進行鏈接。這里需要更新_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;++_size;}

3、迭代器

? ? ? ? 迭代器開始位置返回的是哨兵位頭節點的下一個節點，迭代器的末尾返回的是哨兵位頭節點的指針，這樣設計就能實現左閉右開的區間。

		iterator begin(){return _head->_next;}iterator end(){return _head;}

? ? ? ? ?在前面我故意沒有寫迭代器的構造函數，其實這里就會很明顯的發現，不管是什么類型的迭代器在返回的時候都是傳遞節點的指針。由于單參數的構造函數支持隱式類型的轉換，那么節點的指針就會通過迭代器的構造函數構造出一個迭代器對象并返回，這里需要注意的是，傳值返回會生成臨時對象，臨時對象具有常性。

? ? ? ? 那么，我們現在來實現一下迭代器的構造函數。

	template<class T>struct __list_iterator{typedef __list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}};

3.1、必要的運算符重載

    T& operator*(){return _node->_val;}__list_iterator<T>& operator++(){_node = _node->_next;return *this;}    __list_iterator<T> operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_iterator<T>& it){return _node != it._node;}

? ? ? ? 有了迭代器就支持范圍for了，現在我們來測試一下目前的list是否可用：

3.2、箭頭的重載

? ? ? ? 假如鏈表中存放的是結構體類型的數據，假設結構體為：

struct A
{A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};

? ? ? ? 如果要訪問A內部的數據，此時對迭代器進行解引用是不能訪問到A內部的數據的。此時重載箭頭，通過拿到A對象的地址，使用A的地址來達到訪問內部數據的內容。重載箭頭可以通過解引用再取地址的方式進行實現。

? ? ? ? 當然也可以通過使用對象+.的方式來進行訪問。

4、iterator 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);newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;++_size;return newNode;}

? ? ? ? ?雖然鏈表的插入不像vector的插入會產生擴容問題而引發迭代器失效，這里返回新插入節點的迭代器主要是方面插入之后的鏈式操作。其次與STL保持一致。

5、iterator erase(iterator pos)

? ? ? ?刪除當前迭代器位置，這里也不像vector，刪除當前位置的數據并不影響后續節點的迭代器，但是當list刪除當前節點時，會進行釋放節點。那么當前節點的迭代器就會懸空，對懸空的迭代器進行操作就會引發錯誤，所以，在刪除之后也會返回下一個節點的迭代器。

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

6、void clear()

? ? ? ? 內部調用erase函數對節點進行清除釋放，但保留頭節點。

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}

7、拷貝構造?

? ? ? ? 這里要進行深拷貝，先為新對象創建一個頭結點，再使用范圍for拿出目標鏈表中的每一個數據，直接進行push_back()操作即可。

		list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto& e:lt){push_back(e);}}

8、賦值重載

????????直接采用傳值傳參，傳值傳參調用拷貝構造，之后進行對象交換即可。

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> tmp){swap(tmp);return *this;}