數據結構之單鏈表基本運算的實現[12]

　　雙向鏈表結點的定義如下

　　typedef struct node{

　　DataType data;

　　struct node *prior *next;

　　}DuNode*DLinkList;

　　和單鏈表類似雙向鏈表也有幾種變形形式圖給出了帶頭結點的雙向鏈表示意圖鏈表中存在從頭到尾和從尾到頭的兩條鏈;圖給出了帶頭結點的雙向循環鏈表示意圖鏈表中存在兩個環

　　顯然通過某結點的指針p可以直接得到它的後繼結點的指針p>next也可以直接得到它的前驅結點的指針p>prior這樣在有些需要查找前驅的操作中時間效率大大提高

　　設p指向雙向循環鏈表中的某一結點即p是該結點的指針則p>prior>next表示的是*p結點之前驅結點的後繼結點的指針即與p相等;類似p>next>prior表示的是*p結點之後繼結點的前驅結點的指針也與p相等所以有以下等式

　　p=p>prior>next = p>next>prior

　　雙向鏈表中結點的插入設p指向雙向鏈表中某結點s指向待插入的值為x的新結點將*s插入到*p的前面插入示意圖如圖所示

　　

　　圖 雙向鏈表中的結點插入

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23077.html