PHP数据结构基础之双链表

上一篇实战PHP数据结构基础之单链表说到

而双链表每个节点有两个指针域，分别指向前驱和后继节点。单链表是单向的，而双链表是双向的。

对双链表我们常见的操作有如下：

insert

insertBefore

insertAfter

insertAtFirst

insertAtLast

deleteFirst

deleteLast

delete

reverse

getNthNode

...

首先我们根据定义实现一个双链表的ListNode类。

html' target='_blank'>class ListNode public $data = null; public $next = null; public $prev = null; public function __construct(string $data) $this- data = $data;}

再来看链表类，首先需要3个私有属性，分别是头节点、尾巴节点和长度。

class DoubleLinkedList private $head = null; private $last = null; private $length = 0;}

接下来还是老规矩，直接看如何实现第一个即常用的插入，这是是一个平均时间复杂度为O(n)的操作。

/** * 插入一个节点 * @param string|null $data * @return bool * complexity O(n)public function insert(string $data = null) $newNode = new ListNode($data); if ($this- head) { $currentNode = $this- head; while ($currentNode) { if ($currentNode- next === null) { $currentNode- next = $newNode; $newNode- prev = $currentNode; $this- last = $newNode; $this- length++; return true; $currentNode = $currentNode- next; } else { $this- head = $newNode; $this- last = $newNode; $this- length++; return true;}

再来看如何删除节点。

/** * 删除一个节点 * @param string $data * @return bool|ListNode * complexity O(n)public function delete(string $query = null)if ($this- head) { $currentNode = $this- head; $prevNode = null; while ($currentNode) { if ($currentNode- data === $query) { if ($nextNode = $currentNode- next) { if ($prevNode) { $prevNode- next = $nextNode; $nextNode- prev = $prevNode; } else { $this- head = $nextNode; $nextNode- prev = null; unset($currentNode); } else { if ($prevNode) { $this- last = $prevNode; $prevNode- next = null; unset($currentNode); } else { $this- head = null; $this- last = null; $this- length--; return true; $prevNode = $currentNode; $currentNode = $currentNode- next; return false;}

反转双链表也不是很复杂。

public function reverse() if ($this- head !== null) { if ($this- head- next !== null) { $reversedList = null; $currentNode = $this- head; while ($currentNode !== null) { $next = $currentNode- next; $currentNode- next = $reversedList; $currentNode- prev = $next; $reversedList = $currentNode; $currentNode = $next; $this- last = $this- head; $this- head = $reversedList;}

双链表其他操作的详细实现可以参考 这里。

双链表是链表这种链式存取数据结构中相对于单链表比较特殊的部分，同样属于链表结构的还有单链表，环形链表和多链表。

PHP基础数据结构专题系列目录地址：http://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP ！

相关推荐：

PHP数据结构基础之栈

php7+的php-fpm参数配置的注意事项

以上就是PHP数据结构基础之双链表的详细内容，PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。