实战PHP数据结构基础之单链表

xumenger 发布于2019-07-01 10:06 / 2698人阅读

摘要：常见操作对单链表我们常见的操作有如下语言实现首先我们根据定义实现一个类。单链表是链表这种链式存取数据结构中基础的部分，同样属于链表结构的还有双链表，环形链表和多链表。专题系列基础数据结构专题系列目录地址主要使用语法总结基础的数据结构和算法。

什么是链表？

链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。

常见操作

对单链表我们常见的操作有如下：

insert

insertBefore

insertAfter

insertAtFirst

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基础数据结构专题系列目录地址：https://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。

混合云专线服务单链表数据单链表存储结构单链表数据结构 c++ 单链表链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28795.html

实战PHP数据结构基础之双链表

摘要：什么是双链表上一篇实战数据结构基础之单链表说到单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。什么是双链表？上一篇实战PHP数据结构基础之单链表说到单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。而双链表每个节点有两个指针域，分别指向前驱...

Michael_Lin 2019-07-01 10:07 评论0 收藏0
PHPer也刷《剑指Offer》之链表

摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。温故知新链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。根据类型可以分为单链表、双链表、环形链表、...

daydream 2019-07-01 10:11 评论0 收藏0
SegmentFault 技术周刊 Vol.31 - 码农也要学算法

摘要：记作称为算法的渐进时间复杂度，简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构，可以存储有序的元素集合。首先在大的分类上，它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候，意味着我们正步入一个算法的时代。计算...

cgspine 2019-06-26 15:45 评论0 收藏0
[个人心得]数据结构之单链表

摘要：一个单向链表包含两个值当前节点的值和一个指向下一个节点的链接。为退出循环即已到了最后一个节点那么它的为加入节点后，要把单链表长度加一。第个节点是运行结果个人源码地址单链表就写到这里咯，接下来还会写其他的数据结构本人也在学习当中。维基百科链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。链表中最简单的一种是单向链...

bingchen 2019-08-21 17:53 评论0 收藏0
图解几种常见的线性表

摘要：下面来看一下，有哪些数据结构属于线性表吧栈特性先进后出只有唯一的一个出入口介绍栈又名堆栈，它是一种运算受限的线性表。原文是在我自己博客中，小伙伴也可以点阅读原文进行跳转查看，还有好听的背景音乐噢背景音乐已取消~ 2333333 线性表什么是线性表？就是一种连续或间断存储的数组，这里的连续和间断是针对物理内存空间中线性表元素之间是否连续，其中连续数组对应内置数组的实现方式，间断数组对...

wawor4827 2019-07-01 10:01 评论0 收藏0