沒(méi)有哨兵的鏈表：

ListSearch(L,k) {
　　x = L.head;
　　while(x!=null && x.key!=k)
　　　　x = x.next;
　　return x;
}

ListInsert(L,x){
　　x.next = L.head;
　　if(L.head!=null)
　　　　L.head.pre = x
　　L.head = x;
　　x.prev = null;
}

ListDelete(L,x) {
　　if(x.prev!=null)
　　　　x.prev.next = x.next;
　　else
　　　　L.head = x.next;
　　if(x.next!=null)
　　　　x.next.prev = x.prev;
}

存在哨兵的鏈表：

L.nil便是鏈表的哨兵

ListSearch(L,k){
　　x = L.nil.next;
　　while(x!=L.nil&&x.key!=k)
　　　　x = x.next;
　　return x;
}

ListInsert(L,x){
　　x.next = L.nil.next;
　　L.nil.next.prev = x;
　　L.nil.next = x;
　　x.prev = L.nil;
}

ListDelete(L,x){
　　x.prev.next = x.next;
　　x.next.prev = x.prev;
}

?

哨兵基本不能降低數(shù)據(jù)結(jié)構(gòu)相關(guān)操作的漸近時(shí)間界，但可以降低常數(shù)因子。

帶哨兵節(jié)點(diǎn)的鏈表，需要額外的一個(gè)節(jié)點(diǎn)，但插入和刪除等操作不需要額外的判斷；不帶哨兵節(jié)點(diǎn)，在處理鏈表為空時(shí)，和其他情況不一樣，需要單獨(dú)判斷一次。
帶哨兵節(jié)點(diǎn)的鏈表，插入或刪除時(shí)，不論操作的位置，表頭都不變，不需要額外的判斷；不帶哨兵節(jié)點(diǎn)的鏈表，插入或刪除操作發(fā)生在第一個(gè)節(jié)點(diǎn)時(shí)，表頭指針都要變化，需要額外的處理。

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/lvcoding/p/7473224.html

總結(jié)

以上是生活随笔為你收集整理的链表——哨兵的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。