我們之前討論的鏈?zhǔn)酱鎯Y(jié)構(gòu)的結(jié)點中只有一個指示直接后繼的指針域璧瞬，由此，從某個結(jié)點出發(fā)只能順時針往后尋查其它結(jié)點渐夸。如果要尋查直接前驅(qū)嗤锉，則需要從表頭指針出發(fā)。換句話說墓塌，在單鏈表中瘟忱，NextElem的執(zhí)行時間為O(1),而PriorElem的執(zhí)行時間為O(n).為克服單鏈表這種單向性的缺點，可以利用雙向鏈表(double linked list).
顧名思義苫幢，在雙向鏈表的結(jié)點中有兩個指針域访诱，一個指向直接后繼，另一個指向直接前驅(qū).
1.定義
typedef struct DulNode{
ElemType data;//數(shù)據(jù)域
struct DulNode *prior;//直接前驅(qū)結(jié)點
struct DulNode *next;//直接后繼結(jié)點
}DulNode;
typedef struct DulNode *DuLinkList;
雙向鏈表結(jié)點結(jié)構(gòu)與空雙向鏈表
既然單鏈表有循環(huán)表韩肝，雙向鏈表也有循環(huán)表結(jié)構(gòu)
雙向循環(huán)鏈表
2. 雙向鏈表的插入操作
雙向鏈表的插入
雙向鏈表的插入操作并不復(fù)雜触菜，但是順序很重要，千萬不要寫反了哀峻。
如圖所示涡相，將結(jié)點S插入在雙向鏈表的P結(jié)點之前，我們需要：
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
實現(xiàn)如下：
//獲取結(jié)點操作
DuLinkList GetElem(DuLinkList L,int i){
DuLinkList p = L->next;//獲取頭結(jié)點的指針 p代表第一個結(jié)點
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return NULL;
}
return p;
}
//在帶頭結(jié)點的雙鏈循環(huán)線性表L中第i個位置之前插入e
Status ListInsert_Dul(DuLinkList *L,int i,ElemType e){
DuLinkList p = GetElem(*L, i);
if (!p) {
//p為NULL剩蟀，插入位置非法
return ERROR;
}
DuLinkList s = (DuLinkList)malloc(sizeof(DulNode));
if (!s) {
return ERROR;
}
s->data = e;
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
return OK;
}
3.雙向鏈表的刪除操作
雙向鏈表的刪除操作
刪除操作更容易理解催蝗，我們可以這樣實現(xiàn):
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
實現(xiàn)如下:
//刪除帶頭結(jié)點的雙向鏈表L的第i個元素
Status ListDelete_Dul(DuLinkList *L,int i,ElemType *e){
DuLinkList p = GetElem(*L, i);
if (!p) {
//位置非法，即第i個元素不存在
return ERROR;
}
*e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
