C++：list(2)list的模擬實現

list的模擬實現

一.list與vector
- - 1.底層結構的本質區別
  - 2.模擬實現的核心差異
  - - 2.1數據存儲的方式
    - 2.2 初始化的過程
    - 2.3 插入元素的操作
    - 2.4 刪除元素的操作
    - 2.5 訪問元素的效率
  - 3.總結
二.頭文件list.h
- - 1. **命名空間與模板**
  - 2. **核心數據結構**
  - 3. **構造函數**
  - 4. **模板參數設計**
  - 5. **核心成員**
  - 6. **構造與析構**
  - 7. **操作符重載**
  - 8. **類型定義**
  - 9. **迭代器接口**
  - 10. **內存管理**
  - 11. **構造函數**
  - 12. **初始化列表構造函數**
  - 13. **交換方法**
  - 14. **賦值運算符重載**
  - 15. **鏈表初始化**
  - 16. **清空操作**
  - 17. **首尾操作**
  - 18. **插入操作**
  - 19. **刪除操作**
三.頭文件test.cpp
- - 1. **打印函數**
  - 2. **測試函數1**
  - 3. **測試函數3：迭代器操作測試**
  - 4. **測試函數4：插入刪除測試**

一.list與vector

順序表與鏈表因底層結構不同而導致的模擬實現差異。

1.底層結構的本質區別

順序表：像一排連續的“格子”，所有元素按順序依次放進這些格子里，每個格子緊挨著下一個，中間沒有空隙。整個結構占用一整塊連續的內存空間，元素的位置（比如第1個、第2個）和它們在內存中的物理位置完全對應。
鏈表：像一串“珠子”，每個珠子（稱為“節點”）分為兩部分：一部分裝數據，另一部分裝一個“指向”下一個珠子的“鉤子”（指針或引用）。這些珠子在內存中可能分散在不同位置，全靠鉤子串聯起來形成邏輯上的順序，物理位置和邏輯位置無關。

2.模擬實現的核心差異

基于上述底層結構，兩者的實現邏輯（比如怎么存數據、怎么加元素、怎么刪元素）完全不同：

2.1數據存儲的方式

順序表：
實現時需要先劃定一塊固定大小的連續空間（比如先準備10個格子），用一個“容器”管理這些格子，同時記錄當前裝了多少元素（比如已用3個格子）和總共能裝多少（10個）。元素的位置可以直接算出來：第i個元素一定在第1個元素往后數i個格子的位置，所以能直接找到。
鏈表：
實現時不需要預先劃定空間，而是用一個“頭指針”記錄第一個節點的位置，每個節點都是單獨創建的（需要時才申請內存）。每個節點除了數據，必須帶一個“鉤子”指向后面的節點，最后一個節點的鉤子指向“空”，表示結束。元素的位置無法直接算，只能從第一個節點開始，順著鉤子一個個找。

2.2 初始化的過程

順序表：
核心是“圈定初始空間”。比如一開始決定能裝5個元素，就申請一塊能放下5個元素的連續內存，然后標記“當前裝了0個元素”。如果后續元素超過5個，就需要“擴容”——重新申請一塊更大的連續內存（比如能裝10個），把原來的元素搬過去，再用新空間替代舊空間。
鏈表：
核心是“確定起點”。通常初始化時，要么讓頭指針指向“空”（表示鏈表為空），要么先創建一個“哨兵節點”（不存數據，專門用來統一操作），頭指針指向這個哨兵節點，同時標記“當前有0個元素”。后續添加元素時，再一個個創建新節點，用鉤子連起來即可，不需要提前規劃總容量。

2.3 插入元素的操作

順序表：
如果要在第i個位置插入元素，必須先檢查當前空間是否夠用（不夠就擴容），然后把第i個及之后的所有元素都往后“挪一個位置”（騰出第i個格子），最后把新元素放進第i個格子，再更新“已用元素數”。
比如在“[1,2,3]”的第2個位置插4，需要先把2、3往后挪，變成“[1, ,2,3]”，再放4，結果是“[1,4,2,3]”。
鏈表：
如果要在第i個位置插入元素，不需要挪動其他元素，只需要：
1. 新建一個節點，存入數據；
2. 找到第i-1個節點，把它的鉤子從原來指向第i個節點，改成指向新節點；
3. 再讓新節點的鉤子指向原來的第i個節點。
  比如在“1→2→3”的2前面插4，只需要讓1的鉤子指向4，4的鉤子指向2，就變成“1→4→2→3”，其他節點不需要動。

2.4 刪除元素的操作

