您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言雙向鏈表任意位置插入：帶頭尾哨兵節點的統一邏輯

編輯：關於C

插入位置定義

pos = 0 表示頭節點之後（第一個有效位置），pos = 1 表示第二個，以此類推。若 pos == length 等價於尾插。

統一插入邏輯


bool List_Insert(DList *L, int pos, int val) {
    Node *p = L->head;
    for (int i = 0; i < pos && p != L->tail; ++i) p = p->next;
    if (p == L->tail) return false;  // 越界

    Node *n = malloc(sizeof(Node));
    n->element = val; n->prior = n->next = NULL;

    /* 關鍵：先連新節點，再斷舊連 */
    n->next = p->next;
    p->next->prior = n;
    p->next = n;
    n->prior = p;
    return true;
}

指針操作順序圖解

插入前： p <-> p->next
步驟1： n->next = p->next
步驟2： p->next->prior = n
步驟3： p->next = n
步驟4： n->prior = p
結果： p <-> n <-> p->next

此順序保證任意時刻鏈表結構完整，即使中途發生中斷/異常也不會產生斷鏈。

特殊情況自動覆蓋

測試用例


int main(void) {
    DList L; List_Init(&L);
    List_PushBack(&L, 10); List_PushBack(&L, 30); // 10 30
    List_Insert(&L, 1, 20);    // pos=1 → 10 20 30
    List_PrintForward(&L);
    List_Insert(&L, 0, 5);     // 頭插 5
    List_PrintForward(&L);     // 5 10 20 30
    List_Insert(&L, 4, 40);    // 尾插 40
    List_PrintForward(&L);     // 5 10 20 30 40
    free(L.head); free(L.tail);
    return 0;
}