目录
循环链表
双向链表
双向循环链表
总结
首页 后端开发 PHP问题 链表有没有其他的表现形式?

链表有没有其他的表现形式?

Jul 27, 2021 pm 05:52 PM
php

在上篇文章中,我们已经说过了链表除了简单的那一种单向链表外,还有其它的几种形式。当然,这也是链表这种结构的一大特点,非常地灵活和方便。我们简单的想一想,如果让最后一个节点的next指回第一个节点,那么这就样就形成了一个环,这就是一个循环链表了。

如果我们在每个节点上增加一个指向上一个节点的 prev 属性,那么这个链表就变成了一个双向链表了。如果我们在双向链表的基础上也让最后一个节点的 next 指向第一个节点,同时让第一个节点的 prev 指向最后一个节点,这不就是一个双向循环链表了嘛。下面我们就来具体的看一看。

循环链表

就像上文所说的,我们让最后一个节点指向第一个节点,这样形成的链表就是一个循环链表,如下图所示:

bVcTAuV.webp.jpg

关于循环的链表的操作我们不做详细的说明,其实大部分代码和单向链表是一样的,只是需要注意两个地方:

1.初始化、插入操作的时候,注意最后一个节点的指向,最后一个节点的 next 要指向第一个节点

2.判断链表遍历是否完成的条件为 item->next == head ,也就是说,判断这个节点的下一个节点如果是头节点的话,链表就遍历完成了。

双向链表

双向链表则是在 LinkedList 这个类里面增加一个属性来指向上一个节点。

// 双向链表
class LinkedList
{
    public $data;

    public $prev;
    public $next;
}
登录后复制

bVcTAuW.webp.jpg

接下来,我们初始化一个双向链表。

/**
 * 生成链表
 */
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 指向最后一个节点。说起来容易但实现起来其实要复杂很多,因为你不仅要关注最后一个节点的下级节点指向问题,而且还要关注头节点的上级指向问题。所以在这里我们就不多做代码演示了,最主要的就是在插入和删除头、尾节点的时候需要多注意它们上下级节点的指向。

bVcTAuX.webp.jpg

总结

突然发现新大陆了吧?链表原来还有这么多种形式。当然,这还没有说完,我们还有一个很高大上的十字链表没说,不过其实十字链表也只是增加了更多的指向属性而已,基本的数据域永远都还是那一个 data 。其实最普通的单向链表,也就是上一篇文章详细介绍的那个才是我们对于链表学习真正要掌握的重点。

因此,大家不必焦虑,也不用恐慌,掌握好普通的单向链表你就可以秒杀绝大部分人了,而今天学习的这些呢?能掌握最好,掌握不了最少混个脸熟就可以了,做人,最重要的是开心了,不要把自己逼的太狠,太狠的话,要么成龙,要么成虫,认清自己的现状和能力才是最重要的。

关于线性表的内容到此为止。物理结构的存储问题就是这样了,接下来我们就要逻辑结构的世界了。也是从最简单的开始,那就是栈和队列,不要怕,它们和 树、图 比起来真的是洒洒水啦!!

测试代码:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20链表的其它形式.php
登录后复制

推荐学习:php视频教程

以上是链表有没有其他的表现形式?的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

我后悔之前不知道的 7 个 PHP 函数 我后悔之前不知道的 7 个 PHP 函数 Nov 13, 2024 am 09:42 AM

如果您是一位经验丰富的 PHP 开发人员,您可能会感觉您已经在那里并且已经完成了。您已经开发了大量的应用程序,调试了数百万行代码,并调整了一堆脚本来实现操作

您如何在PHP中解析和处理HTML/XML? 您如何在PHP中解析和处理HTML/XML? Feb 07, 2025 am 11:57 AM

本教程演示了如何使用PHP有效地处理XML文档。 XML(可扩展的标记语言)是一种用于人类可读性和机器解析的多功能文本标记语言。它通常用于数据存储

在PHP API中说明JSON Web令牌(JWT)及其用例。 在PHP API中说明JSON Web令牌(JWT)及其用例。 Apr 05, 2025 am 12:04 AM

JWT是一种基于JSON的开放标准,用于在各方之间安全地传输信息,主要用于身份验证和信息交换。1.JWT由Header、Payload和Signature三部分组成。2.JWT的工作原理包括生成JWT、验证JWT和解析Payload三个步骤。3.在PHP中使用JWT进行身份验证时,可以生成和验证JWT,并在高级用法中包含用户角色和权限信息。4.常见错误包括签名验证失败、令牌过期和Payload过大,调试技巧包括使用调试工具和日志记录。5.性能优化和最佳实践包括使用合适的签名算法、合理设置有效期、

php程序在字符串中计数元音 php程序在字符串中计数元音 Feb 07, 2025 pm 12:12 PM

字符串是由字符组成的序列,包括字母、数字和符号。本教程将学习如何使用不同的方法在PHP中计算给定字符串中元音的数量。英语中的元音是a、e、i、o、u,它们可以是大写或小写。 什么是元音? 元音是代表特定语音的字母字符。英语中共有五个元音,包括大写和小写: a, e, i, o, u 示例 1 输入:字符串 = "Tutorialspoint" 输出:6 解释 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。总共有 6 个元

解释PHP中的晚期静态绑定(静态::)。 解释PHP中的晚期静态绑定(静态::)。 Apr 03, 2025 am 12:04 AM

静态绑定(static::)在PHP中实现晚期静态绑定(LSB),允许在静态上下文中引用调用类而非定义类。1)解析过程在运行时进行,2)在继承关系中向上查找调用类,3)可能带来性能开销。

什么是PHP魔术方法(__ -construct,__destruct,__call,__get,__ set等)并提供用例? 什么是PHP魔术方法(__ -construct,__destruct,__call,__get,__ set等)并提供用例? Apr 03, 2025 am 12:03 AM

PHP的魔法方法有哪些?PHP的魔法方法包括:1.\_\_construct,用于初始化对象;2.\_\_destruct,用于清理资源;3.\_\_call,处理不存在的方法调用;4.\_\_get,实现动态属性访问;5.\_\_set,实现动态属性设置。这些方法在特定情况下自动调用,提升代码的灵活性和效率。

See all articles