站長資訊網(wǎng)在上篇文章中，我們已經(jīng)說過了鏈表除了簡單的那一種單向鏈表外，還有其它的幾種形式。當(dāng)然，這也是鏈表這種結(jié)構(gòu)的一大特點(diǎn)，非常地靈活和方便。我們簡單的想一想，如果讓最后一個(gè)節(jié)點(diǎn)的next指回第一個(gè)節(jié)點(diǎn)，那么這就樣就形成了一個(gè)環(huán)，這就是一個(gè)循環(huán)鏈表了。
如果我們?cè)诿總€(gè)節(jié)點(diǎn)上增加一個(gè)指向上一個(gè)節(jié)點(diǎn)的 prev 屬性，那么這個(gè)鏈表就變成了一個(gè)雙向鏈表了。如果我們?cè)陔p向鏈表的基礎(chǔ)上也讓最后一個(gè)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)，同時(shí)讓第一個(gè)節(jié)點(diǎn)的 prev 指向最后一個(gè)節(jié)點(diǎn)，這不就是一個(gè)雙向循環(huán)鏈表了嘛。下面我們就來具體的看一看。
循環(huán)鏈表
就像上文所說的，我們讓最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，這樣形成的鏈表就是一個(gè)循環(huán)鏈表，如下圖所示：
關(guān)于循環(huán)的鏈表的操作我們不做詳細(xì)的說明，其實(shí)大部分代碼和單向鏈表是一樣的，只是需要注意兩個(gè)地方：
1.初始化、插入操作的時(shí)候，注意最后一個(gè)節(jié)點(diǎn)的指向，最后一個(gè)節(jié)點(diǎn)的 next 要指向第一個(gè)節(jié)點(diǎn)
2.判斷鏈表遍歷是否完成的條件為 item->next == head ，也就是說，判斷這個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)如果是頭節(jié)點(diǎn)的話，鏈表就遍歷完成了。
雙向鏈表
雙向鏈表則是在 LinkedList 這個(gè)類里面增加一個(gè)屬性來指向上一個(gè)節(jié)點(diǎn)。
// 雙向鏈表 class LinkedList { public $data; public $prev; public $next; }
接下來，我們初始化一個(gè)雙向鏈表。
/** * 生成鏈表 */ function createLinkedList() { $list = new LinkedList(); $list->data = null; $list->next = null; $list->prev = null; // ** 全部都初始化為 null ** return $list; } /** * 初始化鏈表 * @param array $data 鏈表中要保存的數(shù)據(jù)，這里以數(shù)組為參考 * @return LinkedList 鏈表數(shù)據(jù) */ function Init(array $data) { // 初始化 $list = createLinkedList(); $r = $list; foreach ($data as $key => $value) { $link = new LinkedList(); $link->data = $value; $link->next = null; $r->next = $link; $link->prev = $r; // ** 增加上級(jí)指向 ** $r = $link; } return $list; } $link = Init(range(1, 10)); var_dump($link); var_dump($link->next->next->next->next); // object(LinkedList)#5 (3) { // ["data"]=> // int(4) // ["prev"]=> // object(LinkedList)#4 (3) { // ["data"]=> // int(3) // ["prev"]=> // object(LinkedList)#3 (3) { // ["data"]=> // int(2) // ["prev"]=> // object(LinkedList)#2 (3) { // ["data"]=> // int(1) // ["prev"]=> // object(LinkedList)#1 (3) { // ["data"]=> // NULL // ["prev"]=> // NULL // ["next"]=> // *RECURSION* // } // ["next"]=> // *RECURSION* // } // ["next"]=> // *RECURSION* // } // ["next"]=> // *RECURSION* // } // ["next"]=> // object(LinkedList)#6 (3) { // ["data"]=> // int(5) // ["prev"]=> // *RECURSION* // ["next"]=> // object(LinkedList)#7 (3) { // ["data"]=> // int(6) // ["prev"]=> // *RECURSION* // ["next"]=> // object(LinkedList)#8 (3) { // ["data"]=> // int(7) // ["prev"]=> // *RECURSION* // ["next"]=> // object(LinkedList)#9 (3) { // ["data"]=> // int(8) // ["prev"]=> // *RECURSION* // ["next"]=> // object(LinkedList)#10 (3) { // ["data"]=> // int(9) // ["prev"]=> // *RECURSION* // ["next"]=> // object(LinkedList)#11 (3) { // ["data"]=> // int(10) // ["prev"]=> // *RECURSION* // ["next"]=> // NULL // } // } // } // } // } // } // } echo $link->next->next->next->next->data, PHP_EOL; // 4 echo $link->next->next->next->next->prev->data, PHP_EOL; // 3
可以看出，與單向鏈表不同的地方就在于多增加了對(duì)于 prev 屬性的操作。這里還是比較好理解的。直接打印鏈表會(huì)顯示很多的 *RECURSION* 內(nèi)容，這是 PHP 的一種輸出的保護(hù)機(jī)制，這個(gè)標(biāo)識(shí)說明當(dāng)前這個(gè)屬性變量是有遞歸類型的。
/** * 鏈表指定位置插入元素 * @param LinkedList $list 鏈表數(shù)據(jù) * @param int $i 位置 * @param mixed $data 數(shù)據(jù) */ function Insert(LinkedList &$list, int $i, $data) { $j = 0; $item = $list; // 遍歷鏈表，找指定位置的前一個(gè)位置 while ($j < $i - 1) { $item = $item->next; $j++; } // 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1) { return false; } // 創(chuàng)建一個(gè)新節(jié)點(diǎn) $s = new LinkedList(); $s->data = $data; // 新創(chuàng)建節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向原 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)，也就是當(dāng)前的 i 節(jié)點(diǎn) $s->next = $item->next; // ** 增加當(dāng)前新創(chuàng)建的節(jié)點(diǎn)的上級(jí)指向 ** $s->prev = $item; // 將 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置 $item->next = $s; // ** 將下級(jí)節(jié)點(diǎn)的 prev 指向新創(chuàng)建的這個(gè)節(jié)點(diǎn) ** $s->next->prev = $s; return true; }
鏈表的插入其實(shí)就是增加了兩行代碼，一個(gè)是當(dāng)前新創(chuàng)建的節(jié)點(diǎn)的上級(jí)的指向，也就是將這個(gè)新節(jié)點(diǎn)的上級(jí)指定為 i-1 個(gè)節(jié)點(diǎn)。而另一個(gè)是將原來 i 位置節(jié)點(diǎn)的上級(jí)指向修改為當(dāng)前新創(chuàng)建的這個(gè)節(jié)點(diǎn)。
/** * 刪除鏈表指定位置元素 * @param LinkedList $list 鏈表數(shù)據(jù) * @param int $i 位置 */ function Delete(LinkedList &$list, int $i) { $j = 0; $item = $list; // 遍歷鏈表，找指定位置的前一個(gè)位置 while ($j < $i - 1) { $item = $item->next; $j++; } // 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1) { return false; } // 使用一個(gè)臨時(shí)節(jié)點(diǎn)保存當(dāng)前節(jié)點(diǎn)信息，$item 是第 i-1 個(gè)節(jié)點(diǎn)，所以 $item->next 就是我們要找到的當(dāng)前這個(gè) i 節(jié)點(diǎn) $temp = $item->next; // 讓當(dāng)前節(jié)點(diǎn)，也就是目標(biāo)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)， i-1 的這個(gè)節(jié)點(diǎn)的下一跳（原來的 i 位置的節(jié)點(diǎn)）變成原來 i 位置節(jié)點(diǎn)的下一跳 next 節(jié)點(diǎn)，讓i位置的節(jié)點(diǎn)脫離鏈條 $item->next = $temp->next; // ** 讓目標(biāo)下一個(gè)節(jié)點(diǎn)的上級(jí)指針指向當(dāng)前這個(gè)節(jié)點(diǎn) ** $temp->next->prev = $item; return true; }
與插入節(jié)點(diǎn)操作類似，刪除節(jié)點(diǎn)操作除了將 i-1 個(gè)位置節(jié)點(diǎn)的數(shù)據(jù)的下一個(gè)節(jié)點(diǎn)的指向變?yōu)?i 節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)的指向之外，還要將 i 的下一級(jí)節(jié)點(diǎn)的上級(jí)節(jié)點(diǎn)指向改為 i-1 節(jié)點(diǎn)。
其實(shí)，雙向鏈表的定義和操作相比單向鏈表來說差別并不大，就是多了一個(gè) prev 用來指向上一級(jí)節(jié)點(diǎn)而已，本質(zhì)上也只是多了對(duì)于 prev 這個(gè)屬性的操作而已。那么，多出來的這一個(gè)上級(jí)指針能帶來什么好處呢？在遍歷鏈表的時(shí)候，我們通過 prev ，就多了一種遍歷方式，也就是反向的對(duì)鏈表進(jìn)行遍歷。在查找某個(gè)元素的時(shí)候，我們可以從兩個(gè)方向同時(shí)進(jìn)行查找，效率是不是一下子就提升了一倍。原來 O(n) 的時(shí)間復(fù)雜度瞬間可以變成 O(n/2) 的時(shí)間復(fù)雜度。
雙向循環(huán)鏈表
最后，我們也簡單的來介紹一下雙向循環(huán)鏈表。顧名思義，它就是在雙向鏈表的基礎(chǔ)上加上循環(huán)鏈表的概念。讓最后一個(gè)節(jié)點(diǎn)的 next 指向頭節(jié)點(diǎn)，讓頭節(jié)點(diǎn)的 prev 指向最后一個(gè)節(jié)點(diǎn)。說起來容易但實(shí)現(xiàn)起來其實(shí)要復(fù)雜很多，因?yàn)槟悴粌H要關(guān)注最后一個(gè)節(jié)點(diǎn)的下級(jí)節(jié)點(diǎn)指向問題，而且還要關(guān)注頭節(jié)點(diǎn)的上級(jí)指向問題。所以在這里我們就不多做代碼演示了，最主要的就是在插入和刪除頭、尾節(jié)點(diǎn)的時(shí)候需要多注意它們上下級(jí)節(jié)點(diǎn)的指向。
總結(jié)
突然發(fā)現(xiàn)新大陸了吧？鏈表原來還有這么多種形式。當(dāng)然，這還沒有說完，我們還有一個(gè)很高大上的十字鏈表沒說，不過其實(shí)十字鏈表也只是增加了
