常德市网站建设_网站建设公司_CSS_seo优化

单链表的插入操作是核心功能之一，根据插入位置可分为头部插入（已实现）、尾部插入（已实现）和指定位置插入（核心扩展）。以下重点讲解指定索引位置插入的实现逻辑、代码细节及注意事项。

一、插入操作的核心逻辑

指定索引插入的目标是：在链表的第index个位置（索引从 0 开始）插入新节点，原索引index及之后的节点后移。步骤拆解：

1. 检查索引合法性（index < 0 || index > size，注意允许index == size，即尾部插入）；
2. 找到插入位置的前驱节点（prev）；
3. 创建新节点，调整指针指向：
   • 新节点的next指向前驱节点的next（即原index位置的节点）；
   • 前驱节点的next指向新节点；
4. 链表长度size加 1。

二、完整插入实现代码

基于之前的单链表类，新增insert方法，并补充测试代码：

cpp

 

运行

 

 

 

 

#include <iostream>
#include <stdexcept>
using namespace std;// 节点结构体（复用）
template <typename T>
struct ListNode {T data;ListNode<T>* next;ListNode(T val) : data(val), next(nullptr) {}
};// 单链表类（新增insert方法）
template <typename T>
class SinglyLinkedList {
private:ListNode<T>* head;int size;public:SinglyLinkedList() {head = new ListNode<T>(T());size = 0;}~SinglyLinkedList() {clear();delete head;head = nullptr;}// 清空链表（复用）void clear() {ListNode<T>* curr = head->next;while (curr != nullptr) {ListNode<T>* temp = curr;curr = curr->next;delete temp;}head->next = nullptr;size = 0;}// 核心：指定索引插入元素bool insert(int index, T val) {// 索引合法性检查：允许index=size（尾部插入）if (index < 0 || index > size) {return false; // 插入失败}// 1. 找到插入位置的前驱节点ListNode<T>* prev = head;for (int i = 0; i < index; i++) {prev = prev->next;}// 2. 创建新节点并调整指针ListNode<T>* newNode = new ListNode<T>(val);newNode->next = prev->next; // 新节点指向原index位置的节点prev->next = newNode;       // 前驱节点指向新节点// 3. 长度加1size++;return true; // 插入成功}// 复用原有方法：push_back/push_front/print/getSize等void push_back(T val) { insert(size, val); } // 复用insert实现尾部插入void push_front(T val) { insert(0, val); }   // 复用insert实现头部插入int getSize() const { return size; }void print() const {ListNode<T>* curr = head->next;if (curr == nullptr) {cout << "Linked list is empty" << endl;return;}cout << "Linked list: ";while (curr != nullptr) {cout << curr->data << " -> ";curr = curr->next;}cout << "nullptr" << endl;}
};// 测试插入操作
int main() {SinglyLinkedList<int> list;// 1. 头部插入（index=0）list.insert(0, 10);list.print(); // 10 -> nullptr// 2. 尾部插入（index=1，等于当前size=1）list.insert(1, 30);list.print(); // 10 -> 30 -> nullptr// 3. 中间插入（index=1，在10和30之间插入20）list.insert(1, 20);list.print(); // 10 -> 20 -> 30 -> nullptr// 4. 非法索引插入（index=-1 或 index=4）cout << "Insert at index -1: " << boolalpha << list.insert(-1, 5) << endl; // falsecout << "Insert at index 4: " << boolalpha << list.insert(4, 40) << endl; // false// 5. 复用push_front/push_back（底层调用insert）list.push_front(5);list.push_back(40);list.print(); // 5 -> 10 -> 20 -> 30 -> 40 -> nullptrreturn 0;
}

 

三、关键细节解析

1. 索引合法性
   • 允许的索引范围：0 ≤ index ≤ size（index=size对应尾部插入，index=0对应头部插入）；
   • 若index < 0或index > size，直接返回false，避免越界访问。
2. 前驱节点的查找
   • 从哨兵头节点head开始遍历index次，最终prev指向插入位置的前一个节点；
   • 例如：插入index=1时，prev指向第 0 个节点（而非第 1 个），确保指针调整逻辑统一。
3. 指针调整顺序
   • 必须先让newNode->next = prev->next，再让prev->next = newNode；
   • 若顺序颠倒，会导致原prev->next的节点地址丢失，链表断裂。
4. 复用优化
   • 原push_front和push_back可直接复用insert方法，减少代码冗余：
     • push_front(val) → insert(0, val)；
     • push_back(val) → insert(size, val)。

四、时间复杂度分析

插入位置	时间复杂度	说明
头部插入（0）	O(1)	无需遍历，直接调整头节点
尾部插入（size）	O(n)	需遍历到最后一个节点
中间插入	O(n)	需遍历到指定索引的前驱节点

优化方向：若添加tail尾指针，尾部插入的时间复杂度可降为O(1)，示例如下：

cpp

 

运行

// 新增尾指针
template <typename T>
class SinglyLinkedList {
private:ListNode<T>* head;ListNode<T>* tail; // 尾指针int size;public:SinglyLinkedList() {head = new ListNode<T>(T());tail = head; // 初始时尾指针指向头节点size = 0;}// 优化尾部插入：O(1)void push_back(T val) {ListNode<T>* newNode = new ListNode<T>(val);tail->next = newNode;tail = newNode; // 尾指针后移size++;}// 插入方法需同步维护tail指针（若插入到尾部）bool insert(int index, T val) {if (index < 0 || index > size) return false;ListNode<T>* prev = head;for (int i = 0; i < index; i++) {prev = prev->next;}ListNode<T>* newNode = new ListNode<T>(val);newNode->next = prev->next;prev->next = newNode;// 若插入到尾部，更新tail指针if (index == size) {tail = newNode;}size++;return true;}
};

 

五、常见错误与避坑

1. 空指针访问：未检查prev是否为nullptr（但哨兵头节点保证了prev至少指向head）；
2. 内存泄漏：创建新节点后若插入失败，需及时delete新节点（上述代码中索引合法才创建节点，无需额外处理）；
3. 指针顺序错误：先改prev->next再改newNode->next，会导致链表断裂；
4. size 未更新：插入成功后忘记size++，导致链表长度与实际不符。

六、扩展场景：按值插入（而非索引）

若需求是 “在某个值的节点后插入新节点”，可实现如下方法：

cpp

 

运行

// 在值为target的第一个节点后插入val
bool insertAfter(T target, T val) {ListNode<T>* curr = head->next;while (curr != nullptr) {if (curr->data == target) {ListNode<T>* newNode = new ListNode<T>(val);newNode->next = curr->next;curr->next = newNode;// 若插入到尾部，更新tailif (curr == tail) {tail = newNode;}size++;return true;}curr = curr->next;}return false; // 未找到target
}

 

综上，单链表插入的核心是找到前驱节点 + 正确调整指针，不同插入位置的逻辑可统一到insert方法中，通过索引控制；优化尾指针可显著提升尾部插入效率，是实际开发中常用的优化手段。