---

前言

在C++ STL中，list是一個非常常用的容器，它基于雙向循環鏈表實現，具有高效的插入和刪除操作。本文將詳細介紹如何模擬實現一個簡易版的STL list容器，包括節點結構、迭代器設計以及list類的核心功能實現。

---

一、list的節點結構設計

list的底層是雙向循環鏈表，因此首先需要設計鏈表的節點結構。每個節點應包含數據域和兩個指針域（前驅和后繼）：

template<class T>
struct ListNode
{typedef ListNode<T> Node;ListNode(const T& val = T());~ListNode();Node* _next;  // 指向后繼節點Node* _prev;  // 指向前驅節點T _val;       // 節點存儲的數據
};template<class T>
ListNode<T>::ListNode(const T& val):_next(nullptr), _prev(nullptr), _val(val)
{}template<class T>
ListNode<T>::~ListNode()
{_next = nullptr;_prev = nullptr;_val = T();
}

---

二、迭代器設計

list的迭代器與vector不同，它不能是簡單的指針，因為list的節點在內存中不是連續存儲的。我們需要設計一個迭代器類，通過重載運算符來模擬指針的行為。

template<class T, class value_type>
struct ListIterator
{typedef ListNode<T> Node;Node* _node;  // 指向當前節點ListIterator(Node* node = nullptr);// 重載各種運算符ListIterator<T, value_type>& operator=(const ListIterator<T, value_type>& it);ListIterator<T, value_type>& operator++();       // 前置++ListIterator<T, value_type> operator++(int);     // 后置++ListIterator<T, value_type>& operator--();       // 前置--ListIterator<T, value_type> operator--(int);     // 后置--value_type& operator*();                         // 解引用value_type* operator->();                        // 箭頭運算符bool operator==(const ListIterator<T, value_type>& it);bool operator!=(const ListIterator<T, value_type>& it);
};

迭代器的核心運算符實現：

// 前置++
template<class T, class value_type>
ListIterator<T, value_type>& ListIterator<T, value_type>::operator++()
{_node = _node->_next;return *this;
}// 后置++
template<class T, class value_type>
ListIterator<T, value_type> ListIterator<T, value_type>::operator++(int)
{ListIterator<T, value_type> tmp = *this;_node = _node->_next;return tmp;
}// 解引用運算符
template<class T, class value_type>
value_type& ListIterator<T, value_type>::operator*()
{return _node->_val;
}// 箭頭運算符
template<class T, class value_type>
value_type* ListIterator<T, value_type>::operator->()
{return &(_node->_val);
}

---

三、list類的實現

list類需要維護一個雙向循環鏈表，我們使用一個頭節點（哨兵節點）來簡化邊界條件的處理。

---

3.1 類的成員變量和類型定義

template<class T>
class list
{
public:typedef ListNode<T> Node;// 定義迭代器類型，普通迭代器和const迭代器typedef ListIterator<T, T> iterator;typedef ListIterator<T, const T> const_iterator;// ... 成員函數聲明
private:Node* _head;  // 頭節點（哨兵節點）
};

---

3.2 構造函數與析構函數

// 默認構造函數
template<class T>
list<T>::list()
{_head = new Node;_head->_next = _head;  // 循環指向自身_head->_prev = _head;
}// 范圍構造函數
template<class T>
template <class InputIterator>
list<T>::list(InputIterator first, InputIterator last)
{_head = new Node;_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);first++;}
}// 析構函數
template<class T>
list<T>::~list()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}delete _head;_head = nullptr;
}

---

3.3 元素訪問與迭代器接口

// 迭代器接口
template<class T>
typename list<T>::iterator list<T>::begin()
{return iterator(_head->_next);  // 第一個元素是頭節點的下一個
}template<class T>
typename list<T>::iterator list<T>::end()
{return iterator(_head);  // 尾后迭代器指向頭節點
}// 元素訪問
template<class T>
T& list<T>::front()
{assert(!empty());return _head->_next->_val;  // 第一個元素
}template<class T>
T& list<T>::back()
{assert(!empty());return _head->_prev->_val;  // 最后一個元素
}

---

3.4 插入與刪除操作

list的插入和刪除操作是其核心優勢，時間復雜度為O(1)：

// 頭插
template<class T>
void list<T>::push_front(const T& val)
{Node* new_node = new Node(val);// 插入到頭節點和第一個元素之間new_node->_prev = _head;new_node->_next = _head->_next;_head->_next->_prev = new_node;_head->_next = new_node;
}// 尾插
template<class T>
void list<T>::push_back(const T& val)
{Node* new_node = new Node(val);// 插入到最后一個元素和頭節點之間new_node->_prev = _head->_prev;new_node->_next = _head;_head->_prev->_next = new_node;_head->_prev = new_node;
}// 指定位置插入
template<class T>
typename list<T>::iterator list<T>::insert(iterator position, const T& val)
{Node* new_node = new Node(val);// 插入到position之前new_node->_prev = position._node->_prev;new_node->_next = position._node;position._node->_prev->_next = new_node;position._node->_prev = new_node;return iterator(new_node);  // 返回指向新節點的迭代器
}// 指定位置刪除
template<class T>
typename list<T>::iterator list<T>::erase(iterator position)
{// 調整前后節點的指針關系position._node->_prev->_next = position._node->_next;position._node->_next->_prev = position._node->_prev;iterator ret = position._node->_next;  // 記錄下一個位置delete position._node;  // 釋放節點內存return ret;  // 返回下一個位置的迭代器
}

---

3.5 其他常用操作

// 清空鏈表
template<class T>
void list<T>::clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}// 恢復頭節點的循環指向_head->_prev = _head;_head->_next = _head;
}// 反轉鏈表
template<class T>
void list<T>::reverse()
{Node* cur = _head->_next;while (cur != _head){Node* tmp = cur->_next;std::swap(cur->_prev, cur->_next);  // 交換前后指針cur = tmp;}// 交換頭節點的前后指針std::swap(_head->_prev, _head->_next);
}// 移除所有值為val的元素
template<class T>
void list<T>::remove(const T& val)
{iterator cur = begin();while (cur != end()){if (*cur == val){cur = erase(cur);  // 刪除后自動移動到下一個元素}else{++cur;}}
}

---

四、總結

本文實現了一個簡易版的STL list容器，包含了list的核心功能：

1. 基于雙向循環鏈表，使用哨兵節點簡化邊界處理
2. 實現了功能完善的迭代器，支持++、–、*、->等操作
3. 提供了插入、刪除、反轉、移除等常用操作

與vector相比，list的優勢在于插入和刪除操作的高效性（O(1)時間復雜度），但隨機訪問性能較差（O(n)時間復雜度）。在實際開發中，應根據具體需求選擇合適的容器。

完整代碼實現了更多細節，如拷貝構造、賦值運算、區間插入、splice操作等，感興趣的讀者可以參考代碼進行深入學習。

如需源碼，可在我的gitee上找到，下面是鏈接：
list
如對您有所幫助，可以來個三連，感謝大家的支持。

---

每文推薦

陳粒–小半
范瑋琪、張韶涵–如果的事
孫燕姿–克卜勒

學技術學累了時可以聽歌放松一下。

---