雙向鏈表(double linked list)定義
雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針扰付。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域：一個(gè)指向直接后繼谐岁，一個(gè)指向直接前驅(qū)澡屡。
線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)代碼實(shí)現(xiàn)
typedef struct DulNode{
ElemType data;
struct DulNode *prior; /* 直接前驅(qū)指針 */
struct DulNode *next; /* 直接后繼指針 */
}DulNode, *DuLinkList;
循環(huán)雙向鏈表圖示
-
雙向鏈表的循環(huán)帶頭結(jié)點(diǎn)的空鏈表：
雙向鏈表的循環(huán)帶頭結(jié)點(diǎn)的空鏈表 -
非空的循環(huán)的帶頭結(jié)點(diǎn)的雙向鏈表：
非空的循環(huán)的帶頭結(jié)點(diǎn)的雙向鏈表
特點(diǎn)
- 對(duì)于鏈表中的某個(gè)結(jié)點(diǎn)
p梆暖，它的后繼的前驅(qū)是它自己，同樣乌奇，它的前驅(qū)的后繼也是它自己
p->next->prior = p;p->prior->next = p;
雙向鏈表的操作
雙向鏈表是單鏈表擴(kuò)展出來(lái)的結(jié)構(gòu)没讲，所以它的很多操作是和單鏈表相同的，比如求長(zhǎng)度的
ListLength,查找元素的GetElem,獲得元素位置的LocateElem等礁苗，這些操作都只要涉及一個(gè)方向的指針即可爬凑。
插入操作
插入操作并不復(fù)雜，但是順序很重要试伙，一定不能寫反嘁信。
假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p和p->next之間疏叨。
雙向鏈表的插入操作圖解
核心代碼：
s->prior = p; /* 把 p 賦值給 s 的前驅(qū) */
s->next = p->next; /* 把 p->next 賦值給 s 的后繼 */
p->next->prior = s; /* 把 s 賦值給 p->next 的前驅(qū) */
p->next = s; /* 把 s 賦值給 p 的后繼 */
注意:關(guān)鍵在于他們的順序潘靖，有第二步和第三部都用到了p->next。如果第四步先執(zhí)行蚤蔓，則會(huì)使得p->next提前變成了s,使得插入的工作完不成卦溢。
刪除操作
刪除操作比插入操作更加簡(jiǎn)單。如果要?jiǎng)h除p秀又，只需要兩步单寂。
雙向鏈表的刪除操作圖解
核心代碼
p->prior->next = p->next; /* 把 p->next 賦值給 p->prior 的后繼 */
p->next->prior = p->prior; /* 把 p->prior 賦值給 p->next 的前驅(qū) */
free(p);