順序表：
如果要刪除第i個元素，需要先把第i個元素去掉，然后把第i+1個及之后的所有元素往前“挪一個位置”（填補空缺），最后更新“已用元素數”。
比如刪除“[1,2,3,4]”的第2個元素（2），需要把3、4往前挪，變成“[1,3,4]”，中間不能留空隙（否則不符合連續空間的特性）。
鏈表：
如果要刪除第i個元素，只需要找到第i-1個節點，把它的鉤子從原來指向第i個節點，改成指向第i+1個節點，然后把第i個節點的內存釋放掉即可。
比如刪除“1→4→2→3”中的4，只需要讓1的鉤子直接指向2，4就被“摘”下來了，其他節點位置不變。

2.5 訪問元素的效率

順序表：
因為元素位置能直接計算（第i個元素的位置 = 起點 + i×元素大小），所以訪問任意位置的元素時，一步就能找到，效率很高（時間復雜度O(1)）。
鏈表：
因為元素位置靠鉤子串聯，訪問第i個元素時，必須從第一個節點開始，順著鉤子一個個數到第i個，效率較低（時間復雜度O(n)）。

3.總結

順序表的底層是“連續內存”，決定了它的實現依賴“空間預分配+位置計算”，操作時需要挪動元素但訪問快；
鏈表的底層是“離散節點+指針”，決定了它的實現依賴“動態創建+指針串聯”，操作時無需挪動元素但訪問慢。
這種底層結構的差異，是兩者實現方式和性能特性的根本原因。

二.頭文件list.h

