本篇是基于上篇單鏈表所作，推薦與上篇配合閱讀，效果更加
http://t.csdnimg.cn/UhXEj
1.鏈表的分類
我們一般叫這個頭為哨兵位
1.帶頭單向循環(huán)鏈表：
2.帶頭單向不循環(huán)鏈表
3.帶頭雙向循環(huán)鏈表
4.帶頭雙向不循環(huán)鏈表
5.不帶頭單向循環(huán)鏈表
6.不帶頭單向不循環(huán)鏈表
7.不帶頭雙向循環(huán)鏈表
8.不帶頭雙向不循環(huán)鏈表
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實際中最常用還是兩種結(jié)構(gòu)： 單鏈表 和 雙向帶頭循環(huán)鏈表1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，?般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復雜，?般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了。
2.雙向帶頭循環(huán)鏈表
我們還是經(jīng)典三個文件：
我們先定義頭文件所需要的函數(shù)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定義雙向鏈表中節(jié)點的結(jié)構(gòu)
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
//注意，雙向鏈表是帶有哨兵位的，插入數(shù)據(jù)之前鏈表中必須要先初始化一個哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead); //推薦一級（保持接口一致性）
void LTPrint(LTNode* phead);
//不需要改變哨兵位，則不需要傳二級指針
//如果需要修改哨兵位的話，則傳二級指針
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//頭刪、尾刪
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x);
//刪除pos位置的數(shù)據(jù)
void LTErase(LTNode* pos);首先我們還是得先定義節(jié)點，由于是雙向鏈表，所以節(jié)點內(nèi)存在兩個節(jié)點的地址，一個是前驅(qū)節(jié)點的（指向其前一個節(jié)點），一個是尾結(jié)點的（指向其后一個節(jié)點）
這一段代碼，是為了確保數(shù)據(jù)類型
我們節(jié)點定義成這樣：
接下來又是完成各個功能：增，刪，查，改。但是，由于我們長線的是帶頭的鏈表，所以我們需要對頭初始化
3.初始化
我們先定義初始化函數(shù)，然后寫函數(shù)：
void LTInit(LTNode** pphead);void ltinit(ltnode** pphead) {
*pphead = (ltnode*)malloc(sizeof(ltnode));
if (*pphead == null) {
perror("malloc fail!");
exit(1);
}
(*pphead)->data = -1;
(*pphead)->next = (*pphead)->prev = *pphead;
}和上回寫單鏈表差不多，檢測開辟是否成功，成功就接著給數(shù)據(jù)賦值，由于此時只有一個節(jié)點，即哨兵節(jié)點，且是循環(huán)鏈表，所以存放的前驅(qū)和尾節(jié)點就是哨兵節(jié)點自己
所以我們可以得出，如果哨兵節(jié)點的next指針或者prev指針指向自己，說明當前鏈表為空。
4.創(chuàng)建新的節(jié)點
我們寫法和上次差不多
LTNode* LTBuyNode(LTDataType x) {
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}只是這回，多了一個前驅(qū)節(jié)點，我們定義時間默認前驅(qū)和后去節(jié)點指向的是本身。
但是既然我們都這么寫了一個創(chuàng)建新節(jié)點的函數(shù)，那么我們可不可以用這個函數(shù)直接去進行哨兵節(jié)點的創(chuàng)建？
答案是肯定的，我們首先先改變以下我們定義的函數(shù)，
LTNode* LTInit();然后調(diào)用創(chuàng)建新節(jié)點的函數(shù)，得到哨兵節(jié)點
LTNode* LTInit() {
LTNode* phead = LTBuyNode(-1);
return phead;
}
5.頭插和尾插
注意：頭插，是把新的節(jié)點插在第一個節(jié)點前，不是哨兵節(jié)點前
頭插和尾插，頭刪和尾刪的思路整體和單鏈表一致，我就不詳細說明了，直接上代碼
定義函數(shù)：
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
函數(shù)代碼示例：
//尾插
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead phead->prev(ptail) newnode
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
不懂的你們可以再看看圖：
6.頭刪和尾刪
定義函數(shù)：
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);函數(shù)代碼示例：
//尾刪
void LTPopBack(LTNode* phead) {
assert(phead);
//鏈表為空：只有一個哨兵位節(jié)點
assert(phead->next != phead);
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
//頭刪
void LTPopFront(LTNode* phead) {
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
//phead del next
next->prev = phead;
phead->next = next;
free(del);
del = NULL;
}7.查找
整體思路還是遍歷，和單鏈表十分相似
定義函數(shù)：
LTNode* LTFind(LTNode* phead, LTDataType x);函數(shù)代碼示例：
LTNode* LTFind(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}8.在pos位置之后插入數(shù)據(jù)
這個和單戀表的也很相似，多了一個prev指針而已，寫的時候要注意順序，函數(shù)定義我就不寫了
函數(shù)代碼示例：
//在pos位置之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x) {
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}9.刪除pos位置的數(shù)據(jù)
這個和單鏈表還是一樣的，遍歷整個表，然后相愛指針指向的地址，然后釋放內(nèi)存
函數(shù)代碼示例：
void LTErase(LTNode* pos) {
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
10.打印
這個其實是用來看每個節(jié)點中間的數(shù)據(jù)的，我們可以通過前驅(qū)節(jié)點或者尾節(jié)點實現(xiàn)正序或逆序打印，這一步也是遍歷然后看哨兵節(jié)點是否是下一位，是就中斷，我這里之舉一種例子，另一種只要將next改成prev
函數(shù)代碼示例：
void LTPrint(LTNode* phead) {
//phead不能為空
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}11.銷毀
這個鏈表的銷毀和點鏈表不大一樣，因為存在哨兵節(jié)點，所以我們要分開釋放內(nèi)存
函數(shù)代碼示例：
void LTDesTroy(LTNode* phead) {
//哨兵位不能為空
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//鏈表中只有一個哨兵位
free(phead);
phead = NULL;
}最后還是一如既往的測試環(huán)節(jié)就交給大家了。推薦閱讀完http://t.csdnimg.cn/UhXEj文章來源：http://www.zghlxwxcb.cn/news/detail-824671.html
然后再閱讀這個文章來源地址http://www.zghlxwxcb.cn/news/detail-824671.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表的分類和雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
