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

C語言雙向鏈表完整實現：建立、插入、刪除與雙向遍歷

編輯：關於C

節點結構設計

typedef struct DoubleLinkedList {
    int data;
    struct DoubleLinkedList *pre;
    struct DoubleLinkedList *next;
} DlinkedList_Node;

核心操作函數詳解

1. 建立鏈表（尾插法，以 65535 為結束標記）

DlinkedList_Node* createDLink() {
    DlinkedList_Node *head, *p, *s;
    int x;
    head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); // 虛擬頭節點
    p = head;
    while (1) {
        printf("please input the data: ");
        scanf("%d", &x);
        if (x != 65535) {
            s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));
            s->data = x;
            s->pre = p;
            p->next = s;
            p = s;
        } else {
            printf("\n數據輸入結束\n");
            break;
        }
    }
    p->next = NULL;
    head = head->next;      // 跳過虛擬頭節點
    if (head) head->pre = NULL;
    return head;
}

2. 雙向遍歷輸出

void printDLink(DlinkedList_Node *head) {
    DlinkedList_Node *p = head, *s = NULL;
    printf("正序輸出雙向鏈表：\n");
    while (p) {
        printf("%d ", p->data);
        s = p;           // 記住尾節點
        p = p->next;
    }
    printf("\n逆序輸出雙向鏈表：\n");
    while (s) {
        printf("%d ", s->data);
        s = s->pre;
    }
    printf("\n\n");
}

3. 刪除指定值節點

DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head, int val) {
    DlinkedList_Node *p = head;
    if (!p) return NULL;
    
    // 刪除頭節點
    if (p->data == val) {
        head = p->next;
        if (head) head->pre = NULL;
        free(p);
        return head;
    }
    
    // 刪除中間/尾節點
    while (p) {
        if (p->data == val) {
            p->pre->next = p->next;
            if (p->next) p->next->pre = p->pre;
            free(p);
            return head;
        }
        p = p->next;
    }
    printf("沒有找到想要刪除的數據\n");
    return head;
}

4. 有序插入節點（按 data 升序）

DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head, int val) {
    DlinkedList_Node *p = head, *temp = malloc(sizeof(DlinkedList_Node));
    temp->data = val;
    
    // 插入頭部
    if (!head || val < head->data) {
        temp->next = head;
        temp->pre = NULL;
        if (head) head->pre = temp;
        return temp;
    }
    
    // 尋找插入位置
    while (p->next && val > p->next->data) p = p->next;
    
    // 插入中間
    if (p->next) {
        temp->next = p->next;
        temp->pre = p;
        p->next->pre = temp;
        p->next = temp;
    } 
    // 插入尾部
    else {
        p->next = temp;
        temp->pre = p;
        temp->next = NULL;
    }
    return head;
}

測試主程式與輸出示例

int main() {
    DlinkedList_Node *head = createDLink();
    printDLink(head);
    head = insertDlinkedList_Node(head, 1012);
    head = deleteDlinkedList_Node(head, 1991);
    printDLink(head);
    return 0;
}

/* 運行結果示例：
正序輸出：1991 1992 2013 2014 512 420
逆序輸出：420 512 2014 2013 1992 1991
插入 1012、刪除 1991 後：
正序輸出：1012 1992 2013 2014 512 420
逆序輸出：420 512 2014 2013 1992 1012
*/