在上一篇文章中，我们已经说过除了简单的单向链表之外，还有其他几种形式的链表。当然，这也是链表结构的一大特点，非常灵活方便。我们简单的想一下，如果最后一个节点的next指向回第一个节点，那么这就形成了一个环，就是一个循环链表。如果我们在每个节点上加上一个指向前一个节点的prev属性，那么这个链表就变成了一个双向链表。如果我们在双向链表的基础上也让最后一个节点的next指向第一个节点，同时让第一个节点的prev指向最后一个节点，这不是双向的吗循环链表？让我们详细看一下。循环链表上面说到，我们让最后一个节点指向第一个节点，这样形成的链表就是循环链表，如下图所示：循环链表。部分代码与单向链表相同，但需要注意两点：1、初始化和插入操作时，注意最后一个节点的指向，最后一个节点的下一个节点node必须指向第一个节点2.判断链表是否遍历完成条件是item->next==head，也就是说如果判断这个节点的下一个节点是头节点，链表遍历完成。双向链表双向链表在LinkedList类中增加了一个属性指向上一个节点。//双向链表类LinkedList{public$data;公共$prev;public$next;}接下来，我们初始化一个双向链表。/***生成链表*/functioncreateLinkedList(){$list=newLinkedList();$列表->数据=空；$列表->下一个=空；$list->prev=null;//**all都初始化为null**return$list;}/***初始化链表*@paramarray$data链表中要保存的数据，这里以数组作为引用*@returnLinkedList链表数据*/functionInit(array$data){//初始化$list=createLinkedList();$r=$列表；foreach($dataas$key=>$value){$link=newLinkedList();$链接->数据=$值；$link->next=null;$r->下一个=$链接；$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*//}//["下一个"]=>//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;//4echo$link->next->next->next->next->prev->data,PHP_EOL;//3可以看出和单向链表的区别就是增加了prev属性的操作，这里比较容易理解。直接打印链表会显示很多*RECURSION*内容，这是PHP的一种输出保护机制。该标记表示当前属性变量具有递归类型。/***在链表的指定位置插入元素*@paramLinkedList$list链表数据*@paramint$iposition*@parammixed$datadata*/functionInsert(LinkedList&$list,int$i,$数据){$j=0;$项目=$列表；//遍历链表，找到指定位置的上一个位置while($j<$i-1){$item=$item->next;$j++;}//如果项目不存在或$i>n+1或$i<0if($item==null||$j>$i-1){returnfalse;}//创建一个新节点$s=newLinkedList();$s->数据=$数据；//新建节点的下一个节点指向原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;返回真；}链表的插入其实就是加入两行代码，一行是指向当前新建节点的上级指针，即指定新节点的上级为i-1个节点。而另一种是将原来的i位置节点的父点修改为当前新建的节点。/***删除链表指定位置的元素*@paramLinkedList$list链表数据*@paramint$iposition*/functionDelete(LinkedList&$list,int$i){$j=0;$项目=$列表；//遍历链表，找到指定位置的上一个位置while($j<$i-1){$item=$item->next;$j++;}//如果项目不存在或$i>n+1或$i<0if($item==null||$j>$i-1){returnfalse;}//使用临时节点保存当前节点信息，$item是第i-1个节点，所以$item->next就是我们要找的当前i节点$temp=$item->next;//让当前节点，也就是目标节点的前一个节点，成为i-1节点的下一跳（原i位置的节点）成为原节点i位置的下一跳next节点,使得位置i的节点出链$item->next=$temp->next;//**让目标next节点的上层指针指向当前This节点**$temp->next->prev=$item;returntrue;}和插入节点的操作类似，只是删除节点的操作改变了i-1位置节点的数据的下一个节点的指向为i节点的指向，除了低-的指向级节点，i的下级节点的上级节点的指向要改为i-1节点。事实上，双向链表的定义和操作与单向链表没有太大区别。只是多了一个prev用来指向上层节点。本质上只是对prev的属性多了一些操作。那么，这个额外的高级指针能带来什么好处呢？在遍历链表的时候，我们使用prev添加一个遍历方法，即反向遍历链表。在查找一个元素的时候，我们可以同时从两个方向进行查找，效率一下子翻了一番。原来的O(n)时间复杂度可以瞬间变成O(n/2)时间复杂度。双向循环链表最后，我们也简单介绍一下双向循环链表。顾名思义，就是在双向链表的基础上加上循环链表的概念。让最后一个节点的next指向头节点，让头节点的prev指向最后一个节点。说起来容易，实际实现起来要复杂得多，因为你不仅要注意最后一个节点的从属节点的指向问题，还要注意头节点的父节点的指向问题。所以这里我们就不做更多的代码演示了。最重要的是，在插入和删除头尾节点时，我们需要多注意它们上下节点的方向。概要突然发现新大陆对吧？链表有很多种形式。当然，这还没有结束。我们还有一个非常大的交叉链表，但其实交叉链表只是增加了更多的指向属性，基本数据字段永远是相同的数据。其实最常见的单向链表，也就是上一篇详细介绍过的单向链表，才是我们学习链表真正需要掌握的重点。所以，大家不用着急和恐慌，掌握了普通的单向链表就可以秒杀大部分人，但是今天学到的呢？如果你能掌握最好，如果你不能掌握，你至少可以熟悉它。做人最重要的是要快乐。不要太勉强自己。是最重要的。关于线性表的内容到此结束。物理结构的存储就是这样，然后我们将进入逻辑结构的世界。也是从最简单的，也就是栈和队列说起。别怕，跟树和图比起来，他们真的是在洒水！！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20其他形式的链表.php参考资料：《数据结构》第二版，严为民《数据结构》第二版，陈越《数据结构高分笔记》2020版，天琴考研各自媒体平台均可搜索【硬核项目经理】
