單鏈表的插入操作是核心功能之一，根據插入位置可分為頭部插入（已實現）、尾部插入（已實現）和指定位置插入（核心擴展）。以下重點講解指定索引位置插入的實現邏輯、代碼細節及注意事項。

一、插入操作的核心邏輯

指定索引插入的目標是：在鏈表的第index個位置（索引從 0 開始）插入新節點，原索引index及之後的節點後移。步驟拆解：

  1. 檢查索引合法性（index < 0 || index > size，注意允許index == size，即尾部插入）；
  2. 找到插入位置的前驅節點（prev）；
  3. 創建新節點，調整指針指向：
  • 新節點的next指向前驅節點的next（即原index位置的節點）；
  • 前驅節點的next指向新節點；
  1. 鏈表長度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. 長度加1
        size++;
        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; // false
    cout << "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 -> nullptr

    return 0;
}

三、關鍵細節解析

  1. 索引合法性
  • 允許的索引範圍：0 ≤ index ≤ size（index=size對應尾部插入，index=0對應頭部插入）；
  • 若index < 0或index > size，直接返回false，避免越界訪問。
  1. 前驅節點的查找
  • 從哨兵頭節點head開始遍歷index次，最終prev指向插入位置的前一個節點；
  • 例如：插入index=1時，prev指向第 0 個節點（而非第 1 個），確保指針調整邏輯統一。
  1. 指針調整順序
  • 必須先讓newNode->next = prev->next，再讓prev->next = newNode；
  • 若順序顛倒，會導致原prev->next的節點地址丟失，鏈表斷裂。
  1. 複用優化
  • 原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;
            // 若插入到尾部，更新tail
            if (curr == tail) {
                tail = newNode;
            }
            size++;
            return true;
        }
        curr = curr->next;
    }
    return false; // 未找到target
}

綜上，單鏈表插入的核心是找到前驅節點 + 正確調整指針，不同插入位置的邏輯可統一到insert方法中，通過索引控制；優化尾指針可顯著提升尾部插入效率，是實際開發中常用的優化手段。