算法與數(shù)據(jù)結(jié)構(gòu)04（基礎(chǔ)篇）——雙鏈表與雙向循環(huán)鏈表

原來長這樣

我們在第一篇《算法與數(shù)據(jù)結(jié)構(gòu)》里用到的鏈表就是雙鏈表。但是在本篇博客，換一個角度，以功能操作（創(chuàng)建、插入、刪除、更新、遍歷等）為切入點，橫向比較 雙向鏈表 雙向循環(huán)鏈表

鏈表結(jié)構(gòu)對比

節(jié)點相同

兩種鏈表的節(jié)點

首尾節(jié)點前后指向不同，注意：下圖中黑線表示指向節(jié)點，不是節(jié)點的data部分
image

創(chuàng)建方式對比

只有頭節(jié)點

區(qū)別：循環(huán)鏈表里，頭指針前后均指向自己

創(chuàng)建雙向鏈表

/// 創(chuàng)建鏈表
Status CreateList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    
    return OK;
}

創(chuàng)建雙向循環(huán)鏈表

/// 創(chuàng)建鏈表
Status CreateList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    
    (*L)->prior = *L;   // 這里和上面不一樣，指向自己，
    (*L)->next = *L;    // 這里和上面不一樣，指向自己
    
    /*
    * 和雙鏈表的稍微差異處理之后，只有頭節(jié)點自己也可以是一個循環(huán)
    */
    
    return OK;
}

插入節(jié)點對比

在任意位置插入節(jié)點

（上圖為兩種鏈表的插入任意位置）

雙鏈表的插入

p：插入位置前的節(jié)點 q：插入位置后的節(jié)點 s：新節(jié)點

  1. 創(chuàng)建新節(jié)點s
  2. 找到插入位置前的一個節(jié)點p
  3. 判斷是不是插入在尾節(jié)點之后
  • 是，新節(jié)點s的prior指向尾節(jié)點p，尾節(jié)點p的next指向新節(jié)點s
  • 不是插入在尾節(jié)點之后，
    1. p的next節(jié)點q的prior 指向新節(jié)點s
    2. 新節(jié)點s的next指向q
    3. 新節(jié)點s的prior指向p
    4. p的next指向s
  1. over
Status ListInsert(LinkList *L, int place , ElemType v)
{
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 新節(jié)點
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;
    
    // 找到插入前的節(jié)點
    LinkList p = *L;
    // 找到插入位置 (place 位置的前一個結(jié)點)
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    
    // 注意：因為有頭節(jié)點，所有新節(jié)點一定是在頭節(jié)點之后，所以頭指針L，一定指向頭節(jié)點
    
    if (p->next == NULL)
    {
        p->next = temp;
        temp->prior = p;
    }
    else
    {
        // 1、p的后一個節(jié)點的prior指向新節(jié)點temp
        p->next->prior = temp;
        // 2、新節(jié)點temp的next指向p的后一個節(jié)點
        temp->next = p->next;
        // 3、新節(jié)點temp的prior指向p
        temp->prior = p;
        // 4、p的next指向新節(jié)點temp
        p->next = temp;
    }
    
    return 1;
}

雙向循環(huán)鏈表的插入

p：插入位置前的節(jié)點 q：插入位置后的節(jié)點 s：新節(jié)點

  1. 創(chuàng)建新節(jié)點s
  2. 找到插入位置前的一個節(jié)點p
  3. 判斷是不是插入在尾節(jié)點之后
  • p的next節(jié)點q的prior 指向新節(jié)點s
  • 新節(jié)點s的next指向q
  • 新節(jié)點s的prior指向p
  • p的next指向s
  1. over

    為什么比雙鏈表少判斷是不是尾節(jié)點？
    因為有頭節(jié)點的存在，并且是個循環(huán)，即使插入在尾節(jié)點，也和任意位置插入一樣
Status ListInsert(LinkList *L, int place , ElemType v)
{
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 新節(jié)點
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;
    
    // 找到插入前的節(jié)點
    // 這里為什么和下面刪除、替換的p=*L->next不同，而是p=*L：我們要找到place位置的前一個節(jié)點，所以要默認(rèn)從頭節(jié)點開始
    LinkList p = *L;
    // 找到插入位置 (place 位置的前一個結(jié)點)
    for (int i = 1; i < place; i++) {
        if (p->next == (*L))
            break; // 說明此時P已經(jīng)是尾節(jié)點
        p = p->next;
    }
        
    temp->next = p->next;
    temp->next->prior = temp;

    p->next = temp;
    temp->prior = p;
    
    return OK;
}

