C語言實現雙向非循環鏈表（不帶頭結點）的節點插入

C語言實現雙向非循環鏈表（不帶頭結點）的節點插入

我在之前一篇博客中《C語言實現雙向非循環鏈表的逆序打印》講到了如何逆序輸出一個雙向非循環鏈表，讓我們對這種鏈表類型有了理性的認識。今天我們要來實現的是對雙向非循環鏈表進行節點的插入。大家可以和《C語言實現單鏈表節點的插入》單鏈表的節點插入對比著學習。代碼上傳至 https://github.com/chenyufeng1991/InsertDoubleLinkedList 。

核心代碼如下：

Node *InsertList(Node *pNode,int pos,int x){

    int i = 1;
    int size = sizeList(pNode);
    Node *pMove;
    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;
    pInsert->next = NULL;
    pInsert->prior = NULL;

    pMove = pNode;

    //首先檢查pos值是否合法
    if (pos < 0 || pos > size) {
        printf("%s函數執行，輸入的pos值非法，插入節點失敗\n",__FUNCTION__);
        return pNode;
    }

    //原鏈表是一個空鏈表，在第一個位置插入節點
    if (pNode == NULL && pos == 0) {
        pNode = pInsert;
        printf("%s函數執行，在pos=%d位置插入x=%d節點成功\n",__FUNCTION__,pos,x);
        return pNode;
    }

    //單獨考慮插入到第一個節點和最後一個節點
    if (pos == 0) {
        //插入的節點作為第一個節點
        pInsert->next = pNode;
        pNode->prior = pInsert;
        pNode = pInsert;
    }else if(pos == size){
        //插入的節點是最後一個節點
        while (pMove->next != NULL) {
            pMove = pMove->next;
        }
        pMove->next = pInsert;
        pInsert->prior = pMove;
    }else{
        while (pMove != NULL) {
            if (i == pos) {

                //找到該位置，請注意下面的鏈表的鏈接順序很重要
                pInsert->next = pMove->next;
                pMove->next->prior = pInsert;
                pInsert->prior = pMove;
                pMove->next = pInsert;
                break;
            }else{
                //繼續找下一個節點
                i++;
                pMove = pMove->next;
            }
        }
    }

    printf("%s函數執行，在pos=%d位置插入x=%d節點成功\n",__FUNCTION__,pos,x);

    return pNode;
}