1. 雙向鏈表的結構

注意：這里的“帶頭”跟單鏈表的“頭結點”是兩個概念，實際上在單鏈表階段稱呼不太嚴謹，但是為了更好地理解就直接稱為單鏈表的頭結點。帶頭鏈表里的頭結點，實際為“哨兵位”，哨兵位結點不存儲任何有效元素，只是站在這里“放哨的”。

“哨兵位”存在的意義：

遍歷循環(huán)鏈表避免死循環(huán)。

2. 雙向鏈表的實現(xiàn)

2.1 雙向鏈表結構體

typedef int LTDataType;
// 定義雙向鏈表節(jié)點的結構
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2.2 申請結點

// 申請節(jié)點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}

2.3 初始化

// 初始化
void LTInit(LTNode** pphead)
{// 給鏈表創(chuàng)建一個哨兵位*pphead = LTBuyNode(-1);
}

2.4 鏈表的銷毀

// 銷毀
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}// 此時pcur指向phead，而phead還沒有被銷毀free(phead);phead = NULL;
}

2.5 鏈表的打印

// 打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.6 鏈表的尾插

// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 舊的尾結點就是phead->prev// 先讓新的尾結點的前指針指向舊的尾結點newNode->prev = phead->prev;newNode->next = phead;	// 再讓新的尾結點的下一級指針指向頭結點（哨兵位）// 舊的尾結點下一級指針指向新的尾結點phead->prev->next = newNode;phead->prev = newNode;	// 再讓頭結點（哨兵位）的下一級指針指向新的尾結點
}

2.7 鏈表的頭插

// 頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 要改變的結點：phead newNode phead->nextnewNode->next = phead->next;	// 先讓新的尾結點的下一級指針指向頭結點的下一級指針的結點newNode->prev = phead;	// 讓新的尾結點的前指針指向頭結點//phead->next->prev = newNode;	// 指向頭結點的下一級指針的結點的下一級指針指向新的結點//phead->next = newNode;	// 頭結點的下一級指針指向新的結點// 這樣也是可行的phead->next = newNode;	// 頭結點的下一級指針指向新的結點newNode->next->prev = newNode;	// 指向頭結點的下一級指針的結點的下一級指針指向新的結點}

2.8 鏈表的尾刪

// 尾刪
void LTPopBack(LTNode* phead)
{// 鏈表必須有效且鏈表不能為空（只有一個哨兵位）assert(phead && phead->next != phead);LTNode* del = phead->prev;// 影響的指針：phead del->prev deldel->prev->next = phead;phead->prev = del->prev;// 刪除del節(jié)點free(del);del = NULL;
}

2.9 鏈表的頭刪

// 頭刪
void LTPopFront(LTNode* phead)
{// 鏈表必須有效且鏈表不能為空（只有一個哨兵位）assert(phead && phead->next != phead);LTNode* del = phead->next;// 影響的指針：phead del del->nextphead->next = del->next;del->next->prev = phead;// 刪除del節(jié)點free(del);del = NULL;
}

2.10 鏈表查找數(shù)據(jù)

// 查找數(shù)據(jù)
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}// 沒有找到return NULL;
}

2.11?在pos位置之后插入數(shù)據(jù)

// 在 pos 位置之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = LTBuyNode(x);// 影響的指針：pos newNode pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}

2.12 刪除pos結點

// 刪除 pos節(jié)點
void LTErase(LTNode* pos)
{// pos理論上來說不能為phead，但是沒有參數(shù)phead，無法增加校驗assert(pos);// 影響的指針：pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}