雙向鏈表

雙向鏈表L的每一個元素都是一個對象，每個對象有一個關鍵字key和兩個指針：next和prev。設x是一個元素，x.next指向它在鏈表中的後繼元素，x.prev指向它的前驅元素。如果x.prev = NIL，則元素x沒有前驅，因此是鏈表的第一個元素，鏈表的頭（head），如果x.next = NIL，則元素沒有後繼，因此是鏈表的最後一個元素，鏈表的尾（tail），屬性L.head指向鏈表的第一個元素，如果L.head = NIL，鏈表為空。

鏈表的搜索

用於查找鏈表L中第一個關鍵字為k的元素，並返回指向該元素的指針。如果鏈表中沒有關鍵字為k的對象，則返回NIL。

List-Search(L,k)x = L.headwhile x ！= NIL and x.key != k x = x.nextreturn x

鏈表的插入

給定一個已設置好關鍵字key的元素x，將x連接到鏈表的前段。

List-Insert(L,x)x.next = L.headif L.head != NIL L.head.prev = xL.head = xx.prev = NIL

鏈表的刪除

將一個元素x從鏈表L中移除，如果要刪除給定關鍵字值的元素，則必須先調用List-Search找到該元素。

List-Delete(L,x)if x.prev != NIL x.prev.next = x.nextelse L.head = x.nextif x.next != NIL x.next.prev = x.prevelse x.prev.next = NIL

哨兵

哨兵是一個啞對象，起作用是簡化邊界處理，利用一個nil節點代替NIL。