当前位置：首页 > news >正文

手撕C++STL list：深入理解双向链表的实现

news 来源：原创 2025/7/3 8:59:10

1. 引言

3. list 类的实现

(1) 基本结构

(2) 初始化与清理

(3) 插入与删除

(4) 常用接口

4. 测试代码

5. 总结

1. 引言

在C++ STL中，list是一个基于双向链表的容器，支持高效的头尾插入/删除操作（O(1)时间复杂度），但不支持随机访问（O(n)时间复杂度）。本文将带你手写一个简化版的 list，并分析其核心实现。
2. 核心结构：list_node 与 __list_iterator
(1) list_node：链表的节点

template<class T>
struct list_node {list_node<T>* _next;  // 指向下一个节点list_node<T>* _prev;  // 指向前一个节点T _val;               // 存储的数据list_node(const T& val = T()) : _next(nullptr), _prev(nullptr), _val(val) {}
};

双向链表节点，包含前驱（_prev）、后继（_next）指针和数据（_val）。
默认构造函数初始化指针为 nullptr，数据为默认值 T()

(2) __list_iterator：链表的迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator {typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;  // 当前指向的节点__list_iterator(Node* node) : _node(node) {}// 解引用（获取数据）Ref operator*() { return _node->_val; }// 成员访问（-> 运算符重载）Ptr operator->() { return &_node->_val; }// 前置++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 _node != it._node; }bool operator==(const self& it) const { return _node == it._node; }
};

迭代器核心功能：
- operator*()：获取当前节点的数据。
- operator->()：访问当前节点的成员（如 it->_a1）。
- ++ / --：支持双向遍历。
- == / !=：判断迭代器是否指向同一节点。

3. `list` 类的实现

(1) 基本结构

template<class T>
class list {typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;         // 普通迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;  // const迭代器list() { empty_init(); }  // 默认构造~list() { clear(); delete _head; _head = nullptr; }  // 析构// 拷贝构造list(const list<T>& lt) {empty_init();for (auto& e : lt) push_back(e);}// 赋值运算符（现代写法）list<T>& operator=(list<T> lt) {swap(lt);return *this;}// 交换两个链表void swap(list<T>& lt) {std::swap(_head, lt._head);std::swap(_size, lt._size);}
private:Node* _head;   // 哨兵头节点（不存储数据）size_t _size;  // 链表长度
};

关键点：
- 哨兵节点 _head：简化边界条件处理（begin() 是 _head->_next，end() 是 _head）。
- 拷贝构造：深拷贝，逐个插入元素。
- 赋值运算符：现代写法（参数传值 + swap）。

(2) 初始化与清理

void empty_init() {_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;
}void clear() {iterator it = begin();while (it != end()) {it = erase(it);}_size = 0;
}

empty_init()：初始化空链表（哨兵节点自环）。
clear()：逐个删除节点，最后重置 _size。

(3) 插入与删除

// 在 pos 前插入
iterator 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;++_size;return iterator(newnode);
}// 删除 pos 位置的节点
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;--_size;return iterator(next);
}

insert：调整前后指针，插入新节点。
erase：调整指针后删除节点，返回下一个有效迭代器。

(4) 常用接口

void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_head); }
const_iterator begin() const { return const_iterator(_head->_next); }
const_iterator end() const { return const_iterator(_head); }size_t size() const { return _size; }

(4) 常用接口

void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_head); }
const_iterator begin() const { return const_iterator(_head->_next); }
const_iterator end() const { return const_iterator(_head); }size_t size() const { return _size; }

4. 测试代码

void test_list() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);for (auto e : lt) cout << e << " ";  // 1 2 3cout << endl;lt.pop_front();for (auto e : lt) cout << e << " ";  // 2 3
}

5. 总结

list 的核心是双向链表，插入/删除高效（O(1)），但不支持随机访问。
迭代器是双向迭代器，支持 ++ / --，但不支持 + / - / []。
哨兵节点简化边界处理，begin() 指向第一个元素，end() 指向哨兵。
深拷贝需手动实现（拷贝构造、赋值运算符）。

通过手写 list，可以更深入理解STL容器的底层实现！

手撕C++STL list：深入理解双向链表的实现

