C++双链表介绍及实现

双链表详解

1. 基本概念

双链表（双向链表）​ 是一种链式数据结构，每个节点包含两个指针：

• ​前驱指针（pre）​：指向直接前驱节点
• ​后继指针（next）​：指向直接后继节点

与单链表对比：

2. 核心结构

用户代码中的 student 结构体：

struct student {
    int m_id;
    string m_name;
    weak_ptr<student> pre;   // 前驱指针（弱引用）
    shared_ptr<student> next;// 后继指针（强引用）
};

智能指针设计亮点：

1. ​防止内存泄漏：
   • shared_ptr 自动管理节点生命周期
   • 析构时自动释放整个链表
2. ​打破循环引用：
   • 前驱使用 weak_ptr 避免循环强引用
   • 当删除节点时，weak_ptr 自动失效

循环引用问题

1. 如果前驱和后驱均用 shared_ptr

假设双向链表中所有节点都用 shared_ptr 相互连接：

struct Node {
    shared_ptr<Node> pre;  // 错误！
    shared_ptr<Node> next; // 错误！
};

当删除链表时：

• ​引用计数永远无法归零：每个节点的 pre 和 next 指针互相持有对方的强引用（shared_ptr）。
• ​内存泄漏：即使外部不再使用链表，节点间依然存在循环强引用，导致内存无法释放。

2. 示例说明

graph LR
A --> B
B --> A

• 节点A的next指向B → B的引用计数=1
• 节点B的pre指向A → A的引用计数=1
• 即使删除头节点，A和B的引用计数始终≥1 → 内存泄漏！

解决方案：weak_ptr 打破循环

1. 设计原理

• ​**shared_ptr 后继指针**：表示节点 ​拥有（own）​ 下一个节点的所有权。
• ​**weak_ptr 前驱指针**：仅表示节点 ​观察（observe）​ 前一个节点，但不持有所有权。

2. 所有权关系

graph LR
A[shared_ptr] --> B[shared_ptr]
B -.-> A[weak_ptr]

• 单向所有权链：从头节点（top）到尾节点（tail），所有节点通过 next 指针形成一条强引用链。
• ​反向弱引用：pre 指针通过 weak_ptr 反向观察，但不增加引用计数。

3. 内存释放过程

当删除头节点时：

1. 头节点的 shared_ptr 被释放 → 引用计数归零 → 头节点内存释放。
2. 头节点的 next 指针释放 → 下一个节点的引用计数减1。
3. 若下一个节点的引用计数归零 → 重复步骤1~2，直到整个链表释放。

即使存在 weak_ptr 前驱指针，也不会阻止节点释放。

代码示例分析

1. 用户代码中的 student 结构

struct student {
    int m_id;
    string m_name;
    weak_ptr<student> pre;   // 前驱：弱引用
    shared_ptr<student> next;// 后驱：强引用
};

2. 插入操作的引用计数变化

假设插入节点 B 到节点 A 之后：

A.next = make_shared<B>();
B.pre = A; // weak_ptr 不增加A的引用计数

• 节点A的引用计数：1（仅被外部持有）
• ​节点B的引用计数：1（被A的next持有）

3. 删除节点时的行为

删除节点A：

• A的引用计数归零 → 内存释放。
• B的pre指针（指向A）自动失效（weak_ptr::expired() == true）。

为什么选择前驱为 weak_ptr？

1. 设计意图

• ​单向所有权链：大多数链表操作（如遍历、插入、删除）​从头部向尾部进行，next 指针是主要操作方向。
• ​避免反向强引用：若 pre 也用 shared_ptr，尾部节点的 pre 指针会强制持有前驱节点的强引用，导致无法释放。

2. 性能与安全性

• ​**weak_ptr 的安全性**：访问前驱时需通过 lock() 转为 shared_ptr，确保操作期间前驱节点有效。
• ​无额外开销：weak_ptr 不增加引用计数，不影响内存释放速度。

对比其他设计方案

3. 关键操作分析 

3.1 插入操作

头插法​（用户代码中 push(int id, string name)）：

void push(int id, string name) {
    auto new_node = make_shared<student>(id, name, nullptr, top);
    if (top) top->pre = new_node; // 更新原头节点的前驱
    else tail = new_node;         // 空链表时初始化尾指针
    top = new_node;               // 更新头指针
}

时间复杂度：O(1)

指定位置插入​（用户代码中 push(int f_id, int id, string name)）：

