跟大家門交流一下:
一、插入操作(insert)
(一)基本原理
雙鏈表就好像是手拉手站成一排的人,每個人的右手(next)拉著下一個人,左手(prior)拉著前一個人,每兩個人之間有兩支手互聯.插入操作實際是向隊伍中增加人員,他需要拉上左右兩邊的人,即共三個人要發生關系,由於每兩個人之間有兩支手互聯,所以要發生4次操作.如已知節點
q,p,需插入s,稱為原型吧）.
----------------------------------
q->next
--->
q p
<---
p->prior
---------------------------------
現在假設需插入節點s,則需進行以下4次操作:
-----------------------------------------
(1)(2)完成q與s的握手
(1) q->next = s;
(2) s->prior = q;
q->next
--->
q s
<---
s->prior
-----------------------------------------
(3)(4)完成s與p的握手
(3) s->next = p;
(4) p->prior = s;
q->next s->next
---> --->
q s p
<--- <---
s->prior p->prior
-------------------------------------------
對於本文的案例，是原型的變種, 只已知節點p,而不知節點q,但通過雙向鏈表的性質我們可以再初始時(插入前)得到以下關系:
p->prior = q;
所以對於以上的4次操作我們可以作等效替換,即將q 換為 p->prior,則以上4次操作為:
(1) p->prior->next = s;
(2) s->prior = p->prior; file://(1)(2)完成q與s的握手
(3) s->next = p;
(4) p->prior = s; file://(3)(4)完成s與p的握手
(二)互換問題
由於不知道q節點，因此用p->prior來代替，所以p->prior的值應當在已經不再使用q節點的時候再改變，由原型：
(1) q->next = s;
(2) s->prior = q;
(3) s->next = p;
(4) p->prior = s;
(4)改變了p->prior的值，而(1)(2)需使用q,所以(4)應當在(1)(2)後。
二、刪除操作(insert)
(一)基本原理
刪除操作就好像某個人退出隊伍，但退出前他需要讓他兩邊的人把手拉上,以保持隊伍的連續性,也好像離職前要把工作要交接好,就好像我現在,哈...,如已知q,s,p, 需刪除s,由於只需兩個人發生關系,所以需進行以下兩次操作:
(1) q->next = p;
(2) p->prior = q;
q->next s->next
---> --->
q s p
<--- <---
s->prior p->prior
q->next
--->
q p
<---
p->prior
對於本例,是上面原型的變種,只已知s,但由雙向鏈表的性質,我們可以推出以下關系:
q == s->prior;
p == s->next;
因此可做以下替換:
(1) s->prior->next = s->next;
(2) s->next->prior = s->prior;
由於s ,以及prior和next的值在兩次操作中並沒有被改變,因此(1)(2)的順序沒有關系.
三、一些結論
1）對於雙向鏈表的插入，只需知道插入位置的一個節點即可完成插入；
2）對於雙向鏈表的刪除，只需知道刪除節點即可完成刪除。
因此對於雙向鏈表的插入和刪除在該情況下，時間度為O(1)。
個人拙見,歡迎大家批評指正.