#pragma once
#include<iostream>
using namespace std;namespace yl
{//定義單個結點結構template<typename T>struct _list_node{_list_node<T>* _prev;_list_node<T>* _next;T _data;_list_node(const T& x):_data(x), _prev(nullptr), _next(nullptr){}};

1. 命名空間與模板

代碼位于yl命名空間內，避免命名沖突
使用模板template<typename T>實現泛型，支持任意數據類型

2. 核心數據結構

_list_node結構體表示鏈表的節點
包含三個成員變量：
- _prev：指向前驅節點的指針
- _next：指向后繼節點的指針
- _data：存儲節點數據的模板類型變量

3. 構造函數

帶參數的構造函數_list_node(const T& x)
初始化節點數據_data為傳入值
將_prev和_next指針初始化為nullptr

設計特點

雙向鏈表結構，支持雙向遍歷
節點獨立管理前后連接關系
模板設計保證了良好的擴展性

 // 鏈表迭代器模板// T: 數據類型，Ref: 引用類型，Ptr: 指針類型template<typename T, class Ref, class Ptr>struct _list_iterator{typedef _list_iterator<T, Ref, Ptr> Self;  // 自身類型別名typedef _list_node<T> Node;               // 節點類型別名Node* _node;                              // 指向當前節點的指針// 構造函數：用節點指針初始化迭代器_list_iterator(Node* node) : _node(node) {}// 解引用操作符：返回節點數據的引用Ref operator*() { return _node->_data; }// 箭頭操作符：返回節點數據的指針Ptr operator->() { return &_node->_data; }// const版本箭頭操作符：用于常量迭代器Ptr operator->() const { 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) const {return it._node != this->_node;}// 析構函數：迭代器不擁有節點內存，無需釋放~_list_iterator() {}};

以上這段代碼實現了雙向鏈表的迭代器

4. 模板參數設計

三個模板參數：T（數據類型）、Ref（引用類型）、Ptr（指針類型）
通過分離引用和指針類型，支持普通迭代器和常量迭代器

5. 核心成員

Node* _node：指向當前節點的指針
類型別名：Self（自身類型）和Node（節點類型）

6. 構造與析構

構造函數：接收節點指針初始化迭代器
析構函數：空實現（迭代器不負責內存管理）

7. 操作符重載

解引用操作符*：返回節點數據引用
箭頭操作符->：返回節點數據指針（含const版本）
自增操作符++：前置和后置版本（支持雙向移動）
自減操作符--：前置和后置版本（支持雙向移動）
不等比較!=：比較節點指針是否相等

迭代器特性

雙向迭代器：支持前后移動
符合STL迭代器規范（實現必要操作符）
輕量級設計：僅包含一個指針成員

內存管理

迭代器不擁有節點內存
節點生命周期由鏈表容器管理

template<typename T>class list {public:typedef _list_node<T> Node;             // 鏈表節點類型typedef _list_iterator<T, T&, T*> iterator;         // 普通迭代器typedef _list_iterator<T, const T&, const T*> const_iterator; // 常量迭代器// 返回指向第一個元素的迭代器iterator begin() { return _head->_next; }// 返回指向尾后位置的迭代器iterator end() { return _head; }// 常量版本的begin()和end()const_iterator begin() const { return const_iterator(_head->_next); }const_iterator end() const { return const_iterator(_head); }// 默認構造函數list() { empty_init(); }// 析構函數：釋放鏈表內存~list() {clear();        // 清空所有數據節點delete _head;   // 釋放頭節點}// 拷貝構造函數list(const list<T>& lt) {empty_init();           // 初始化空鏈表for (auto& e : lt) {    // 逐個復制元素push_back(e);}}

這段代碼實現了雙向鏈表的容器類，下面是重點內容概括：

8. 類型定義

嵌套類型定義：Node（節點類型）
迭代器類型：
- iterator：普通迭代器（引用類型T&，指針類型T*）
- const_iterator：常量迭代器（引用類型const T&，指針類型const T*）

9. 迭代器接口

begin()：返回指向第一個元素的迭代器
end()：返回指向尾后位置的迭代器
提供常量版本，支持常量對象遍歷

10. 內存管理

哨兵節點（頭節點_head）設計：
- 空鏈表時_head->_next == _head
- 簡化邊界條件處理
析構函數：
- 調用clear()釋放所有數據節點
- 釋放頭節點內存

11. 構造函數

默認構造函數：調用empty_init()初始化空鏈表
拷貝構造函數：
- 初始化空鏈表
- 通過范圍for循環逐個復制元素

. 關鍵方法

empty_init()：初始化頭節點，構建循環鏈表
clear()：清空所有數據節點但保留頭節點

        // 初始化列表構造函數list(initializer_list<T> il) {empty_init();           // 初始化空鏈表for (auto& e : il) {    // 使用初始化列表中的元素填充鏈表push_back(e);}}// 交換兩個鏈表的內容void swap(list<T> lt) {std::swap(_head, lt._head);     // 交換頭節點指針std::swap(_size, lt._size);     // 交換元素數量}// 賦值運算符重載list<T>& operator=(const list<T> il) {swap(il);         // 通過交換實現拷貝賦值return *this;}// 初始化空鏈表void empty_init() {_head = new Node(T());       // 創建頭節點，初始化為T的默認值_head->_next = _head;        // 頭節點的next指向自身_head->_prev = _head;        // 頭節點的prev指向自身_size = 0;                   // 鏈表大小初始化為0}// 清空鏈表但保留頭節點void clear() {iterator it = begin();while (it != end()) {        // 遍歷所有數據節點it = erase(it);          // 刪除當前節點并獲取下一個節點}}

以上cpp代碼繼續完善了雙向鏈表容器類，新增了初始化列表構造、賦值運算符等功能：

12. 初始化列表構造函數

支持list<int> lst = {1, 2, 3}語法
調用empty_init()初始化頭節點
通過范圍for循環和push_back()逐個添加元素

13. 交換方法

swap(list<T> lt)：交換兩個鏈表的內容
直接交換頭節點指針和元素數量
時間復雜度O(1)

14. 賦值運算符重載

采用拷貝并交換(Copy-and-swap)慣用法
通過值傳遞接收參數，自動處理自我賦值問題
高效釋放原有資源并獲取新資源

15. 鏈表初始化

empty_init()：
- 創建頭節點，初始化為T()
- 構建循環鏈表結構(_head的prev和next指向自身)
- 初始化_size為0

16. 清空操作

clear()：
- 使用迭代器遍歷所有數據節點
- 調用erase(it)刪除節點并更新迭代器
- 保留頭節點，保持鏈表結構完整性

// 在鏈表頭部插入元素void push_front(const T& x) { insert(begin(), x); }// 在鏈表尾部插入元素void push_back(const T& x) { insert(end(), x); }// 刪除鏈表尾部元素void pop_back() { erase(--end()); }// 刪除鏈表頭部元素void pop_front() { erase(begin()); }// 在指定位置前插入元素，返回新節點的迭代器iterator insert(iterator pos, const T& x) {Node* cur = pos._node;              // 當前位置的節點Node* newnode = new Node(x);        // 創建新節點Node* prev = cur->_prev;            // 當前位置的前一個節點// 調整指針連接新節點prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;_size++;                            // 更新鏈表大小return iterator(newnode);           // 返回指向新節點的迭代器}// 刪除指定位置的節點，返回下一個位置的迭代器iterator erase(iterator pos) {Node* cur = pos._node;              // 當前位置的節點Node* prev = cur->_prev;            // 前一個節點Node* next = cur->_next;            // 下一個節點// 調整指針跳過當前節點prev->_next = next;next->_prev = prev;delete cur;                         // 釋放當前節點內存_size--;                            // 更新鏈表大小return iterator(next);              // 返回下一個位置的迭代器}private:Node* _head;           // 頭節點指針（哨兵節點）size_t _size = 0;      // 鏈表元素數量};
}

以上代碼完善了雙向鏈表的核心操作接口：

17. 首尾操作

push_front/push_back：通過insert在首尾插入元素
pop_front/pop_back：通過erase刪除首尾元素
時間復雜度均為O(1)

18. 插入操作

insert(iterator pos, const T& x)：
- 在pos前插入新節點
- 調整四個指針完成插入
- 返回指向新節點的迭代器
保持迭代器有效性（除被插入位置外）

19. 刪除操作

erase(iterator pos)：
- 刪除pos指向的節點
- 調整兩個指針跳過待刪節點
- 釋放節點內存并返回下一位置迭代器
注意：刪除后原迭代器失效

指針調整邏輯

插入時需修改四個指針：前驅節點的next、新節點的prev/next、后繼節點的prev
刪除時需修改兩個指針：前驅節點的next、后繼節點的prev
頭節點參與循環鏈表維護

數據成員

Node* _head：哨兵節點，構成循環鏈表
size_t _size：記錄元素數量，插入/刪除時維護

三.頭文件test.cpp

#include"list.h"// 打印鏈表內容的模板函數
template<class T>
void print(const yl::list<T>& lt) {auto it = lt.begin();while (it != lt.end()) {cout << *it << " ";++it;}cout << endl;
}// 測試函數1：測試基本功能
void test01() {yl::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);print(lt1);
}// 測試函數2：測試拷貝構造和初始化列表
void test02() {yl::list<int> lt1 = { 0, 1, 2, 3, 4, 5 };yl::list<int> lt2 = lt1;print(lt2);
}

