C++如何实现单向链表_C++手写链表增删改查底层代码【手撕】

因面试算法题需暴露指针细节，std::list封装过深；手写可掌握内存布局、空链表处理、nullptr检查及悬垂指针防范等核心要点。

为什么不能直接用 std::list 而要手写单向链表

因为面试、笔试、算法课作业或嵌入式环境里，常要求你暴露指针操作细节，std::list 封装太深，无法体现内存布局和节点管理逻辑。手写能看清：节点怎么分配、头指针怎么维护、空链表边界怎么处理。

常见错误是忽略 nullptr 判定，比如在空链表上调用 deleteHead() 却没检查 head == nullptr，直接解引用导致段错误。

• 所有插入/删除前，先判断 head 是否为空
• 删除节点后必须将原指针置为 nullptr（尤其在析构或清空时）
• 不要在遍历中释放当前节点后还访问 current->next —— 应该先保存 next = current->next，再 delete current

node 结构体和 LinkedList 类的基本骨架

单向链表只需一个 next 指针，Node 通常定义为内部结构体；LinkedList 管理 head，不存 size 是常见简化做法（加 size 成员可避免每次查长度都遍历）。

struct Node {     int val;     Node* next;     Node(int x) : val(x), next(nullptr) {} }; 
class LinkedList { private: Node* head; public: LinkedList() : head(nullptr) {} ~LinkedList() { clear(); } void clear(); // 其他接口... };

注意：Node 构造函数显式初始化 next 为 nullptr，否则野指针风险极高；LinkedList 析构调用 clear()，避免资源泄漏。

立即学习“C++免费学习笔记（深入）”；

插入操作：头插、尾插、按索引插的差异点

头插最简单，时间复杂度 O(1)；尾插需遍历到末尾，O(n)，除非额外维护 tail 指针；按索引插入必须处理越界（索引 Length）。

• 头插：newNode->next = head; head = newNode;
• 尾插：特判空链表（head == nullptr），否则循环到 cur->next == nullptr 再接上
• 按索引插：先用辅助函数 getNodeAt(int index) 获取前驱节点（不是目标节点！），对 index=0 要特殊处理为头插

容易踩坑的是：插入时忘记更新前驱的 next，或者把新节点插到了错误位置（比如本该插在第 i 个位置，却插在了第 i+1 个）。

删除与查找：如何安全释放节点并避免悬垂指针

删除节点本质是「跳过它」：让前驱的 next 指向被删节点的 next，再 delete 它。关键在于拿到前驱 —— 查找时必须多走一步，或用双指针法。

• 删头节点：Node* tmp = head; head = head->next; delete tmp;，别忘了 tmp = nullptr（虽非必须，但习惯好）
• 删指定值：遍历时用 prev 和 curr，找到后 prev->next = curr->next，再 delete curr
• 按索引删：同样依赖前驱，index=0 单独处理；index 越界直接 return

查找函数返回 Node* 本身不危险，但调用方若保存了该指针，在后续删除操作后继续使用，就是典型悬垂指针 —— 手写链表里，这类 bug 很难被编译器捕获，只能靠逻辑严谨性预防。

真正麻烦的是多线程环境下的 delete —— 但手撕题一般不考，先确保单线程下每个 new 都有唯一对应的 delete，且无重复释放。