inline void MyClass::push(int f_id,int id,string name)
{
	if (isempty()) {
		top = make_shared<MyClass::student>( id, name,nullptr,nullptr);
		tail = top;
	}
	else
	{
		auto resource = find(f_id);
		auto &pre = resource.pre;
		auto &cur = resource.cur;

		//如果目标节点不存在，就把新节点插入到尾部，新节点的前指针指向原链表的尾节点tail
		if (cur == nullptr) {
			// 插入到尾部
			auto new_node = std::make_shared<student>(id, name, tail, nullptr);
			tail->next = new_node;
			tail = new_node;
		}
		//插入到中间节点前
		else {
			// 在目标节点前插入新节点，新节点的前指针指向前节点pre,新节点的next指针指向后节点cur
			auto new_node = std::make_shared<student>(id, name, pre, cur);
			if (pre) {
				pre->next = new_node;
			}
			else {
				top = new_node; // 更新头指针
			}
			cur->pre = new_node; // 更新目标节点的前驱
		}
	}
	
}

 时间复杂度：查找O(n) + 插入O(1)

3.2 删除操作

指定节点删除​（用户代码中 pop(int id)）：

void pop(int id) {
    auto res = find(id);
    if (res.cur) {
        if (res.pre) res.pre->next = res.cur->next;
        else top = res.cur->next; // 删除头节点
        
       res.cur->next) 
            res.cur->next->pre = res.pre; 
        else 
            tail = res.pre; // 删除尾节点
    }
}

 时间复杂度：查找O(n) + 删除O(1)

3.3 遍历与查找

遍历函数：

void MyClass::printlist()
{
	if (isempty())
	{
		cout << "链表为空" << endl;
		return;
	}
	
		auto str = top;//注意这里必须使用临时变量遍历链表，str前面加上&会使str成为top的引用，在经过str = str->next;会破坏链表
		while (str!= nullptr)
		{
			cout << str->m_id << ":" << str->m_name << " <-> ";
			str = str->next;
		} 
		cout << "NULL" << endl;
		
		
	
}

 查找函数：

MyClass::FindResult MyClass::find(int id)
{
	shared_ptr<student> cur = top;
	shared_ptr<student> preptr = shared_ptr<student>(nullptr);
	while (cur!=nullptr)
	{
		if (cur->m_id == id) {
			return { preptr,cur };
		}
		else
		{
			preptr = cur;
			cur = cur->next;
		}
	}
	return { nullptr,nullptr };
}

时间复杂度对比

 典型应用场景

1. ​文本编辑器：支持移动
2. ​浏览器历史记录：前进/后退功能
3. ​音乐播放列表：上一曲/下一曲切换
4. ​撤销重做系统：操作记录的双向遍历

STL对双链表的支持

C++标准模板库（STL）通过 ​**std::list** 容器提供对双向链表的原生支持。以下是其核心特性和使用场景的全面分析：

一、底层实现

std::list 是严格的双向链表：

• ​节点结构：每个节点包含：

  struct Node {
      T data;          // 存储数据
      Node* prev;      // 指向前驱节点
      Node* next;      // 指向后继节点
  };

• 内存管理：STL内部通过自定义分配器管理内存，自动处理节点的创建和销毁，​无需手动管理指针。
• ​无哨兵节点：部分实现可能使用头尾哨兵节点简化边界条件处理。

二、核心特性

1. 时间复杂度

2. 迭代器

• ​双向迭代器：支持前向（++）和后向（--）遍历。

  for (auto it = myList.begin(); it != myList.end(); ++it) { /* 前向 */ }
  for (auto rit = myList.rbegin(); rit != myList.rend(); ++rit) { /* 反向 */ }

• 稳定性：插入/删除操作不会使其他迭代器失效（除非指向被删节点）。

3. 内存分配

• ​非连续存储：节点分散在内存中，无预留空间（与vector相反）。
• ​缓存不友好：频繁跳转访问可能导致性能下降。

三、关键成员函数

1. 插入操作

2. 删除操作

3. 高级操作

四、与其它容器的对比

五、适用场景

1. ​推荐使用 std::list 的场景

• ​频繁在任意位置插入/删除
  例如：实时记录系统的事件队列（需动态调整顺序）。
• ​需要稳定迭代器
  例如：游戏引擎中遍历并修改场景对象链表。
• ​大对象存储
  避免vector扩容时的复制开销。

2. ​应避免使用 std::list 的场景

• ​需要随机访问
  例如：科学计算中的矩阵操作。
• ​内存敏感场景
  例如：嵌入式系统开发中需最小化内存占用。
• ​高频缓存访问
  例如：实时图像处理中的像素操作。

六.性能优化建议

1. ​优先使用 std::list 的成员函数

   • sort() 比 std::sort() 更高效（因链表特性优化）：

     std::list<int> lst = {...};
     lst.sort(); // 正确方式（O(n log n)）
     // std::sort(lst.begin(), lst.end()); // 错误！需要随机访问迭代器

   • ​避免频繁的 size() 调用

     std::list::size() 的复杂度为O(n)（C++11前），C++11后为O(1)，但实现可能仍有差异。

              3.​使用 emplace 避免拷贝 

struct BigObj { BigObj(int a, double b) {...} };
std::list<BigObj> list;
list.emplace_back(42, 3.14); // 直接在节点构造对象，无需拷贝