您好,登录后才能下订单哦!
这篇文章主要介绍php中链表的表现形式有哪些,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
就像上文所说的,我们让最后一个节点指向第一个节点,这样形成的链表就是一个循环链表,如下图所示:
关于循环的链表的操作我们不做详细的说明,其实大部分代码和单向链表是一样的,只是需要注意两个地方:
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 指向最后一个节点。说起来容易但实现起来其实要复杂很多,因为你不仅要关注最后一个节点的下级节点指向问题,而且还要关注头节点的上级指向问题。所以在这里我们就不多做代码演示了,最主要的就是在插入和删除头、尾节点的时候需要多注意它们上下级节点的指向。
以上是“php中链表的表现形式有哪些”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。