本章目標

0.雙向鏈表的基本結構
1.雙向鏈表的初始化
2.頭插尾插
3.頭刪尾刪
4.查找與打印
5.在指定位置之前插入數據/在指定位置之后插入數據
6.在指定位置之前刪除數據/在指定位置之后刪除數據
7.銷毀鏈表

0.雙向鏈表的基本結構

本章所實現的雙向鏈表是雙向循環帶頭鏈表,是stl中list容器的結構一致.

它有一個真正意義上的頭結點,但該結點并不存儲數據,我們一般管它叫做哨兵位.
它與單鏈表不同的是它的結點中有兩個指向結點的指針,分別是前一個結點和下一個結點的指針.

typedef int listdatatype;struct listNode
{listdatatype data;struct listNode* prev;struct listNode* next;
};
typedef struct listNode listNode;

我們把數據類型和鏈表結點進行typedef方便后面我們進行實現該鏈表的函數.

1.雙向鏈表的初始化

與單鏈表不同的是,每當我們創建鏈表的時候,需要創建一個新的哨兵位,然后才能將數據進行插入,刪除操作.既然要創建一個新的結點,我們就需要將該邏輯進行分裝,方便后續使用.

listNode* buyNode(listdatatype x)
{listNode* newnode = (listNode*)malloc(sizeof(listNode));if (!newnode){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

對于頭節點的創建我們有兩種方法,第一個中是在函數體內實現,另一種是傳過來一個指針進行操作,如果時第二種方法,我們就需要傳址,需要二級指針,如果傳一級指針相當于傳值操作,當函數結束的時候,函數棧幀會自動銷毀,那么外面的指針就成為野指針了.

listNode* listinit()
{listNode* newnode = buyNode(-1);return newnode;}void listintalpha(listNode **pphead)
{*pphead = buyNode(-1);
}

因為該結點時頭節點,并不存儲數據,所以在創建結點時給的參數可以隨便給.

2.頭插尾插

2.1頭插

對于頭插來說,我們需要操作三個部分,哨兵位,哨兵位的下一個結點,newnode.
我們先討論newndoe,要讓它的prev指向哨兵位,next指向哨兵位的下一個結點,該操作時不會對鏈表產生影響的.我可以隨意他們的順序.
接著讓哨兵位的下一個結點的prev指向newnode,然后再讓哨兵位的next指向newnode.
該操作是有順序要求的,如果先讓哨兵位的next指向newnode,會找不到后面的鏈表,當然我們也可以提前保存一份,這樣就可以隨意操作了.

void listpushfront(listNode* phead, listdatatype x)
{assert(phead);listNode* newnode = buyNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}

2.2.尾插

對于尾插來說,我們要操作的結點一共有三個,最后一個結點,哨兵位,newnode.
我們先操作對鏈表沒有影響newnode,讓它的prev的結點指向最后一個結點(頭節點的prev結點)
讓它的next結點指向哨兵位,然后讓最后一個結點的下一個結點的指針指向newnode,讓哨兵位的prev結點指向newnode.

void listpushback(listNode* phead,listdatatype x)
{assert(phead);listNode* newnode = buyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

3.頭刪尾刪

3.0判斷鏈表是否為空

當我們如果要進行刪除操作的時候鏈表中一定是有元素的.我們可以將鏈表的判空封裝成一個方法.
如果當前結點下一個結點仍然是當前結點就證明,該鏈表為空.

/判斷是否非空
bool LTEmpty(listNode* phead)
{assert(phead);return phead->next == phead;
}

3.1頭刪

因為我們傳過來的結點一定是哨兵位,我們刪除的數據是它的下一個結點.為了防止丟失,我們可以提前將它保存為del.與它相關聯的結點時哨兵位以及del的下一個結點,我們要讓它的del的下一個結點的prev指向哨兵位,哨兵位的next指向del的下一個結點.然后釋放del,置空.
該實現該函數的時候要注意判空.

void listpopfront(listNode* phead)
{assert(!LTEmpty(phead));listNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

3.2尾刪

對于尾刪來說,我們要刪除最后一個有數據的結點,與之關聯的結點一共有兩個,哨兵位以及它的前一個結點.我們要讓它的前一個結點的next指向哨兵位,讓哨兵位的prev指針指向要刪除結點的前一個結點.然后釋放該結點.我們可以提前保存該結點為del,方便操作.

void listpopback(listNode* phead)
{assert(!LTEmpty(phead));listNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

4.查找與打印

4.1查找

對于查找來說,它需要遍歷整個鏈表,然后用當前值與該結點數據域中的值進行比對.如果找到就返回該結點,找不到就返回空.結束條件時當前結點等于哨兵位

listNode* listFind(listNode* phead, listdatatype x)
{listNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

4.2打印

打印仍然時遍歷鏈表,直到結束條件時當前結點等于哨兵位.

void print(listNode* phead)
{listNode* pcur = phead->next;while (pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}

5.在指定位置之前插入數據/在指定位置之后插入數據

5.1在指定位置之前插入數據

該函數實現涉及三個結點pos結點,pos結點的前一個結點.newnode.
我們讓newnode的prev指向pos結點的前一個結點.它的next結點指向pos結點.
pos結點的前一個結點的next指針指向newnode,pos結點的prev指針指向newnode即可

void listinsertFront(listNode* pos, listdatatype x)
{assert(pos);listNode* newnode = buyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}

5.2在指定位置之后插入數據

該方法實現涉及三個結點.pos結點.pos結點的下一個結點,newnode.
我們仍然newnode結點的prev和next分別指向pos結點和pos結點的下一個結點.
pos結點的下一個結點的prev指針指向newnode,pos結點的next指針指向newnode.

void listinsertBack(listNode* pos, listdatatype x)
{assert(pos);listNode* newnode = buyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

6.在指定位置之前刪除數據/在指定位置之后刪除數據

6.1在指定位置之前刪除數據

我們先要將pos之前那個要刪除的結點保存為del.
讓del的前一個結點的next指針指向pos.
pos的prev指針指向del的前一個結點,然后釋放del.
但再刪除前仍然需要判空.

void listErasefront(listNode* pos)
{assert(!LTEmpty(pos));listNode* del = pos->prev;del->prev->next = pos;pos->prev = del->prev;free(del);del = NULL;
}

6.2在指定位置之后刪除數據

我們要先將pos結點之后的那個要刪除的結點保存為del,然后讓del的下一個結點的prev指向pos.
pos的next指針指向del的下一個結點,然后釋放del.

void listEraseback(listNode* pos)
{assert(!LTEmpty(pos));listNode* del = pos->next;del->next->prev = pos;pos->next = del->next;free(del);del = NULL;
}

7.銷毀鏈表

與鏈表的初始化相對,它也有兩種實現方式,但大體的思想都是循環銷毀.

void destroyalpha(listNode** pphead)
{listNode* pcur = (*pphead)->next;while (pcur != (*pphead)){listNode* next = pcur->next;free(pcur);pcur = next;}free((*pphead));*pphead = NULL;
}void destroybata(listNode* phead)
{listNode* pcur = phead->next;while (pcur != phead){listNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;}

但要注意第二種方式如果使用,我們需要再外面對結點置空,防止成為野指針,