在上篇文章中，我們已經(jīng)說過了鏈表除了簡單的那一種單向鏈表外，還有其它的幾種形式。當然，這也是鏈表這種結(jié)構(gòu)的一大特點，非常地靈活和方便。我們簡單的想一想，如果讓最后一個節(jié)點的next指回第一個節(jié)點，那么這就樣就形成了一個環(huán)，這就是一個循環(huán)鏈表了。

如果我們在每個節(jié)點上增加一個指向上一個節(jié)點的 prev 屬性，那么這個鏈表就變成了一個雙向鏈表了。如果我們在雙向鏈表的基礎(chǔ)上也讓最后一個節(jié)點的 next 指向第一個節(jié)點，同時讓第一個節(jié)點的 prev 指向最后一個節(jié)點，這不就是一個雙向循環(huán)鏈表了嘛。下面我們就來具體的看一看。

循環(huán)鏈表

就像上文所說的，我們讓最后一個節(jié)點指向第一個節(jié)點，這樣形成的鏈表就是一個循環(huán)鏈表，如下圖所示：

關(guān)于循環(huán)的鏈表的操作我們不做詳細的說明，其實大部分代碼和單向鏈表是一樣的，只是需要注意兩個地方：

1.初始化、插入操作的時候，注意最后一個節(jié)點的指向，最后一個節(jié)點的 next 要指向第一個節(jié)點

2.判斷鏈表遍歷是否完成的條件為 item->next == head ，也就是說，判斷這個節(jié)點的下一個節(jié)點如果是頭節(jié)點的話，鏈表就遍歷完成了。

雙向鏈表

雙向鏈表則是在 LinkedList 這個類里面增加一個屬性來指向上一個節(jié)點。

// 雙向鏈表 class LinkedList {     public $data;      public $prev;     public $next; }

接下來，我們初始化一個雙向鏈表。

/**  * 生成鏈表  */ 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; // ** 增加上級指向 **         $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

可以看出，與單向鏈表不同的地方就在于多增加了對于 prev 屬性的操作。這里還是比較好理解的。直接打印鏈表會顯示很多的 *RECURSION* 內(nèi)容，這是 PHP 的一種輸出的保護機制，這個標識說明當前這個屬性變量是有遞歸類型的。

/**  * 鏈表指定位置插入元素  * @param LinkedList $list 鏈表數(shù)據(jù)  * @param int $i 位置  * @param mixed $data 數(shù)據(jù)  */ function Insert(LinkedList &$list, int $i, $data) {     $j = 0;     $item = $list;     // 遍歷鏈表，找指定位置的前一個位置     while ($j < $i - 1) {         $item = $item->next;         $j++;     }      // 如果 item 不存在或者 $i > n+1 或者 $i < 0     if ($item == null || $j > $i - 1) {         return false;     }      // 創(chuàng)建一個新節(jié)點     $s = new LinkedList();     $s->data = $data;      // 新創(chuàng)建節(jié)點的下一個節(jié)點指向原 i-1 節(jié)點的下一跳節(jié)點，也就是當前的 i 節(jié)點     $s->next = $item->next;      // ** 增加當前新創(chuàng)建的節(jié)點的上級指向 **     $s->prev = $item;      // 將 i-1 節(jié)點的下一跳節(jié)點指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置     $item->next = $s;      // ** 將下級節(jié)點的 prev 指向新創(chuàng)建的這個節(jié)點 **     $s->next->prev = $s;      return true; }

鏈表的插入其實就是增加了兩行代碼，一個是當前新創(chuàng)建的節(jié)點的上級的指向，也就是將這個新節(jié)點的上級指定為 i-1 個節(jié)點。而另一個是將原來 i 位置節(jié)點的上級指向修改為當前新創(chuàng)建的這個節(jié)點。

/**  * 刪除鏈表指定位置元素  * @param LinkedList $list 鏈表數(shù)據(jù)  * @param int $i 位置  */ function Delete(LinkedList &$list, int $i) {     $j = 0;     $item = $list;     // 遍歷鏈表，找指定位置的前一個位置     while ($j < $i - 1) {         $item = $item->next;         $j++;     }     // 如果 item 不存在或者 $i > n+1 或者 $i < 0     if ($item == null || $j > $i - 1) {         return false;     }      // 使用一個臨時節(jié)點保存當前節(jié)點信息，$item 是第 i-1 個節(jié)點，所以 $item->next 就是我們要找到的當前這個 i 節(jié)點     $temp = $item->next;     // 讓當前節(jié)點，也就是目標節(jié)點的上一個節(jié)點， i-1 的這個節(jié)點的下一跳（原來的 i 位置的節(jié)點）變成原來 i 位置節(jié)點的下一跳 next 節(jié)點，讓i位置的節(jié)點脫離鏈條     $item->next = $temp->next;      // ** 讓目標下一個節(jié)點的上級指針指向當前這個節(jié)點 **     $temp->next->prev = $item;      return true; }

與插入節(jié)點操作類似，刪除節(jié)點操作除了將 i-1 個位置節(jié)點的數(shù)據(jù)的下一個節(jié)點的指向變?yōu)?i 節(jié)點的下一級節(jié)點的指向之外，還要將 i 的下一級節(jié)點的上級節(jié)點指向改為 i-1 節(jié)點。

其實，雙向鏈表的定義和操作相比單向鏈表來說差別并不大，就是多了一個 prev 用來指向上一級節(jié)點而已，本質(zhì)上也只是多了對于 prev 這個屬性的操作而已。那么，多出來的這一個上級指針能帶來什么好處呢？在遍歷鏈表的時候，我們通過 prev ，就多了一種遍歷方式，也就是反向的對鏈表進行遍歷。在查找某個元素的時候，我們可以從兩個方向同時進行查找，效率是不是一下子就提升了一倍。原來 O(n) 的時間復(fù)雜度瞬間可以變成 O(n/2) 的時間復(fù)雜度。

雙向循環(huán)鏈表

最后，我們也簡單的來介紹一下雙向循環(huán)鏈表。顧名思義，它就是在雙向鏈表的基礎(chǔ)上加上循環(huán)鏈表的概念。讓最后一個節(jié)點的 next 指向頭節(jié)點，讓頭節(jié)點的 prev 指向最后一個節(jié)點。說起來容易但實現(xiàn)起來其實要復(fù)雜很多，因為你不僅要關(guān)注最后一個節(jié)點的下級節(jié)點指向問題，而且還要關(guān)注頭節(jié)點的上級指向問題。所以在這里我們就不多做代碼演示了，最主要的就是在插入和刪除頭、尾節(jié)點的時候需要多注意它們上下級節(jié)點的指向。

總結(jié)

突然發(fā)現(xiàn)新大陸了吧？鏈表原來還有這么多種形式。當然，這還沒有說完，我們還有一個很高大上的十字鏈表沒說，不過其實十字鏈表也只是增加了