2.3.3雙向鏈表 插入、刪除

指在前驅和后驅方向都能游歷（遍歷）的線性鏈表

雙向鏈表的每個結點有兩個指針域
【結構】：prior data next

雙鏈表通常采用帶頭結點的循環鏈表形式

可理解為首位相接的數據“圈”，每個結點都可以向前或向后走

【結點指向】

【插入操作】：

1.分配空間
2.斷開與連接

【操作算法
status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{if(!p=GetElem_Dul(L,i))
return ERROR; 相當于嵌套第i個結點的指針

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))
return ERROR 空間分配失敗
s-data=e; 將數據放入新結點的數據圖
s-prior=p-prior; 將p的前驅結點指針放入新結點的前向指針域
s-next=p; 將p放入新結點的反向指針域
p-prior-next=s; 修改p的前驅結點的反向指針
p-prior=s; 修改p的前驅指針
return OK;
} ListInsert_DuL

【刪除操作】

1.p指向目標結點
2.將目標結點的前一個結點與后一個連接（跳過中間那個）
3釋放內存

【操作算法】
status ListDelete_Dul(DuLinkList &L,int i,ElemType &e)
{ 刪除頭結點的雙向循環鏈表L中第i個元素返回，1=i=表長
if（!p=GetElem_Dul(L,i)）
return ERROR; 查找第i個指針
e=p-data; 將p指向結點數據域中的值取出
p-prior-next=p-next; p前一個結點的后驅指向p的后一個結點
p-next-prior=p-prior; 后指向前
free§; 釋放p
return OK;

} ListDelete_DuL

【 算法評價：T(n)=O(n) 】

！注意：如何選擇合適的存儲結構
鏈表只能順序存取，在單鏈表的最后一個元素后插入元素，需遍歷整個鏈表

頻繁插入刪除用鏈式存儲
偶爾 用順序存儲