目录 1. 引言 3. list 类的实现 (1) 基本结构 (2) 初始化与清理 (3) 插入与删除 (4) 常用接口 (4) 常用接口 4. 测试代码 5. 总结 1. 引言在C STL中，list是一个基于双向链表的容器，支持高效的头尾插入/删除操作（O(1)时间复杂度&…...

编程日记 2025/7/3 8:59:10

QMT学习课程Day1

我们先从交易的最基础，如何进行下单，最为简答的下单，帮助大家建立自信心。首先导入相关函数： #encoding:gbk import pandas as pd import numpy as np import datetime import pandas as pd import numpy as np import talib i…...

编程日记 2025/6/29 10:40:19

【Rust结构体】Rust结构体详解：从基础到高级应用

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，…...

编程日记 2025/7/3 8:10:41

Java面试实战：音视频场景下的微服务架构与缓存技术剖析

面试场景描述谢飞机，一位自称“全栈工程师”的程序员，来到一家互联网大厂参加Java开发岗位的面试。面试官是一位严肃的技术专家，他希望通过一系列问题考察谢飞机的实际技术水平。第一轮提问（基础问题） 面试官&…...

编程日记 2025/7/3 8:41:53

Vue 3 的核心组合式 API 函数及其完整示例、使用场景和总结表格

以下是 Vue 3 的核心组合式 API 函数及其完整示例、使用场景和总结表格： 1. ref 作用创建一个响应式引用值，用于管理基本类型或单个值的响应式状态。示例 <template><div><p>Count: {{ count }}</p><button click&quo…...

编程日记 2025/6/29 9:20:11

Kotlin学习基础知识大全(上)

文章目录 Kotlin基础知识全面解析第一章：Kotlin语言概述1.1 Kotlin的发展历程1.2 Kotlin的设计目标1.3 Kotlin的应用领域1.4 Kotlin与Java的比较第二章：Kotlin基础语法2.1 变量与常量2.2 基本数据类型数字类型示例：字符和字符串示例&#xf…...

编程日记 2025/7/3 8:30:03

【Java面试笔记：进阶】18.什么情况下Java程序会产生死锁？如何定位、修复？

死锁（Deadlock）是指两个或多个线程因竞争资源而无限期阻塞的现象。 1. 死锁的定义与产生原因定义：死锁是一种程序状态，多个线程或进程因循环依赖而永久处于等待状态，无法继续执行。根据 Coffman 条件，死锁产生需同时满足以下四个必要条件：互斥（Mutual Exclusion）…...

编程日记 2025/6/29 9:51:58

PS Mac Photoshop 2025 for Mac图像处理 PS 2025安装笔记

Mac分享吧文章目录效果一、准备工作二、开始安装1、Anticc简化版安装1.1双击运行软件，安装1.2 解决来源身份不明的开发者问题**此代码为打开：系统偏好设置 – 隐私与安全性，中的【任何来源】，如下图：**1.3 再次运行…...

编程日记 2025/7/3 8:51:08

HarmonyOS 框架基础知识

参考文档：HarmonyOS开发者文档第三方库：OpenHarmony三方库中心仓基础特性 Entry：关键装饰器 Components：组件特性EntryComponent作用范围仅用于页面入口可定义任意可复用组件数量限制每个页面有且仅有一个无数量…...

编程日记 2025/7/3 8:23:17

LabVIEW实现Voronoi图绘制功能

该 LabVIEW 虚拟仪器（VI）借助 MathScript 节点，实现基于手机信号塔位置计算 Voronoi 图的功能。通过操作演示，能直观展示 Voronoi 图在空间划分上的应用。各部分功能详细说明随机地形创建部分功能：根据 “Maximum a…...

编程日记 2025/7/3 8:20:15

centos7的环境下ollama 如何卸载

在 CentOS 7 环境下卸载 ollama，可以按照以下步骤操作。假设 ollama 是通过手动安装的，以下是卸载的详细步骤。 1. 停止所有运行中的 ollama 进程在卸载之前，确保所有与 ollama 相关的进程都已停止。查找并停止进程 ps aux | grep ollam…...

编程日记 2025/6/29 9:20:13

中心极限定理（CLT）习题集 · 答案与解析篇

