php中链表的表现形式有哪些
这篇文章主要介绍php中链表的表现形式有哪些，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
创新互联长期为1000+客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为花都企业提供专业的成都网站设计、成都网站建设、外贸网站建设，花都网站改版等技术服务。拥有十余年丰富建站经验和众多成功案例,为您定制开发。
循环链表
就像上文所说的，我们让最后一个节点指向第一个节点，这样形成的链表就是一个循环链表，如下图所示：
关于循环的链表的操作我们不做详细的说明，其实大部分代码和单向链表是一样的，只是需要注意两个地方：
1.初始化、插入操作的时候，注意最后一个节点的指向，最后一个节点的 next 要指向第一个节点
2.判断链表遍历是否完成的条件为 item->next == head ，也就是说，判断这个节点的下一个节点如果是头节点的话，链表就遍历完成了。
双向链表
双向链表则是在 LinkedList 这个类里面增加一个属性来指向上一个节点。
// 双向链表
class LinkedList
{
public $data;
public $prev;
public $next;
}
接下来，我们初始化一个双向链表。
/**
* 生成链表
*/
function createLinkedList()
{
$list = new LinkedList();
$list->data = null;
$list->next = null;
$list->prev = null; // ** 全部都初始化为 null **
return $list;
}
/**
* 初始化链表
* @param array $data 链表中要保存的数据，这里以数组为参考
* @return LinkedList 链表数据
*/
function Init(array $data)
{
// 初始化
$list = createLinkedList();
$r = $list;
foreach ($data as $key => $value) {
$link = new LinkedList();
$link->data = $value;
$link->next = null;
$r->next = $link;
$link->prev = $r; // ** 增加上级指向 **
$r = $link;
}
return $list;
}
$link = Init(range(1, 10));
var_dump($link);
var_dump($link->next->next->next->next);
// object(LinkedList)#5 (3) {
// ["data"]=>
// int(4)
// ["prev"]=>
// object(LinkedList)#4 (3) {
// ["data"]=>
// int(3)
// ["prev"]=>
// object(LinkedList)#3 (3) {
// ["data"]=>
// int(2)
// ["prev"]=>
// object(LinkedList)#2 (3) {
// ["data"]=>
// int(1)
// ["prev"]=>
// object(LinkedList)#1 (3) {
// ["data"]=>
// NULL
// ["prev"]=>
// NULL
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// object(LinkedList)#6 (3) {
// ["data"]=>
// int(5)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#7 (3) {
// ["data"]=>
// int(6)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#8 (3) {
// ["data"]=>
// int(7)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#9 (3) {
// ["data"]=>
// int(8)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#10 (3) {
// ["data"]=>
// int(9)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#11 (3) {
// ["data"]=>
// int(10)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// NULL
// }
// }
// }
// }
// }
// }
// }
echo $link->next->next->next->next->data, PHP_EOL; // 4
echo $link->next->next->next->next->prev->data, PHP_EOL; // 3可以看出，与单向链表不同的地方就在于多增加了对于 prev 属性的操作。这里还是比较好理解的。直接打印链表会显示很多的 *RECURSION* 内容，这是 PHP 的一种输出的保护机制，这个标识说明当前这个属性变量是有递归类型的。
/**
* 链表指定位置插入元素
* @param LinkedList $list 链表数据
* @param int $i 位置
* @param mixed $data 数据
*/
function Insert(LinkedList &$list, int $i, $data)
{
$j = 0;
$item = $list;
// 遍历链表，找指定位置的前一个位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 创建一个新节点
$s = new LinkedList();
$s->data = $data;
// 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是当前的 i 节点
$s->next = $item->next;
// ** 增加当前新创建的节点的上级指向 **
$s->prev = $item;
// 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
$item->next = $s;
// ** 将下级节点的 prev 指向新创建的这个节点 **
$s->next->prev = $s;
return true;
}链表的插入其实就是增加了两行代码，一个是当前新创建的节点的上级的指向，也就是将这个新节点的上级指定为 i-1 个节点。而另一个是将原来 i 位置节点的上级指向修改为当前新创建的这个节点。
/**
* 删除链表指定位置元素
* @param LinkedList $list 链表数据
* @param int $i 位置
*/
function Delete(LinkedList &$list, int $i)
{
$j = 0;
$item = $list;
// 遍历链表，找指定位置的前一个位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 使用一个临时节点保存当前节点信息，$item 是第 i-1 个节点，所以 $item->next 就是我们要找到的当前这个 i 节点
$temp = $item->next;
// 让当前节点，也就是目标节点的上一个节点， i-1 的这个节点的下一跳（原来的 i 位置的节点）变成原来 i 位置节点的下一跳 next 节点，让i位置的节点脱离链条
$item->next = $temp->next;
// ** 让目标下一个节点的上级指针指向当前这个节点 **
$temp->next->prev = $item;
return true;
}与插入节点操作类似，删除节点操作除了将 i-1 个位置节点的数据的下一个节点的指向变为 i 节点的下一级节点的指向之外，还要将 i 的下一级节点的上级节点指向改为 i-1 节点。
其实，双向链表的定义和操作相比单向链表来说差别并不大，就是多了一个 prev 用来指向上一级节点而已，本质上也只是多了对于 prev 这个属性的操作而已。那么，多出来的这一个上级指针能带来什么好处呢？在遍历链表的时候，我们通过 prev ，就多了一种遍历方式，也就是反向的对链表进行遍历。在查找某个元素的时候，我们可以从两个方向同时进行查找，效率是不是一下子就提升了一倍。原来 O(n) 的时间复杂度瞬间可以变成 O(n/2) 的时间复杂度。
双向循环链表
最后，我们也简单的来介绍一下双向循环链表。顾名思义，它就是在双向链表的基础上加上循环链表的概念。让最后一个节点的 next 指向头节点，让头节点的 prev 指向最后一个节点。说起来容易但实现起来其实要复杂很多，因为你不仅要关注最后一个节点的下级节点指向问题，而且还要关注头节点的上级指向问题。所以在这里我们就不多做代码演示了，最主要的就是在插入和删除头、尾节点的时候需要多注意它们上下级节点的指向。
以上是“php中链表的表现形式有哪些”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！
分享文章：php中链表的表现形式有哪些
标题链接：http://scjbc.cn/article/gipeho.html
