前面的文章中，介紹了，的模擬實現(xiàn)，本篇文章將介紹對于的模擬實現(xiàn)。

目錄

1. list的基本結(jié)構(gòu)：

2. list功能實現(xiàn)：尾部插入元素：

3. list迭代器的實現(xiàn)：

4. list功能實現(xiàn)：在任意位置前插入元素：?

4.1 函數(shù)實現(xiàn)方法：

4.2 函數(shù)運行邏輯：

5. list功能實現(xiàn)：刪除任意位置的結(jié)點：

6. 拷貝構(gòu)造與賦值重載：

7. list功能實現(xiàn)：clear與析構(gòu)函數(shù)：

---

1. list的基本結(jié)構(gòu)：

對于，可以將其看作數(shù)據(jù)結(jié)構(gòu)中的雙向帶頭循環(huán)鏈表一起學數(shù)據(jù)結(jié)構(gòu)（4）——帶頭結(jié)點的雙向循環(huán)鏈表_帶頭結(jié)點的雙循環(huán)鏈表-CSDN博客

針對于雙向帶頭循環(huán)鏈表，其基本構(gòu)成單元為如下圖所示：

其中，用來保存上一個結(jié)點的地址，用于保存下一個結(jié)點的地址，用于保存數(shù)據(jù)。對于上述結(jié)構(gòu)單元，可以由下方的代碼表示：

namespace violent
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;};
}

對于雙向帶頭循環(huán)鏈表，其結(jié)構(gòu)可以由下圖表示：

其中，鏈表的第一個結(jié)點稱為哨兵位頭結(jié)點，此結(jié)點的不用于存儲數(shù)據(jù)，只是利用建立其他結(jié)點的關系。因此，在編寫針對于鏈表單元結(jié)構(gòu)的構(gòu)造函數(shù)時，需要考慮到哨兵位頭結(jié)點。本文將采用隱式類型轉(zhuǎn)換的方式，來完成對于構(gòu)造函數(shù)的編寫：

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

對于一個帶頭雙向循環(huán)鏈表結(jié)構(gòu)的實現(xiàn)，可以看作是若干個結(jié)構(gòu)單元的相互鏈接，因此在初始化鏈表結(jié)構(gòu)時，只需要在構(gòu)造函數(shù)中，完成對于哨兵位頭結(jié)點的建立，以及其內(nèi)部指針的指向即可，即：

具體的實現(xiàn)方法，就是再創(chuàng)建一個類，名為的類，將上述表示單個結(jié)點結(jié)構(gòu)的類作為一種類型引入到，即：

template<class T>class list{typedef ListNode<T>  Node;Node* _node;};

通過上述給出的圖片，可以得到下面的構(gòu)造函數(shù)：

class list{typedef ListNode<T>  Node;public:list(){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}Node* _phead;};

2. list功能實現(xiàn)：尾部插入元素：

在插入一個元素之前，首先需要創(chuàng)建一個新的結(jié)構(gòu)單元用于保存這個元素，例如需要插入的元素為，需要提前創(chuàng)建一個名為的結(jié)點用于存儲該元素，即：

Node* newnode = new Node(x);

當進行插入時，即：

第一步，首先獲取鏈表最后一個結(jié)點的地址，這里命名為，通過上圖不難得出.

第二步，建立與的聯(lián)系，即：,，對于此關系的圖片表示是如下：

?最后一步：建立與的聯(lián)系，即,

代碼實現(xiàn)如下：

void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _phead->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _phead;_phead->_prev = newnode;}

3. list迭代器的實現(xiàn)：

? ? ? ?在中，由于這兩種數(shù)據(jù)結(jié)構(gòu)的空間是連續(xù)的，因此，在實現(xiàn)其迭代器功能時，通常先利用對指針進行更名，使用時直接即可。

? ? ? 但是對于，前面說到的結(jié)構(gòu)可以近似的看為鏈表，由于鏈表的空間不連續(xù)，因此，在使用迭代器進行訪問時，對迭代器不能達成訪問空間中下一個結(jié)點的目的。對于來說，正確訪問下一個結(jié)點的訪問為通過本結(jié)點的獲取下一個結(jié)點的地址。因此，可以考慮使用運算符重載，將的運行邏輯從指向連續(xù)空間的下一個地址改為通過本結(jié)點的訪問下一個結(jié)點。

? ? ?但是，運算符重載只能針對于自定義類型，因為迭代器的實現(xiàn)是依托于指針來完成的。雖然在前面利用創(chuàng)建自定義類型的方式創(chuàng)建了鏈表中單個結(jié)點結(jié)構(gòu)的對象，但是，需要注意，此處運算符重載進行重載的目標并不是這個自定義類型，而是這個類型的指針，而指針是一個內(nèi)置類型，因此，不能直接完成對于指針的重載。而是再創(chuàng)建一個自定義類型用于封裝指針，在內(nèi)部進行運算符重載。

? ? 對于封裝方法：首先需要將表示單個結(jié)點結(jié)構(gòu)的自定義類型引入到新的類中，此處將這個類命名為___。為了方便使用，將表示單個結(jié)點結(jié)構(gòu)的類重命名為，成員變量為類型為的指針。即：

