基于实际PHP数据结构什么是双链表？上一篇基于实际PHP数据结构的单链表说了单链表是由一个个对象作为节点组成的。每个节点都有一个指向下一个节点的指针，最后一个节点的指针字段指向空。每个节点都可以存储任何数据类型。双链表的每个节点都有两个指针字段，分别指向前驱节点和后继节点。单链表是单向的，而双向链表是双向的。常用操作我们对双链表的常用操作如下：类ListNode{public$data=null;公共$下一个=空；公共$prev=空；公共函数__construct(string$data){$this->data=$data;再来看链表类，我们首先需要3个私有属性，分别是头节点、尾节点和长度。类DoubleLinkedList{private$head=null;私人$last=null；private$length=0;}接下来还是老规矩，只看第一个也是常用的插入是怎么实现的，这是一个平均时间复杂度为O(n)的操作。/***插入一个节点*@paramstring|null$data*@returnbool*complexityO(n)*/publicfunctioninsert(string$data=null){$newNode=newListNode($data);如果（$this->head）{$currentNode=$this->head;while($currentNode){if($currentNode->next===null){$currentNode->next=$newNode;$newNode->prev=$currentNode;$this->last=$newNode;$这个->长度++；返回真；}$currentNode=$currentNode->next;}}else{$this->head=&$newNode;$this->last=$newNode;$这个->长度++；返回真；}}再来看看如何删除节点。/***删除一个节点*@paramstring$data*@returnbool|ListNode*复杂度O(n)*/publicfunctiondelete(string$query=null){if($this->head){$currentNode=$这个->头；$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;}未设置（$currentNode）；}else{if($prevNode){$this->last=$prevNode;$prevNode->next=null;取消设置（$currentNode）；}else{$this->head=null;$this->last=null;}}$这个->长度--;返回真；}$prevNode=$currentNode;$currentNode=$currentNode->下一个；}}returnfalse;}反转双链表并不复杂publicfunctionreverse(){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语言特性的深入研究。
