在上篇文章中，咱们曾经说过了链表除了简略的那一种单向链表外，还有其它的几种模式。当然，这也是链表这种构造的一大特点，十分地灵便和不便。咱们简略的想一想，如果让最初一个节点的 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

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】