區(qū)別：雙向鏈表多了尾節(jié)點后插入操作

刪除節(jié)點對比

刪除任意位置的節(jié)點

（上圖為兩種鏈表刪除任意位置）

雙鏈表的刪除

老話重提，注意是不是刪除尾節(jié)點，因為尾節(jié)點的next需要為null

Status ListDelete(LinkList *L, int place, ElemType *v)
{
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 找到place位置的節(jié)點
    LinkList p = (*L)->next; // 從首元節(jié)點開始
    
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    
    *v = p->data;
    
    if (p->next == NULL)
    {
        // p是尾節(jié)點
        // 將p的前一個節(jié)點變成尾節(jié)點
        p->prior->next = NULL;
        // 釋放p
        free(p);
    }
    else
    {
        // p是任意位置的節(jié)點
        // 1、將p的后一個節(jié)點指向p的前一個節(jié)點
        p->next->prior = p->prior;
        // 2、將p的前一個節(jié)點指向p的后一個節(jié)點
        p->prior->next = p->next;
        // 3、釋放
        free(p);
    }
    
    return 1;
}

雙向循環(huán)鏈表的刪除

循環(huán)鏈表不需要考慮是不是尾節(jié)點，因為他有下一個節(jié)點，把下一個節(jié)點和他前一個節(jié)點建立互相指向，釋放自己。為什么在本篇博客中沒有提及頭指針的變更？ 因為我們有頭節(jié)點。

Status ListDelete(LinkList *L, int place, ElemType *v)
{
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 找到place位置的節(jié)點
    LinkList p = (*L)->next; // 從首元節(jié)點開始
    
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    
    *v = p->data;
    
    if (p->next == NULL)
    {
        // p是尾節(jié)點
        // 將p的前一個節(jié)點變成尾節(jié)點
        p->prior->next = NULL;
        // 釋放p
        free(p);
    }
    else
    {
        // p是任意位置的節(jié)點
        // 1、將p的后一個節(jié)點指向p的前一個節(jié)點
        p->next->prior = p->prior;
        // 2、將p的前一個節(jié)點指向p的后一個節(jié)點
        p->prior->next = p->next;
        // 3、釋放
        free(p);
    }
    
    return 1;
}

區(qū)別：雙鏈表多了尾節(jié)點刪除處理

更新節(jié)點對比

  1. 找到要操作的節(jié)點
  2. 更新data


兩種鏈表步驟一樣
圖片可以參考上面刪除的圖片，在找到后，僅更改節(jié)點data即可

Status ListReplace(LinkList *L, int place, ElemType newValue)
{
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 找到place位置的節(jié)點
    LinkList p = (*L)->next; // 從首元節(jié)點開始
    
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    
    p->data = newValue;
    
    return 1;
}

查找指定位置的節(jié)點

按照上文替換、刪除的方式找到要操作的place位置的節(jié)點。
兩種鏈表在不涉及更改操作，單純的執(zhí)行查找時，是一樣的

/// 查找節(jié)點
/// @param L 鏈表（沒有使用指針，所以L是拷貝的鏈表，不是原鏈表！?。。?/// @param place 查找的位置
/// @param node 要查找的節(jié)點（C語言不好的同學(xué)，這里*node實際是存儲節(jié)點地址的指針，與 function(LinkList *L) 一樣，用了雙指針）
Status FindNode(LinkList L, int place, LinkList *node)
{
    if (L == NULL) {
        printf("打印的雙向循環(huán)鏈表為空!\n\n");
        return ERROR;
    }
    
    // 有頭節(jié)點 所以插入位置不能是<1
    if (place < 1) return ERROR;
    
    // 找到place位置的節(jié)點
    LinkList p = L->next; // 從首元節(jié)點開始
    
    int i = 1;
    
    for (; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    
    if (i < place) {
        printf("位置超出鏈表長度！");
        return ERROR;
    }
    
    *node = p;
    
    return OK;
}

主函數(shù)

int main(int argc, const char * argv[]) {
    
    LinkList L;
    int place, value;
    
    CreateList(&L);
    DisplayList(L);
    
    /*
    * 
    * 。。。。。。。。
    * ListInsert（）插入測試數(shù)據(jù)
    */
    
    printf("查詢節(jié)點，請輸入查詢位置:\n");
    
    LinkList node = NULL;
    scanf("%d", &place);
    FindNode(L, place, &node);
    if (node != NULL) {
        printf("節(jié)點：%p, data：%d\n",node,node->data);
    }
}
查找輸出結(jié)果
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容