1. 打印函數

模板函數print(const yl::list<T>& lt)
使用迭代器遍歷鏈表并輸出元素
支持任意可輸出類型（需重載operator<<）

2. 測試函數1

功能：測試基本插入操作
步驟：
1. 創建空鏈表lt1
2. 尾插5個元素（1-5）
3. 打印鏈表（預期輸出：1 2 3 4 5）
驗證點：
- push_back功能
- 迭代器遍歷正確性

測試函數2
- 功能：測試初始化列表和拷貝構造
- 步驟：
  1. 使用初始化列表構造lt1（元素0-5）
  2. 通過拷貝構造創建lt2
  3. 打印lt2（預期輸出：0 1 2 3 4 5）
- 驗證點：
  - 初始化列表構造函數
  - 拷貝構造函數（深拷貝）

// 測試函數3：測試迭代器操作
void test03() {yl::list<int> lt;lt.push_back(10);lt.push_back(20);lt.push_back(30);cout << "測試前置++: ";auto it = lt.begin();++it;cout << *it << endl;cout << "測試后置++: ";it = lt.begin();it++;cout << *it << endl;cout << "測試前置--: ";it = lt.end();--it;cout << *it << endl;cout << "測試后置--: ";it = lt.end();it--;cout << *it << endl;
}// 測試函數4：測試插入和刪除操作
void test04() {yl::list<int> lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);auto it = lt.begin();++it;lt.insert(it, 2);cout << "插入后: ";print(lt);it = lt.begin();++it;lt.erase(it);cout << "刪除后: ";print(lt);
}int main() {cout << "=== 測試基本功能 ===" << endl;test01();cout << "\n=== 測試拷貝構造和初始化列表 ===" << endl;test02();cout << "\n=== 測試迭代器操作 ===" << endl;test03();cout << "\n=== 測試插入和刪除操作 ===" << endl;test04();return 0;
}

這段代碼新增了迭代器操作和插入刪除功能的測試，以下是重點內容概括：

3. 測試函數3：迭代器操作測試

功能：驗證迭代器自增自減操作
步驟：
1. 創建鏈表lt并插入元素10, 20, 30
2. 測試前置++：移動到第二個元素（輸出20）
3. 測試后置++：移動到第二個元素（輸出20）
4. 測試前置--：從end()移動到最后一個元素（輸出30）
5. 測試后置--：從end()移動到最后一個元素（輸出30）
驗證點：
- 雙向迭代器的移動正確性
- 前置/后置操作符的語義差異

4. 測試函數4：插入刪除測試

功能：驗證插入刪除接口
步驟：
1. 創建鏈表lt并插入元素1, 3, 4
2. 在第二個位置插入2（鏈表變為1, 2, 3, 4）
3. 刪除第二個位置元素（鏈表變為1, 3, 4）
驗證點：
- insert在指定位置前插入元素
- erase正確刪除元素并返回下一位置迭代器