C++中l(wèi)ist實現(xiàn)雙向循環(huán)鏈表詳細解析
更新時間：2026年01月15日 10:57:08 作者：yuuki233233
雙向循環(huán)鏈表是一種重要的線性數(shù)據(jù)結(jié)構(gòu),支持前后雙向遍歷,適用于頻繁插入刪除和高效訪問的場景,這篇文章主要介紹了C++中l(wèi)ist實現(xiàn)雙向循環(huán)鏈表詳細解析的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
前言
在上一篇中，我們吃透了 vector 的底層實現(xiàn) —— 作為動態(tài)連續(xù)數(shù)組，它憑借 “隨機訪問” 的優(yōu)勢成為日常開發(fā)的首選，但也存在無法回避的短板：頭部 / 中間插入刪除需要挪動大量元素，時間復雜度高達 O (n)；擴容時的內(nèi)存拷貝也會帶來額外性能開銷。
而 list 作為 STL 中另一核心容器，恰好彌補了 vector 的這些不足：它基于雙向循環(huán)鏈表實現(xiàn)，任意位置的插入刪除僅需修改指針指向，時間復雜度可降至 O (1)。本章我們將從鏈表的底層結(jié)構(gòu)出發(fā)，一步步實現(xiàn)一個功能完整的 list 類，帶你掌握：
- 雙向循環(huán)鏈表的設(shè)計邏輯與核心優(yōu)勢
- list 與 vector 的底層差異及適用場景
- 鏈表迭代器的特殊實現(xiàn)（為什么不能直接用指針？）
一、list 容器的核心特性
list 是 STL 中以雙向循環(huán)鏈表為底層結(jié)構(gòu)的序列式容器，其核心特性包括：
- 非連續(xù)存儲：元素在內(nèi)存中離散分布，通過指針連接形成鏈表
- 雙向遍歷：每個節(jié)點包含前驅(qū)和后繼指針，支持向前 / 向后遍歷
- 高效增刪：任意位置的插入 / 刪除操作僅需修改指針指向，時間復雜度為 O (1)
- 無擴容開銷：無需預先分配內(nèi)存，元素增減不會導致大規(guī)模內(nèi)存拷貝
- 迭代器特殊：迭代器不是原生指針，需重載
++/--等運算符實現(xiàn)節(jié)點跳轉(zhuǎn)
與 vector 的核心差異：
| 特性 | vector | list |
|---|---|---|
| 存儲方式 | 連續(xù)內(nèi)存空間 | 離散鏈表節(jié)點 |
| 隨機訪問 | 支持（O (1)） | 不支持（需遍歷） |
| 插入刪除效率 | 中間插入刪除效率低（O (n)） | 任意位置效率高（O (1)） |
| 內(nèi)存開銷 | ?。▋H存儲數(shù)據(jù)） | 大（需額外存儲指針） |
| 擴容機制 | 自動擴容（可能有拷貝） | 無擴容機制 |
二、list 的迭代器使用
list 的迭代器是實現(xiàn)鏈表遍歷的關(guān)鍵，由于其非連續(xù)存儲特性，迭代器的實現(xiàn)與 vector 有本質(zhì)區(qū)別。
| 方式 | 適用場景 |
|---|---|
begin() + end() | 正向迭代器，begin() 指向首元素，end() 指向尾元素下一位r |
rbegin() + rend() | 反向迭代器，rbegin() 指向尾元素，rend() 指向首元素前一位 |
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {1, 2, 3, 4, 5};
// 正向迭代器遍歷
cout << "正向遍歷: ";
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
cout << *it << " ";
}
cout << endl; // 輸出：1 2 3 4 5
// 反向迭代器遍歷
cout << "反向遍歷: ";
for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl; // 輸出：5 4 3 2 1
return 0;
}
注意：list 的迭代器不支持隨機訪問（如 it + 3 操作），只能通過 ++/-- 逐步移動。
三、list 的常見構(gòu)造方式
list 提供了多種構(gòu)造函數(shù)，滿足不同場景下的初始化需求：
| 方式 | 適用場景 |
|---|---|
| list() | 無參構(gòu)造，創(chuàng)建空鏈表 |
| list(size_type n, const T& val = T()) | 構(gòu)造包含 n 個 val 元素的鏈表 |
| list(const list& x) | 拷貝構(gòu)造，創(chuàng)建 x 的副本 |
| list(InputIterator first, InputIterator last) | 用 [first, last) 區(qū)間元素構(gòu)造鏈表 |
| list(initializer_list< T > ilist) | 初始化列表構(gòu)造（C++11） |
#include <iostream>
#include <list>
using namespace std;
void printList(const list<int>& l) {
for (auto num : l) {
cout << num << " ";
}
cout << endl;
}
int main() {
// 無參構(gòu)造
list<int> l1;
// 構(gòu)造包含5個3的鏈表
list<int> l2(5, 3);
printList(l2); // 輸出：3 3 3 3 3
// 迭代器區(qū)間構(gòu)造
list<int> l3(l2.begin(), --l2.end());
printList(l3); // 輸出：3 3 3 3
// 拷貝構(gòu)造
list<int> l4(l3);
printList(l4); // 輸出：3 3 3 3
// 初始化列表構(gòu)造（C++11）
list<int> l5{1, 2, 3, 4, 5};
printList(l5); // 輸出：1 2 3 4 5
return 0;
}
四、list 的容量與元素訪問
list 提供了基礎(chǔ)的容量查詢和元素訪問接口：
| 方式 | 適用場景 |
|---|---|
| empty() | 判斷鏈表是否為空，為空返回 true |
| size() | 返回鏈表中有效元素的個數(shù) |
| front() | 返回鏈表第一個元素的引用 |
| back() | 返回鏈表最后一個元素的引用 |
| max_size() | 返回鏈表理論上能容納的最大元素個數(shù)（很少使用） |
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {10, 20, 30, 40, 50};
cout << "鏈表是否為空: " << (l.empty() ? "是" : "否") << endl; // 輸出：否
cout << "鏈表元素個數(shù): " << l.size() << endl; // 輸出：5
cout << "第一個元素: " << l.front() << endl; // 輸出：10
cout << "最后一個元素: " << l.back() << endl; // 輸出：50
// 修改首尾元素
l.front() = 100;
l.back() = 500;
for (auto num : l) {
cout << num << " ";
}
// 輸出：100 20 30 40 500
return 0;
}
注意：list 不支持 operator[] 下標訪問和隨機訪問，只能通過迭代器或 front()/back() 訪問元素。
五、list 的增刪查改操作
list 提供了豐富的元素操作接口，尤其擅長插入和刪除操作：
| 函數(shù)聲明 | 接口說明 |
|---|---|
| push_front(const T& val) | 在鏈表頭部插入元素 val |
| pop_front() | 刪除鏈表頭部元素 |
| push_back(const T& val) | 在鏈表尾部插入元素 val |
| pop_back() | 刪除鏈表尾部元素 |
| insert(iterator pos, const T& val) | 在 pos 位置前插入元素 val |
| insert(iterator pos, size_type n, const T& val) | 在 pos 位置前插入 n 個 val |
| insert(iterator pos, InputIterator first, InputIterator last) | 在 pos 位置前插入 [first, last) 區(qū)間元素 |
| erase(iterator pos) | 刪除 pos 位置的元素，返回下一個元素的迭代器 |
| erase(iterator first, iterator last) | 刪除 [first, last) 區(qū)間元素，返回下一個元素的迭代器 |
| swap(list& x) | 交換當前鏈表與 x 中的元素 |
| clear() | 清空鏈表中的所有元素 |
| remove(const T& val) | 刪除鏈表中所有值為 val 的元素 |
| unique() | 刪除連續(xù)的重復元素（只保留一個） |
| sort() | 對鏈表元素進行排序（升序） |
| reverse() | 反轉(zhuǎn)鏈表元素的順序 |
#include <iostream>
#include <list>
#include <algorithm> // 用于find算法
using namespace std;
void printList(const list<int>& l, const string& msg) {
cout << msg << ": ";
for (auto num : l) {
cout << num << " ";
}
cout << endl;
}
int main() {
list<int> l;
// 尾插元素
l.push_back(1);
l.push_back(2);
l.push_back(3);
printList(l, "尾插后"); // 輸出：1 2 3
// 頭插元素
l.push_front(0);
printList(l, "頭插后"); // 輸出：0 1 2 3
// 查找元素（使用STL算法）
auto it = find(l.begin(), l.end(), 2);
if (it != l.end()) {
// 在找到的位置前插入元素
l.insert(it, 100);
printList(l, "插入后"); // 輸出：0 1 100 2 3
}
// 刪除元素
it = find(l.begin(), l.end(), 1);
if (it != l.end()) {
l.erase(it);
printList(l, "刪除后"); // 輸出：0 100 2 3
}
// 排序
l.sort();
printList(l, "排序后"); // 輸出：0 2 3 100
// 反轉(zhuǎn)
l.reverse();
printList(l, "反轉(zhuǎn)后"); // 輸出：100 3 2 0
// 移除指定值元素
l.remove(3);
printList(l, "移除3后"); // 輸出：100 2 0
// 清空鏈表
l.clear();
cout << "清空后是否為空: " << (l.empty() ? "是" : "否") << endl; // 輸出：是
return 0;
}
注意：
list自帶sort()成員函數(shù)，不建議使用 STL 中的sort算法（效率低）- 插入操作不會使迭代器失效，刪除操作只會使被刪除元素的迭代器失效
unique()僅刪除連續(xù)的重復元素，通常需配合sort()使用以刪除所有重復元素
六、list的實際運用
list憑借其高效的插入刪除特性，適用于以下場景：
- 頻繁插入刪除的場景：如實現(xiàn)隊列、棧、雙向隊列等數(shù)據(jù)結(jié)構(gòu)
- 數(shù)據(jù)元素較大的場景：避免
vector擴容時的大量數(shù)據(jù)拷貝- 需要頻繁在兩端操作的場景：如實現(xiàn) LRU 緩存淘汰算法
七、總結(jié)
list 作為基于雙向循環(huán)鏈表的容器，在元素插入刪除操作上具有顯著優(yōu)勢，但不支持隨機訪問。使用時需根據(jù)具體場景選擇：
- 需頻繁隨機訪問數(shù)據(jù) → 選擇
vector - 需頻繁插入刪除數(shù)據(jù) → 選擇
list - 數(shù)據(jù)量小且訪問模式不確定 → 可優(yōu)先考慮
vector（簡單高效）
掌握 list 的迭代器特性和成員函數(shù)用法，能幫助我們在合適的場景下寫出更高效的代碼。在實際開發(fā)中，合理搭配不同容器的優(yōu)勢，才能發(fā)揮 STL 的最大威力。
到此這篇關(guān)于C++中l(wèi)ist實現(xiàn)雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C++ list雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
memset是一個初始化函數(shù)，作用是將某一塊內(nèi)存中的全部設(shè)置為指定的值，本文給大家介紹C++中的memset用法，感興趣的朋友跟隨小編一起看看吧2023-02-02
? 互斥量是一種同步原語,用于保護多個線程同時訪問共享數(shù)據(jù),互斥量提供獨占的、非遞歸的所有權(quán)語義,本文將和大家一起深入探究C/C++中互斥量(鎖)的實現(xiàn)原理,感興趣的小伙伴跟著小編一起來看看吧2024-06-06
本文介紹了在Qt中遍歷QStringList子集并存儲的三種方法：1）使用mid()函數(shù)提取連續(xù)范圍的元素；2）通過循環(huán)遍歷指定索引范圍；3）利用filter()函數(shù)按內(nèi)容篩選,每種方法適用于不同場景,需要的朋友可以參考下2026-01-01
C++實現(xiàn)LeetCode(136.單獨的數(shù)字)
這篇文章主要介紹了C++實現(xiàn)LeetCode(136.單獨的數(shù)字),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
類型轉(zhuǎn)換是項目中常使用的一種語法規(guī)則,幾乎每個編程語言都不可避免的涉及到這方面,下面這篇文章主要給大家介紹了關(guān)于C++11新特性之四種類型轉(zhuǎn)換cast說明的相關(guān)資料,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了C語言基礎(chǔ) strlen 函數(shù)，在C 語言中，char 字符串也是一種非常重要的數(shù)據(jù)類型，我們可以使用 strlen 函數(shù)獲取字符串長度，這就是C語言strlen 函數(shù)的作用，下面我們來簡單介紹該內(nèi)容,需要的朋友可以參考以下2021-10-10
本文主要介紹了C++內(nèi)存對齊的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
又是一年七夕節(jié)要到了,每年一次直男審美MATLAB繪圖大賽開始了,于是今年對我之前寫的老代碼進行了點優(yōu)化組合,整了個花球變花束,感興趣的小伙伴可以動手試一試2023-08-08
在面向?qū)ο笳Z言中,經(jīng)常提到重載與重寫,本文主要介紹了C++ 重載與重寫的區(qū)別與實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-01-01
QWidget類是所有用戶界面對象的基類,被稱為基礎(chǔ)窗口部件,下面這篇文章主要給大家介紹了關(guān)于QT中大部分部件如何使用的相關(guān)資料,需要的朋友可以參考下2022-06-06