1.雙向鏈表的數據結構

typedef char DLinkType;typedef struct DLinkNode 
{ DLinkType data; struct DLinkNode* next; struct DLinkNode* prev; 
}DLinkNode; 

????雙向帶頭結點的鏈表有三個成員， 一個是數據， 一個是指針 next 指向當前結點的下一個結點， 一個指針 prev 指向當前結點的 前一個結點，即每一個節點都有一個直接的前驅， 一個直接的后繼， 這里只討論帶頭結點的雙向鏈表。

2.雙向鏈表的初始化

/*** 初始化雙鏈表**/void DLinkListInit(DLinkNode** phead)
{if(phead == NULL){return;//非法輸入}*phead = (DLinkNode*)malloc(sizeof(DLinkNode));(*phead) -> data = 0;(*phead) -> next = *phead;(*phead) -> prev = *phead;
}

????帶頭結點雙向鏈表的初始化即就是用一個傀儡節點代表其為空，這里將頭節點的數據初始化為 0， 注意，雙向鏈表中沒有空指針，所以將雙向鏈表的頭節點的 next 指向它自己， 將雙向鏈表的 prev 指向它自己，即判斷一個雙向帶頭節點的鏈表是否為空的條件就是head -> next == head 或者是 head -> prev == head。

3.創建一個新節點

????既然需要對鏈表進行插入數據， 那便需要對其創建一個指定數據的節點，然后將其插入到當前的鏈表中。創建一個節點就是對其先分配空間， 再將節點對應的數據改為需要的目標數據。

/*** 創建一個新節點**/
DLinkNode* DLinkNodeCreat(DLinkType value)
{DLinkNode* new_node = (DLinkNode*)malloc(sizeof(DLinkNode));if(new_node == NULL){return NULL;//內存分配失敗}new_node -> data = value;new_node -> next = new_node;new_node -> prev = new_node;return new_node;
}

4.頭插一個新結點

?&enap;?&enap;對雙向鏈表的頭插節點也就是先創建一個新結點，然后定義一個指針 prev 指向頭結點的下一個節點， 即prev = head -> next, 然后修改對應的 prev 和 所創建的新結點 new_node 的指向， 即 讓 prev -> next = new_node, 再讓new_node -> prev = prev,就OK了

/*** 頭插一個節點**/void DLinkListPushFront(DLinkNode* head, DLinkType value)
{if(head == NULL){return;//非法輸入}DLinkNode* new_node = DLinkNodeCreat(value);DLinkNode* prev = head;DLinkNode* next = head -> next;prev -> next = new_node;new_node -> prev = prev;new_node -> next = next;next -> prev = new_node;
}

5.頭刪一個節點

?????既然頭刪一個節點就必須先定義一個指針 to_delete 指向要刪除的節點， 即 head ->next, 然后在定義一個指針指向要刪除的元素的下一個節點， 即定義一個指針 next = to_delete -> next, 然后修改head和 next 指針的指向即可， 最后將 to_delete 所指向的節點銷毀即可。

/*** 頭刪一個節點**/
void DLinkListPopFront(DLinkNode* head)
{if(head == NULL){return;//非法輸入}if(head -> next == head){return;//空鏈表}DLinkNode* to_delete = head -> next;DLinkNode* next = to_delete -> next;head -> next = next;next -> prev = head;DLinkNodeDstroy(to_delete);
}/*** 銷毀一個節點**/void DLinkNodeDstroy(DLinkNode* to_delete)
{free(to_delete);to_delete = NULL;
}

6.尾插一個節點

????尾插一個節點和鏈表頭插一個元素道理基本相似， 即先創建一個節點 new_node， 然后在定義一個指針 prev = head -> prev,最后修改 head 和 new_node 指針的指向， 接下來再修改 new_node 和 next 指針的指向就可以了。即讓 head -> prev = new_node, new_node -> next = head, new_node -> prev = prev, prev -> next = new_node, 此時就已經將新的元素尾插到鏈表中了

/*** 尾插一個節點**/DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value)
{if(head == NULL){return NULL;//非法輸入}DLinkNode* new_node = DLinkNodeCreat(value);DLinkNode* next = head -> next;new_node -> next = next;next -> prev = new_node;head -> next = new_node;new_node -> prev = head;return head;
}

7.尾刪一個節點

????往雙鏈表中尾插一個元素就是先找到最后一個節點, to_delete = head -> prev, 然后記下 to_delete 節點的前一個節點, 即 prev = to_delete -> prev, 然后讓 prev -> next = head, haed -> prev = prev, 再將to_delete 刪除就可以了

/*** 尾刪一個元素**/void DLinkListPopBack(DLinkNode* head)
{if(head == NULL){return;//非法輸入}if(head -> next == head){return;//刪除空鏈表}DLinkNode* to_delete = head -> prev;DLinkNode* prev = to_delete -> prev;head -> prev = prev;prev -> next = head;DLinkNodeDstroy(to_delete);
}

8.在雙向鏈表中查找值為 to_find 節點，并且返回該節點所對應的位置

?&esnp;??定義一個指針cur 指向 head -> next, 然后讓 cur 依次遍歷整個鏈表, 當 cur -> data == to_find 時,就將此時的 cur 返回即可

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find)
{if(head == NULL){return NULL;//非法輸入}if(head -> next == head){return NULL;}DLinkNode* cur = head -> next;for(; cur != head; cur = cur -> next){if(cur -> data == to_find){return cur;}}return NULL;//沒有找到
}

9.往對應位置 pos 處插入一個值為 value的新結點

????往指定位置插入一個值為value 的節點, 需要先創建一個新結點, 然后定義一個指針 prev = pos -> prev, 再定義一個指針 next = pos -> next, 然后改變 prev 和 新節點 之間指針的指向, 以及 新結點和next指針之間的指向就可以將其插入到指定位置 pos 處了

/*** 往 pos 所對應的位置處插入 value ***/void DLinkListInsert(DLinkNode* pos, DLinkType value)
{if(pos == NULL){return;//非法輸入}DLinkNode* new_node = DLinkNodeCreat(value);DLinkNode* prev = pos -> prev;//prev vs new_nodeprev -> next = new_node;new_node -> prev = prev;//new_node vs posnew_node -> next = pos;pos -> prev = new_node;
}

10.往指定位置之后插入一個值為 value 的結點

???? 先創建一個新結點 new_node,再定義一個指針 prev = pos, 接下來定義一個指針 next = pos -> next, 然后改變 new_node 節點和 prev 節點 之間的指向, 最后改變 new_node 和 next 之間節點指針指向就 OK 了

/*** 往指定位置之后插入一個元素**/void DLinkListInsertAfter(DLinkNode* pos, DLinkType value)
{if(pos == NULL){return;//非法輸入}DLinkNode* new_node = DLinkNodeCreat(value);DLinkNode* next = pos -> next;pos -> next = new_node;new_node -> prev = pos;new_node -> next = next;next -> prev = new_node;
}

11. 刪除某個元素對應的結點

????刪除某個元素對應的節點就先找到要刪除節點對應的位置, 然后再將這個位置對應的節點刪掉就可以了, 如果鏈表中沒有這個元素,或者鏈表是空鏈表則直接返回.

/*** 刪除某個元素對應的結點**/void DLinkListErase(DLinkNode* head, DLinkType to_delete)
{if(head == NULL){return;//非法輸入}if(head -> next == NULL){return;//刪除空鏈表}DLinkNode* cur = DLinkListFind(head, to_delete);if(cur == NULL){return;//刪除不存在的節點}DLinkNode* prev = cur -> prev;DLinkNode* next = cur -> next;prev -> next = next;next -> prev = prev;DLinkNodeDstroy(cur);
}

12.求鏈表長度

/*** 求鏈表長度**/size_t DLinkListSize(DLinkNode* head)
{DLinkNode* cur = head -> next;size_t size = 0;while(cur != head){cur = cur -> next;size++;}return size;
}

13. 鏈表判空

/*** 鏈表判空**/int DLinkListEmpty(DLinkNode* head)
{if(head == NULL){return -1;//非法輸入}if(head -> next == head){return 1;}return 0;
}

14.刪除鏈表中所有相同的結點

void DLinkListRemoveAll(DLinkNode* head, DLinkType to_delete)
{if(head == NULL){                                                                                                                                                    return;//非法輸入}if(head -> next == head){return;//空鏈表}DLinkNode* cur = head -> next;while(cur != head){if(to_delete == cur -> data){DLinkListErase(head, to_delete);}cur = cur -> next;}
}