什么是链表？
链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。
常见操作
对单链表我们常见的操作有如下：
- 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 = $data; } public function __get($var) { return $this->$var; } public function __set($var, $val) { return $this->$var = $val; }} 再来看链表类，首先需要2个私有属性，分别是头节点和长度。
class LinkedList{ private $head; private $length;} 下面我们长话短说，直接看如何实现第一个即常用的插入，这是是一个平均时间复杂度为O(n)的操作。
/** * 插入一个节点 * @param string|null $data * @return bool * complexity O(n) */public function insert(string $data = 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 === $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基础数据结构专题系列目录地址： 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。