在 C++ 標準模板庫(STL)中，list 是一個非常重要的序列容器，它實現了雙向鏈表的數據結構。與 vector 和 deque 不同，list 提供了高效的插入和刪除操作，特別是在任意位置。本文將深入探討 list 容器的特性、使用方法以及常見操作。
文章目錄
- 一、list 容器的基本特性
- 二、list 的基本操作
- 2.1 list的語法
- 2.2 常用成員函數
- 2.3 插入和刪除操作
- 三、list 的高級特性
- 3.1 迭代器使用
- 3.2 排序和去重
- 3.3 合并和拼接
- 四、list對比其它容器的優劣勢
- 4.1優勢
- 4.2劣勢
一、list 容器的基本特性
list 是一個雙向鏈表容器，它有下面5個特點：
-
雙向鏈表結構：每個元素都包含指向前驅和后繼的指針。
-
非連續內存：元素存儲在任意內存位置，通過指針連接。
-
高效的插入刪除：在任意位置插入和刪除元素的時間復雜度為 O(1)。
-
不支持隨機訪問：不能像數組一樣通過下標直接訪問元素。
-
迭代器穩定性：插入和刪除操作不會使迭代器失效（除了被刪除元素的迭代器）。
二、list 的基本操作
2.1 list的語法
- 使用 list 前需要包含 頭文件：
#include <iostream>
#include <list>
using namespace std;- 初始化一個空的 list
list<int> lst1;
- 初始化包含 5 個元素，每個元素值為 10
list<int> lst2(5, 10);- 通過初始化列表初始化
list<int> lst3 = {1, 2, 3, 4, 5};
- 通過數組初始化
int arr[] = {6, 7, 8, 9, 10};list<int> lst4(arr, arr + sizeof(arr)/sizeof(arr[0]));
2.2 常用成員函數
定義一個list作為示例，將為大家演示一些常用的成員函數及其使用方法。
list<int> myList = {1, 2, 3};
- 在末尾添加元素
myList.push_back(4); // 1,2,3,4
- 在開頭添加元素
myList.push_front(0); // 0,1,2,3,4
- 獲取第一個和最后一個元素
cout << "Front: " << myList.front() << endl; // 0
cout << "Back: " << myList.back() << endl; // 4
- 刪除第一個和最后一個元素
myList.pop_front(); // 1,2,3,4
myList.pop_back(); // 1,2,3
- 判斷 list 是否為空
if (!myList.empty()) {cout << "List size: " << myList.size() << endl; // 3
}
2.3 插入和刪除操作
list 的插入和刪除操作非常高效，定義一個list作為示例：
list<int> nums = {10, 20, 30, 40};
- 在指定位置前插入元素
auto it = nums.begin();
advance(it, 2); // 移動到第3個元素位置
nums.insert(it, 25); // 10,20,25,30,40
- 刪除指定位置的元素
it = nums.begin();
advance(it, 3);
nums.erase(it); // 10,20,25,40
- 刪除所有值為20的元素
nums.remove(20); // 10,25,40
- 刪除滿足條件的元素
nums.remove_if([](int n){ return n > 30; }); // 10,25
三、list 的高級特性
3.1 迭代器使用
由于 list 不支持隨機訪問，遍歷時必須使用迭代器。
我在這里定義一個string類型的list作為演示遍歷時的操作。（其實主要還是迭代器遍歷，但是范圍for也可以。其實范圍for內核本質就是迭代器啦）
list<string> names = {"Alice", "Bob", "Charlie"};
- 使用迭代器遍歷
for (auto it = names.begin(); it != names.end(); ++it) {cout << *it << " ";
}
cout << endl;
- 使用范圍for循環遍歷
for (const auto& name : names) {cout << name << " ";
}
cout << endl;
3.2 排序和去重
list 中，庫提供了專門的排序和去重成員函數，下面我創建一個int類型的list為大家一一演示其使用方法：
list<int> values = {3, 1, 4, 1, 5, 9, 2, 6};
- 排序 (升序)
values.sort(); // 1,1,2,3,4,5,6,9
- 降序排序
values.sort(greater<int>()); // 9,6,5,4,3,2,1,1
- 去重 (必須先排序)
values.unique(); // 9,6,5,4,3,2,1
- 自定義去重條件
values.unique([](int a, int b){ return abs(a-b) <= 1; });
3.3 合并和拼接
list 在合并和拼接提供了十分方便并且高效的庫函數：
- 定義兩個list鏈表作為演示
list<int> list1 = {1, 3, 5};
list<int> list2 = {2, 4, 6};
- 合并兩個有序list (list2會被清空)
list1.merge(list2); // list1: 1,2,3,4,5,6; list2: 空list<int> list3 = {7, 8, 9};
- 拼接list (將list3的元素移動到list1的指定位置)
auto pos = list1.begin();
advance(pos, 3);
list1.splice(pos, list3); // list1: 1,2,3,7,8,9,4,5,6
下次我們寫算法題就可以不用像C語言那樣那么麻煩了…（手動狗頭）
四、list對比其它容器的優劣勢
4.1優勢
-
適合頻繁插入刪除：當需要在序列中間頻繁插入刪除元素時，list 是最佳選擇
-
適合大元素對象：當元素對象很大時，list 可能比 vector 更高效，因為不需要重新分配和復制
-
不需要隨機訪問：如果不需要通過下標快速訪問元素
-
迭代器穩定性高：需要保證插入刪除操作不影響其他元素的迭代器
4.2劣勢
-
- 內存開銷大
- list 作為鏈表結構，每個元素都需要額外的指針空間來存儲前驅和后繼節點的地址：
- 內存開銷大
struct ListNode {T data; // 存儲的實際數據ListNode* prev; // 指向前驅節點的指針ListNode* next; // 指向后繼節點的指針
};
-
- 緩存不友好
-
鏈表節點分散在內存各處，無法利用空間局部性。
-
遍歷鏈表時幾乎每次訪問都會導致緩存缺失。
-
CPU 難以預測下一個節點的內存位置。
