php|实战PHP数据结构基础之单链表算法|PHP|数据结构

什么是链表？
链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。
常见操作
对单链表我们常见的操作有如下：
- insert
- insertBefore
- insertAfter
- insertAtFirst
- search
- deleteFirst
- deleteLast
- delete
- reverse
- getNthNode
- …
PHP语言实现
首先我们根据定义实现一个ListNode类。

class ListNode { private $data; private $next; public function __construct(string $data) { $this->data = https://www.it610.com/article/$data; }public function __get($var) { return $this->$var; }public function __set($var, $val) { return $this->$var = $val; } }

【php|实战PHP数据结构基础之单链表】再来看链表类，首先需要2个私有属性，分别是头节点和长度。

class LinkedList { private $head; private $length; }

下面我们长话短说，直接看如何实现第一个即常用的插入，这是是一个平均时间复杂度为O(n)的操作。

/** * 插入一个节点 * @param string|null $data * @return bool * complexity O(n) */ public function insert(string $data = https://www.it610.com/article/null) { $newNode = new ListNode($data); if ($this->head === null) { $this->head = &$newNode; } else { $currentNode = $this->head; while ($currentNode->next !== null) { $currentNode = $currentNode->next; }$currentNode->next = $newNode; }$this->length++; return true; }

再来看搜索，同样是一个平均时间复杂度为O(n)的操作。

/** * 搜索一个节点 * @param string $data * @return bool|ListNode * complexity O(n) */ public function search(string $data) { if ($this->length > 0) { $currentNode = $this->head; while ($currentNode !== null) { if ($currentNode->data =https://www.it610.com/article/== $data) { return $currentNode; }$currentNode = $currentNode->next; } }return false; }

反转单链表

public function reverse() { if ($this->head !== null) { if ($this->head->next !== null) { $reveredList = null; $next = null; $currentNode = $this->head; while ($currentNode !== null) { $next = $currentNode->next; $currentNode->next = $reveredList; $reveredList = $currentNode; $currentNode = $next; }$this->head = $reveredList; } }}

单链表其他操作的详细实现可以参考这里。
单链表是链表这种链式存取数据结构中基础的部分，同样属于链表结构的还有双链表，环形链表和多链表。
专题系列 PHP基础数据结构专题系列目录地址：https://github.com/… 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。