template<class T>struct __list_iterator{typedef ListNode<T> Node;Node* _node;};

對于上述類的初始化如下：

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

為了正常的使用迭代器來完成對于的打印，不但需要對于，還需要對于和進行重載，代碼如下：

template<class T>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T> self;__list_iterator(Node* node): _node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(_node);_node = _node->next;return tmp;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return _node != s._node;}Node* _node;};

? ? ? ?在完成上述步驟后，向中引入___，再添加兩個函數(shù)用于表示鏈表的起始和結(jié)束。

? ? ? ?需要注意的是，在定義鏈表的起始時，并不能定義成哨兵位頭結(jié)點，因為哨兵位頭結(jié)點并沒有保存數(shù)據(jù)，在訪問鏈表時，需要從第一個保存數(shù)據(jù)的結(jié)點開始訪問。而對于尾結(jié)點，由于鏈表是雙向循環(huán)的。因此，可以將不存儲任意數(shù)據(jù)的哨兵位頭結(jié)點看作尾結(jié)點，代碼如下：

typedef __list_iterator<T> iterator;iterator begin(){return _phead->_next;}iterator end(){return _phead;}

在完成了上述步驟后，就可以使用迭代器對于進行正常的訪問，例如：

void test1(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);list<int>::iterator it1 = It.begin();while (it1 != It.end()){cout << *it1 << ' ';++it1;}}

代碼運行結(jié)果如下：

4. list功能實現(xiàn)：在任意位置前插入元素：?

4.1 函數(shù)實現(xiàn)方法：

與尾部插入元素的大致思路相同，首先需要創(chuàng)建一個結(jié)點來存儲這個元素：

Node* newnode = new Node(x);

例如，需要在位置之前插入這個結(jié)點，首先需要獲取位置的前一個結(jié)點的地址。但是，只是類型為的一個對象，需要先創(chuàng)建一個變量，來存儲中成員變量，也就是這個結(jié)點的地址，通過來獲取位置前一個結(jié)點的坐標，即：

Node* cur = pos._node;

Node* prev = cur->_prev;

在對?這三個位置所代表的結(jié)點進行連接，即：

void 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;newnode->_next = cur;cur->_prev = newnode;}

利用下方的代碼對于函數(shù)功能進行測試，即：

It.insert(It.begin(), 5);It.insert(It.begin(), 6);It.insert(It.begin(), 7);It.insert(It.begin(), 8);for (auto e : It){cout << e << ' ';}

運行結(jié)果如下：

4.2 函數(shù)運行邏輯：

為了更清晰的了解的動作邏輯，下面給出函數(shù)的整體運行步驟，例如對于下方的代碼：

It.insert(It.begin(), 5);

函數(shù)運行的第一步為首先通過函數(shù)獲取地址：

在返回時，由于函數(shù)的返回類型為自定義類型，因此在返回前會去調(diào)用___中的構(gòu)造函數(shù)，來構(gòu)造一個臨時變量作為返回值，即：

再獲取返回值后，跳轉(zhuǎn)到函數(shù)中，即：

?最后根據(jù)中編寫好的代碼的順序進行運行。

在完成了對于函數(shù)的編寫后，對于_函數(shù)可以復用，從而簡化_，即：

void push_back(const T& x){insert(_phead, x);}

同理也可以實現(xiàn)頭部插入任意元素_，即：

void push_front(const T& x){insert(_phead->_next, x);}

5. list功能實現(xiàn)：刪除任意位置的結(jié)點：

在刪除任意位置的結(jié)點前，首先需要找到這個結(jié)點的前結(jié)點和后結(jié)點的地址，為了方便表達，用表示前結(jié)點的地址，用表示后結(jié)點的地址。代碼如下：

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

在完成了對于的編寫后，可以通過復用來完成對于頭部刪除_和尾部刪除_，代碼如下：

void pop_back(){erase(_phead->_prev);}void pop_front(){erase(_phead->_next);}

利用下方代碼對上述的函數(shù)進行測試：
?

It.pop_back();It.pop_back();It.pop_front();It.pop_front();for (auto e : It){cout << e << ' ';}

運行結(jié)果如下：

6. 拷貝構(gòu)造與賦值重載：

list(const list<T>& s){empty();for (auto e : s){push_back(e);}}void swap(list<T>& s){std::swap(_phead, s._phead);}list<T>& operator=(list<T> s){swap(s);return *this;}

7. list功能實現(xiàn)：clear與析構(gòu)函數(shù)：

對于函數(shù)，其功能是用于清理空間中的所有內(nèi)容，即所有開辟的結(jié)點，但是不包括哨兵位頭結(jié)點。

對于析構(gòu)函數(shù)，則是在函數(shù)的基礎上，將哨兵位頭結(jié)點也進行處理。

二者對應代碼如下：

void clear(){iterator i2 = begin();while (i2 != end()){i2 = erase(i2);}}~list(){clear();delete _phead;phead = nullptr;}

?