这篇文章主要介绍了关于php数据结构基础之双链表，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
什么是双链表？
上一篇实战PHP数据结构基础之单链表说到
单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。
而双链表每个节点有两个指针域，分别指向前驱和后继节点。单链表是单向的，而双链表是双向的。
常见操作
对双链表我们常见的操作有如下：
-
insert
立即学习“PHP免费学习笔记（深入）”；
insertBefore
insertAfter
insertAtFirst
insertAtLast
deleteFirst
deleteLast
delete
reverse
魔法映像企业网站管理系统下载技术上面应用了三层结构，AJAX框架，URL重写等基础的开发。并用了动软的代码生成器及数据访问类，加进了一些自己用到的小功能，算是整理了一些自己的操作类。系统设计上面说不出用什么模式，大体设计是后台分两级分类，设置好一级之后，再设置二级并选择栏目类型，如内容，列表，上传文件，新窗口等。这样就可以生成无限多个二级分类，也就是网站栏目。对于扩展性来说，如果有新的需求可以直接加一个栏目类型并新加功能操作
getNthNode
...
PHP语言实现
首先我们根据定义实现一个双链表的ListNode类。
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基础数据结构专题系列目录地址：https://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。
以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！
相关推荐：
