想要学好C++、吃透STL底层源码，弄懂各类容器的实现逻辑是必不可少的一步，而STL里面十分经典的序列式容器list，底层依靠的就是带头双向循环链表，和普通单链表以及动态数组vector相比，它在任意位置插入、删掉元素的效率都很高，不光不用操心扩容问题，各类边界情况的处理方式也更简单，这篇博客就带着大家从零基础开始，一步步手写完成list核心的增删查改功能，彻底弄懂双向链表的底层运行逻辑。
一、带头双向循环链表核心特性
动手编写代码前，我们先要理清list底层链表的核心架构，这也是后续实现各类功能接口的重要基础。
- 带头节点：设置一个不存放有效数据的哨兵位头节点，能统一空链表和非空链表的操作逻辑，不用额外判断链表是否为空，也能大幅简化各类边界情况的处理步骤。
- 双向：每一个节点都会同时留存前驱指针prev和后继指针next，既可以向前遍历也可以向后遍历，迭代器也能正常完成++、--这类基础操作。
- 循环：尾节点的next指针指向头节点，头节点的prev指针又指向尾节点，二者形成完整的闭环，能快速定位首尾节点，做尾插、尾删操作时也不用从头到尾遍历整条链表。
在这样的结构支撑下，链表任意位置插入、删除元素的时间复杂度都是O(1)，唯一的不足就是不支持随机访问，只能借助迭代器一步步遍历查找想要的元素。
二、整体结构设计
本次我们采用模板类实现整个容器，让容器可以适配任意类型的数据，整体结构一共分成三大部分，分别是链表节点结构体、迭代器封装类以及list容器主类，迭代器不会直接使用原生指针，而是对节点指针做一层封装，再通过运算符重载模拟指针的使用行为，和STL原生list的设计思路完全保持一致。
1. 链表节点结构体
单个节点包含数据域、前驱指针、后继指针三个核心部分，构造函数会直接完成节点的初始化工作，从根源上杜绝野指针带来的各类问题。
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace mylist
{
// 链表节点结构体
template<class T>
struct list_node
{
// 节点成员
T _data;
list_node<T>* _prev;
list_node<T>* _next;
// 构造函数
list_node(const T& x = T())
:_data(x)
, _prev(nullptr)
, _next(nullptr)
{}
};
2. 迭代器类
list的迭代器并不是原生指针，需要对节点指针做封装处理，同时重载*、->、++、--、==、!=等运算符，实现和原生指针完全一样的遍历、访问效果，我们还会用到三模板参数，让普通迭代器和const迭代器共用一套代码，减少重复多余的代码量。
// 迭代器类
template
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->_data;
}
// 箭头运算符：适配自定义类型访问
Ptr operator->()
{
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 _node == it._node;
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}};
3. list容器主体类
容器类只需要维护好哨兵位头节点和有效元素个数即可，构造函数负责完成头节点初始化，析构函数负责释放占用的内存，核心实现增删查改各类基础接口，还会通过接口复用的方式，简化整体的代码逻辑。
// list容器类
template
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;
// 迭代器获取
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);
}
// 构造函数：初始化哨兵位头节点
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// 析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
// 清空容器：保留哨兵位头节点
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
// 获取有效元素个数
size_t size() const
{
return _size;
}
// 判断是否为空
bool empty() const
{
return _size == 0;
}
三、核心增删查改接口实现
1. 插入接口：insert（任意位置插入）
insert是list插入操作的核心函数，头插、尾插都可以直接调用这个接口，只需要调整待插入位置前后节点的指针，将新节点顺利链接到链表中即可，对应的时间复杂度固定为O(1)。
// 任意位置插入
iterator insert(iterator pos, const T& x)
{
assert(pos != end());
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);
}
2. 尾插、头插（复用insert）
// 尾插
void push_back(const T& x)
{
insert(end(), x);
}
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
3. 删除接口：erase（任意位置删除）
erase是删除操作的核心接口，头删、尾删都会直接调用这个函数，删除节点时要先断开节点之间的指针链接，再释放节点占用的内存，同时返回下一个位置的迭代器，以此避免出现迭代器失效的问题。
// 任意位置删除
iterator erase(iterator pos)
{
assert(pos != end());
assert(!empty());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 断开节点链接
prev->_next = next;
next->_prev = prev;
// 释放节点
delete cur;
--_size;
return iterator(next);
}
4. 尾删、头删（复用erase）
// 尾删
void pop_back()
{
erase(--end());
}
// 头删
void pop_front()
{
erase(begin());
}
5. 查找接口：find
list本身不支持随机访问，想要查找元素只能借助迭代器遍历整条链表，找到目标数值就返回对应的迭代器，若是没有找到则直接返回end()迭代器。
// 查找指定值
iterator find(const T& x)
{
iterator it = begin();
while (it != end())
{
if (*it == x)
{
return it;
}
++it;
}
return end();
}
6. 修改操作
通过迭代器定位到目标节点之后，直接解引用就可以修改节点内的数值，不用再单独封装专门的修改接口，操作起来十分简便。
// 修改指定位置值
void modify(iterator pos, const T& x)
{
assert(pos != end());
*pos = x;
}
7. 容器收尾与私有成员
private:
Node* _head; // 哨兵位头节点
size_t _size; // 有效元素个数
};
}
四、功能测试验证
写完所有核心接口之后，我们可以编写对应的测试代码，检查增删查改各项功能能否正常运行，测试逻辑也会覆盖日常开发里常用的各类操作场景。
void test_list()
{
// 测试增删查改
mylist::list<int> lt;
// 尾插
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
// 遍历打印
cout << "尾插后遍历：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
// 头插
lt.push_front(0);
cout << "头插后遍历：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
// 查找+修改
auto it = lt.find(3);
if (it != lt.end())
{
lt.modify(it, 30);
}
cout << "修改3为30后：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
// 尾删+头删
lt.pop_back();
lt.pop_front();
cout << "尾删头删后：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
// 清空
lt.clear();
cout << "清空后size：" << lt.size() << endl;
}
int main()
{
test_list();
return 0;
}
五、核心要点总结
- 带头双向循环链表自带的哨兵位节点，是简化边界处理的核心关键，空链表和非空链表的操作逻辑完全统一，不用做额外区分。
- list的插入、删除操作运行效率极高，时间复杂度均为O(1)，但缺点是不支持随机访问，更适合需要频繁增删元素的使用场景。
- 迭代器封装是STL容器的核心设计思路，list迭代器通过运算符重载，实现了和原生指针相近的便捷使用效果。
- 接口复用能大幅缩减重复代码量，头插尾插直接调用insert函数，头删尾删直接调用erase函数，后期维护代码也会更省心。
- 删除节点时一定要及时释放对应的内存，避免出现内存泄漏的情况，同时返回下一位置迭代器，彻底解决迭代器失效的问题。
以上就是list带头双向链表增删查改功能的完整手写实现，代码贴合STL原生设计思路，逻辑清晰易懂，吃透这份代码就能完全掌握list底层原理，后续深入学习STL源码也会变得更加轻松。