上一篇文章写了线性表的基本概念以及用C语言实现链表，有兴趣的同学可以看看：线性表--链表（C语言实现）。
现在，我们来看看用PHP来实现链表。
我们都知道，链表由一个个结点组成。在c语言中，我们用结构来定义一个结点，那么在PHP中我们用什么来定义结点？
当然是类。
<?php//用面向对象的思想定义结点class Node{ ???public $value; ???public $next = null;}先给出创建和遍历链表的代码，我们再说说链表的插入和删除操作，比起用顺序存储结构实现线性表的插入或者删除操作（也就是用一维数组实现线性表），链表为什么更快。
<?php/** * LinkedList * Author: TianJiankun */
// 定义结点class Node{ ???public $value; ???public $next = null;}
class LinkedList{ ???public $list;
???//传入一个数组，创建链表 ???public function createList($arr) ???{ ???????$head = new Node(); ???????$a = $head; ???????for ($i = 0; $i<count($arr) ; $i++) { ???????????$pNode = new Node(); ???????????while ($a->next) { ???????????????$a = $a->next; ???????????} ???????????$pNode->value = $arr[$i]; ???????????$a->next = $pNode; ???????} ???????$this->list = $head; ???} ???//打印链表的数据 ???public function printList() ???{ ???????$list = $this->list; ???????$pNode = $list->next; ???????if (! $pNode) { ???????????echo "empty list"; ???????} ???????while ($pNode != null) { ???????????echo $pNode->value."\r\n"; ???????????$pNode = $pNode->next; ???????} ???} ???//打印整个链表（可以清晰的看到内部结构） ???public function printStructure() ???{ ???????$list = $this->list; ???????$pNode = $list->next; ???????if (! $pNode) { ???????????echo "empty list"; ???????} ???????$str = ‘<pre style="display: block;padding: 9.5px;margin: 44px 0 0 0;">‘; ???????$show_data = print_r($pNode, true); ???????$str .= $show_data; ???????$str .= ‘</pre>‘; ???????echo $str; ???}}$list = new LinkedList();$list->createList([1,2,3,4,5]);$list->printStructure();$list->printList();
我们举个例子来说明顺序存储结构插入的劣势之处。
假设你有一个十层书架，并且你有一千本书，你把书按字母A~Z排序，整整齐齐放在书架上。
后来，你买了一本《计算机程序的构造和解释》，这个时候你要把这本书插入字母J的位置，那么，你就得在新书插入的这个位置开始，把后面所有的书都往后移动一个位置。也就是说，如果插入的位置后面有500个元素的话，你就得做500个操作。这就是顺序存储结构的插入操作。
而链表依靠指针域，就不会这么麻烦。上代码。
???//在第n个位置插入一个元素,如果成功返回true ???public function insert($value, $n) ???{ ???????$p = $this->list; ???????$i = 1; ???????while ($p->next && $n>$i) { ???????????$p = $p->next; ???????????++$i; ???????} ???????//$q就是第n个元素 ???????$q = $p->next; ???????if (! $q || $n<$i) { ???????????echo ‘insert error‘; ???????????die; ???????} ???????$s = new Node(); ???????$p->next = $s; ???????$s->value = $value; ???????$s->next = $q; ???????return true; ???} //删除第n个元素,如果成功返回被删除元素的值 ???public function delete($n) ???{ ???????$p = $this->list; ???????$i = 1; ???????while ($p->next && $n>$i) { ???????????$p = $p->next; ???????????++$i; ???????} ???????//$q就是第n个元素 ???????$q = $p->next; ???????if (! $q || $n<$i) { ???????????echo ‘delete error‘; ???????????die; ???????} ???????$p->next = $q->next; ???????$value = $q->value; ???????unset($q); ???????return $value; ???}整体代码：
<?phpclass Node{ ???public $value; ???public $next = null;}class LinkedList{ ???public $list; ???//传入一个数组，创建链表 ???public function createList($arr) ???{ ???????$head = new Node(); ???????$a = $head; ???????for ($i = 0; $i<count($arr) ; $i++) { ???????????$pNode = new Node(); ???????????while ($a->next) { ???????????????$a = $a->next; ???????????} ???????????$pNode->value = $arr[$i]; ???????????$a->next = $pNode; ???????} ???????$this->list = $head; ???} ???//打印链表的数据 ???public function printList() ???{ ???????$list = $this->list; ???????$pNode = $list->next; ???????if (! $pNode) { ???????????echo "empty list"; ???????} ???????while ($pNode != null) { ???????????echo $pNode->value."\r\n"; ???????????$pNode = $pNode->next; ???????} ???} ???//打印整个链表（可以清晰的看到内部结构） ???public function printStructure() ???{ ???????$list = $this->list; ???????$pNode = $list->next; ???????if (! $pNode) { ???????????echo "empty list"; ???????} ???????$str = ‘<pre style="display: block;padding: 9.5px;margin: 44px 0 0 0;">‘; ???????$show_data = print_r($pNode, true); ???????$str .= $show_data; ???????$str .= ‘</pre>‘; ???????echo $str; ???} ???????//判断链表是否为空 ???public function isEmpty() ???{ ???????return $this->list->next == null; ???} ???//删除第n个元素,如果成功返回被删除元素的值 ???public function delete($n) ???{ ???????$p = $this->list; ???????$i = 1; ???????while ($p->next && $n>$i) { ???????????$p = $p->next; ???????????++$i; ???????} ???????//$q就是第n个元素 ???????$q = $p->next; ???????if (! $q || $n<$i) { ???????????echo ‘delete error‘; ???????????die; ???????} ???????$p->next = $q->next; ???????$value = $q->value; ???????unset($q); ???????return $value; ???} ???//在第n个位置插入一个元素,如果成功返回true ???public function insert($value, $n) ???{ ???????$p = $this->list; ???????$i = 1; ???????while ($p->next && $n>$i) { ???????????$p = $p->next; ???????????++$i; ???????} ???????//$q就是第n个元素 ???????$q = $p->next; ???????if (! $q || $n<$i) { ???????????echo ‘insert error‘; ???????????die; ???????} ???????$s = new Node(); ???????$p->next = $s; ???????$s->value = $value; ???????$s->next = $q; ???????return true; ???} ???//读取第i个元素 ???public function getElem($n) ???{ ???????$p = $this->list->next; ???????$i = 1; ???????while ($p && $n>$i) { ???????????$p = $p->next; ???????????++$i; ???????} ???????if (! $p && $n<$i) { ???????????echo "get error"; ???????????die; ???????} ???????$value = $p->value; ???????return $value; ???} ???????//整表删除,成功返回true ???public function clearList() ???{ ???????$p = $this->list->next; ???????while ($p) { ???????????$q = $p->next; ???????????unset($p); ???????????$p = $q; ???????} ???????$this->list->next = null; ???????return true; ???}}$list = new LinkedList();$list->createList([1,2,3,4,5]);echo $list->delete(5)."\r\n";$list->insert(100,2);echo $list->getElem(3);$list->printStructure();$list->printList();$list->clearList();var_dump($list->isEmpty());$list->printStructure();线性表--链表（PHP实现）
原文地址：https://www.cnblogs.com/tianjiankun/p/8605089.html