鍊錶有沒有其他的表現形式？-PHP問題-PHP中文網

在上篇文章中，我們已經說過了鍊錶除了簡單的那一種單向鍊錶外，還有其它的幾種形式。當然，這也是鍊錶這種結構的一大特點，非常靈活和方便。我們簡單的想一想，如果讓最後一個節點的next指回第一個節點，那麼這就樣就形成了一個環，這就是一個循環鍊錶了。

如果我們在每個節點上增加一個指向上一個節點的 prev 屬性，那麼這個鍊錶就變成了一個雙向鍊錶了。如果我們在雙向鍊錶的基礎上也讓最後一個節點的 next 指向第一個節點，同時讓第一個節點的 prev 指向最後一個節點，這不就是一個雙向循環鍊錶了嘛。下面我們就來具體的看一看。

循環鍊錶

就像上文所說的，我們讓最後一個節點指向第一個節點，這樣形成的鍊錶就是一個循環鍊錶，如下圖所示：

鍊錶有沒有其他的表現形式？

關於循環的鍊錶的操作我們不做詳細的說明，其實大部分程式碼和單向鍊錶是一樣的，只是需要注意兩個地方：

# 1.初始化、插入操作的時候，注意最後一個節點的指向，最後一個節點的next 要指向第一個節點

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

雙向鍊錶

雙向鍊錶則是在 LinkedList 這個類別裡面增加一個屬性來指向上一個節點。

// 双向链表
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 链表中要保存的数据，这里以数组为参考
 * @return LinkedList 链表数据
 */
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* 內容，這是 PHP 的一種輸出的保護機制，這個標識說明目前這個屬性變數是有遞迴類型的。

/**
 * 链表指定位置插入元素
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 * @param mixed $data 数据
 */
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;
    }

    // 创建一个新节点
    $s = new LinkedList();
    $s->data = $data;

    // 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是当前的 i 节点
    $s->next = $item->next;

    // ** 增加当前新创建的节点的上级指向 **
    $s->prev = $item;

    // 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
    $item->next = $s;

    // ** 将下级节点的 prev 指向新创建的这个节点 **
    $s->next->prev = $s;

    return true;
}

登入後複製

鍊錶的插入其實就是增加了兩行程式碼，一個是目前新建立的節點的上級的指向，也就是將這個新節點的上級指定為 i-1 個節點。而另一個是將原來 i 位置節點的上級指向修改為目前新建立的這個節點。

/**
 * 删除链表指定位置元素
 * @param LinkedList $list 链表数据
 * @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;
    }

    // 使用一个临时节点保存当前节点信息，$item 是第 i-1 个节点，所以 $item->next 就是我们要找到的当前这个 i 节点
    $temp = $item->next;
    // 让当前节点，也就是目标节点的上一个节点， i-1 的这个节点的下一跳（原来的 i 位置的节点）变成原来 i 位置节点的下一跳 next 节点，让i位置的节点脱离链条
    $item->next = $temp->next;

    // ** 让目标下一个节点的上级指针指向当前这个节点 **
    $temp->next->prev = $item;

    return true;
}

登入後複製

與插入節點操作類似，刪除節點操作除了將i-1 個位置節點的資料的下一個節點的指向變為i 節點的下一級節點的指向之外，還要將i的下一級節點的上級節點指向改為i-1 節點。

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

雙向循環鍊錶

最後，我們也簡單的來介紹雙向循環鍊錶。顧名思義，它就是在雙向鍊錶的基礎上加上循環鍊錶的概念。讓最後一個節點的 next 指向頭節點，讓頭節點的 prev 指向最後一個節點。說起來容易但實現起來其實要複雜很多，因為你不僅要關注最後一個節點的下級節點指向問題，還要關注頭節點的上級指向問題。所以在這裡我們就不多做程式碼示範了，最主要的就是在插入和刪除頭、尾節點的時候需要多注意它們上下級節點的指向。

鍊錶有沒有其他的表現形式？

總結

突然發現新大陸了吧？鍊錶原來還有這麼多種形式。當然，這還沒說完，我們還有一個很高大上的十字鍊錶沒說，不過其實十字鍊錶也只是增加了更多的指向屬性而已，基本的資料域永遠都還是那一個 data 。其實最普通的單向鍊錶，也就是上一篇文章詳細介紹的那個才是我們對於鍊錶學習真正要掌握的重點。

因此，大家不必焦慮，也不用恐慌，掌握好普通的單向鍊錶你就可以秒殺絕大部分人了，而今天學習的這些呢？能掌握最好，掌握不了最少混個臉熟就可以了，做人，最重要的是開心了，不要把自己逼的太狠，太狠的話，要么成龍，要么成蟲，認清自己的現狀和能力才是最重要的。

关于线性表的内容到此为止。物理结构的存储问题就是这样了，接下来我们就要逻辑结构的世界了。也是从最简单的开始，那就是栈和队列，不要怕，它们和树、图比起来真的是洒洒水啦！！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20链表的其它形式.php

登入後複製

推荐学习：php视频教程

以上是鍊錶有沒有其他的表現形式？的詳細內容。更多資訊請關注PHP中文網其他相關文章！