中心极限定理（CLT）习题集答案与解析篇与题目篇一一对应。若有其他解法欢迎在评论区补充。 1. 概念与判断题 1.1 经典叙述若 (X_1,X_2,\dots) i.i.d.，满足 (E[X_1]=\mu,;0<\sigma^2:=\operatorname{Var}(X_1)<\infty)。则 [ Z_n=\frac{\sum_{k=1}^{n}(X_k-\mu)}…...

编程日记 2025/7/3 8:35:57

Spring Cloud Gateway配置双向SSL认证（完整指南）

本文将详细介绍如何为Spring Cloud Gateway配置双向SSL认证，包括证书生成、配置和使用。目录结构 /my-gateway-project ├── /certs │ ├── ca.crt # 根证书 │ ├── ca.key # 根私钥 │ ├── gateway.crt # 网关证书 │ ├── …...

编程日记 2025/6/29 9:20:01

中间系统-SPF计算

SPF计算 isis如何计算路由：以自己为根构建SPF树，之后填充叶子。 <R1>display isis lsdb 0000.0000.0001.00-00 verbose //查看lsp的详细信息 SOURCE 0000.0000.0001.00 //源节点系统，用于标识产生该LSP的路由器…...

编程日记 2025/6/29 10:51:12

立马耀：通过阿里云 Serverless Spark 和 Milvus 构建高效向量检索系统，驱动个性化推荐业务

作者：厦门立马耀网络科技有限公司大数据开发工程师陈宏毅背景介绍行业蝉选是蝉妈妈出品的达人选品服务平台。蝉选秉持“陪伴达人赚到钱”的品牌使命，致力于洞悉达人变现需求和痛点，提供达人选高佣、稳变现、速响应的选品服务。业务特…...

编程日记 2025/7/3 8:31:02

Diffusion inversion后的latent code与标准的高斯随机噪音不一样

可视化latents_list如下; 可视化最后一步与标准的噪声： 能隐约看出到最后一步还是会有“马”的形状整个代码（及可视化代码如下）： ## 参考freeprompt(FPE)的代码 import os import torch import torch.nn as nn import torch.n…...

编程日记 2025/7/3 8:36:57

C语言-函数-1

以下是我初学C语言的笔记记录，欢迎在评论区留言补充一，函数分为几类 * 函数分为两类： 一类是库函数；一类是自定义函数 * 库函数： 系统自己带的，在使用时候，要用到头文件； 查询库函…...

编程日记 2025/7/3 8:46:24

AXOP34032: 40V/40µA 轨到轨输入输出双通道运算放大器

AXOP34032是一款通用型高压低功耗双通道运算放大器，产品的工作电压为2.5V至40V，具有1.2MHz的带宽，压摆率为 0.7V/μs，单路静态电流为40A。该产品非常适合需要较高耐压的低功耗应用。产品可选关断功能(AXOP34032S)。主要特性 2…...

编程日记 2025/7/3 8:52:58

HTML5 服务器发送事件 (Server-Sent Events)：实现网页自动获取服务器更新

一、引言在现代 Web 应用开发中，实时性和动态交互性变得越来越重要。HTML5 引入的服务器发送事件（Server-Sent Events，简称 SSE）为网页获取来自服务器的实时更新提供了一种简单而有效的解决方案。与传统方式中网页需主动询问服务器是否有更新不同，SSE 能够让更新自动推送…...

编程日记 2025/7/3 8:57:19

如何创建和使用 Hive 视图

一、Hive 视图的基本概念 Hive 视图是一种虚拟表，其内容由查询语句定义，本身不存储实际数据。当查询视图时，Hive 会动态执行视图定义中的查询逻辑并返回结果。视图的核心作用是简化复杂查询、提供数据抽象和实现权限控制。例如，通过视图可以隐藏底层表的复杂关联关系，或限…...

编程日记 2025/7/3 8:43:52

快速体验tftp文件传输（嵌入式设备）

一、参考资料 Linux tftp 命令 | 菜鸟教程 Ubuntu最新版本(Ubuntu22.04LTS)安装Tftp服务及其使用教程-CSDN博客 Windows下的Tftpd32(Tftpd64)软件下载和使用教程-集成了Tftp服务器、客户端-CSDN博客 tftpd32 tftpd64文件传输安装和使用教程【图文并茂】-CSDN博客二、快速…...

编程日记 2025/6/29 11:33:21

数据库进阶之MySQL 程序

1.目标 1> 了解mysqlId服务端程序 2> 掌握mysql客户端程序的使用 3> 了解工具包中的其他程序 2. MySQL程序简介本章介绍 MySQL 命令⾏程序以及在运⾏这些程序时指定选项的⼀般语法(如:mysql -uroot -p)。对常⽤程序进⾏详细的讲解(实用工具的使用方法)&#xf…...

编程日记 2025/7/3 8:36:57

细说STM32单片机FreeRTOS信号量和互斥量及二值信号量的应用实例

目录一、信号量和互斥量概述 1、二值信号量 2、计数信号量 3、互斥量 4、递归互斥量 5、相关函数概述 （1） 负责创建的函数 （2） 负责释放和获取的函数 （3）负责返回数据的函数二、二值信号量使用…...

编程日记 2025/7/3 8:47:05

云原生之认识DDD

一、DDD是什么？领域驱动设计(DDD) 做为一种软件工程的方法论，它可以帮助我们设计高质量的软件，或者说任何工程的设计都需要方法论，不论是城市设计、建筑设计、室内设计。比如没有方法论的情况下楼是可以盖起来的，或许整个楼道和窗户上挂满了电话线、闭路线、电线？下水…...

编程日记 2025/7/3 8:34:50

Kingbase 数据库物理备份与恢复操作手册

版本环境：KingbaseES V8R6 适用对象：DBA / 运维工程师 / 技术支持人员目标用途：生产环境灾备保障、全量迁移、异地容灾恢复一、物理备份操作流程物理备份是指直接对数据库实例的物理文件进行复制，具备完整性强、恢复速度快等特…...

编程日记 2025/7/3 8:25:00

高等数学同步测试卷同济7版试卷部分上做题记录第四章不定积分同步测试卷 A卷

第四章不定积分同步测试卷 A卷一、单项选择题(本大题共5小题，每小题3分，总计15分) 1. 2. 3. 4. 5. 二、填空题(本大题共5小题,每小题3分,总计15 分) 6. 7. 8. 9. 10. 三、求解下列各题(本大题共5小题,每小题6分,总计30…...

编程日记 2025/7/3 8:43:51

【刷题Day25】用户态和内核态、Reactor、虚拟内存（浅）

什么是用户态和内核态？ 用户态（User Mode）和内核态（Kernel Mode）是操作系统中的两种运行模式，用于区分应用程序与操作系统内核的操作权限。两者区别在于权限级别： 用户态：应用程…...

编程日记 2025/7/3 8:41:53

使用Qt Quick Controls创建自定义日历组件

目录引言相关阅读1. DayOfWeekRow2. MonthGrid3. WeekNumberColumn 项目结构及实现工程结构图代码实现及解析1. 组件封装2. 主界面实现运行效果总结下载链接引言 Qt6 Quick框架提供了一套丰富的日历相关组件，包括 MonthGrid、DayOfWeekRow 和 WeekNumberColumn…...

编程日记 2025/7/3 8:56:30

Java 富文本转word

前言： 本文的目的是将传入的富文本内容(html标签，图片)并且分页导出为word文档。所使用的为docx4j 一、依赖导入 <dependency><groupId>org.docx4j</groupId><artifactId>docx4j</artifactId&…...

编程日记 2025/7/3 8:46:23

基于 Spring Boot 瑞吉外卖系统开发（七）

基于 Spring Boot 瑞吉外卖系统开发（七） 新增菜品页面菜品管理页面提供了一个“新增菜品”按钮，单击该按钮时，会打开新增菜品页面。菜品分类列表首先要获取分类列表数据。请求路径/category/list，请求方法GE…...

编程日记 2025/6/29 9:52:30

// Child.jsx import React, { forwardRef, useImperativeHandle, useState } from react; import { Form, Input } from antd;const Child forwardRef((props, ref) > {const [form] Form.useForm();const [customState, setCustomState] useState(默认值);useImperativ…...

编程日记 2025/6/29 12:00:55

1. 引言

3. list 类的实现

(1) 基本结构

(2) 初始化与清理

(3) 插入与删除

(4) 常用接口

(4) 常用接口

4. 测试代码

5. 总结

相关文章：

3. `list` 类的实现