如何用c++实现一个链表 单链表的创建、插入和删除【数据结构】
C++单链表需定义节点结构和链表类，手动管理内存；核心操作包括头插（O(1)）、指定位置插入（需遍历）、按值删除（分头/中/尾处理），并需实现析构函数防止内存泄漏。
用 C++ 实现单链表，核心是定义节点结构、管理头指针，并封装插入、删除等操作。不需要依赖 STL 容器，手动管理内存更利于理解数据结构本质。
定义节点结构和链表类
每个节点包含数据域和指向下一节点的指针；链表类维护头指针（可为 nullptr 表示空表）：
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class LinkedList {
private:
ListNode* head;
public:
LinkedList() : head(nullptr) {}
~LinkedList(); // 后续需实现析构释放内存
};
在链表头部插入节点（最简单）
时间复杂度 O(1)，适合频繁在开头增删的场景：
- 新建节点，赋值
- 新节点 next 指向原 head
- 更新 head 指向新节点
void insertAtHead(int value) {
ListNode* newNode = new ListNode(value);
newNode->next = head;
head = newNode;
}在指定位置插入（如第 i 个位置，从 0 开始）
需遍历到前一个节点，注意边界检查（i 小于 0 或超过长度时可忽略或报错）：
- i == 0 等价于头插，直接调用 insertAtHead
- 遍历至第 i−1 个节点（prev），若 prev 为 nullptr 说明越界
- 新建节点，接在 prev 后面：newNode→next = prev→next；prev→next = newNode
void insertAt(int index, int value) {
if (index == 0) {
insertAtHead(value);
return;
}
ListNode* prev = head;
for (int i = 0; i < index - 1 && prev != nullptr; ++i) {
prev = prev->next;
}
if (prev == nullptr) return; // 位置无效
ListNode* newNode = new ListNode(value);
newNode->next = prev->next;
prev->next = newNode;
}删除节点（按值或按位置）
以按值删除为例（删第一个匹配的节点），需处理三种情况：
- 空链表 → 直接返回
- 头节点即目标 → 更新 head，并 delete 原头节点
- 中间或尾部节点 → 找到前驱 prev，跳过目标节点，并释放内存
void deleteByValue(int value) {
if (!head) return;
if (head->val == value) {
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
ListNode* prev = head;
while (prev->next && prev->next->val != value) {
prev = prev->next;
}
if (prev->next) {
ListNode* toDelete = prev->next;
prev->next = toDelete->next;
delete toDelete;
}
}
}
ListNode* prev = head;
while (prev->next && prev->next->val != value) {
prev = prev->next;
}
if (prev->next) {
ListNode* toDelete = prev->next;
prev->next = toDelete->next;
delete toDelete;
}
}补充：遍历与析构（避免内存泄漏）
打印链表用于调试：
void print() {
ListNode* cur = head;
while (cur) {
std::cout << cur->val;
if (cur->next) std::cout << " → ";
cur = cur->next;
}
std::cout << std::endl;
}析构函数应逐个释放节点：
LinkedList::~LinkedList() {
while (head) {
ListNode* temp = head;
head = head->next;
delete temp;
}
}不复杂但容易忽略
