C 語言數組插入元素：後續元素向後移動

算法步驟

在已排序數組指定位置插入新元素，保持有序：

1. 從數組末尾向前遍歷至插入位置。
2. 每個元素向後移動一位：arr[i+1] = arr[i]。
3. 在空出位置放入新元素。

代碼實現

void insert(int arr[], int *n, int pos, int val) {
    // pos 為 0-based 插入索引，合法性檢查省略
    for (int i = *n; i > pos; i--) {
        arr[i] = arr[i-1];
    }
    arr[pos] = val;
    (*n)++;
}

鏈表優勢

若使用鏈表，只需修改前驅節點 next 指向新節點，新節點 next 指向原後繼節點，無需移動數據，時間 O(1)。

適用場景

• 數組：數據量小、頻繁隨機訪問、插入較少。
• 鏈表：頻繁插入刪除、不需隨機訪問。

選擇合適數據結構，從算法層面優化性能。