Laravel
话题列表 社区 Wiki 优质外文 招聘求职 Laravel 实战教程 社区文档
登录
注册

画江湖之数据结构 [第一话:链表] 双向链表

Krisji 的个人博客 / 0 / 2 / 创建于 5年前 / 更新于 5年前

链表

1 双链表

概括：双向链表有两个引用分别指向前后节点。优势方便向前查询数据。
file
请看上图：data为数据，pre为指向前个节点的引用，next为指向后个节点的引用 。

完整代码块：

<?php

/**
 * 节点实现
 */
class Node
{
    /**
     * 数据元素
     * @var
     */
    public $item;

    /**
     * 前驱节点
     * @var
     */
    public $prev;

    /**
     * 后继节点
     * @var
     */
    public $next;

    /**
     * Node constructor.
     * @param $item
     */
    public function __construct($item)
    {
        $this->item = $item;
        $this->prev = null;
        $this->next = null;
    }
}

/**
 * 双向链表基本操作
 *
 * 1.isEmpty()    链表是否为空
 * 2.length()      链表长度
 * 3.travel()      遍历整个链表
 * 4.add(item)     链表头部添加元素
 * 5.append(item)  链表尾部添加元素
 * 6.insert(pos, item) 指定位置添加元素
 * 7.remove(item)  删除节点
 * 8.search(item)  查找节点是否存在
 */
class DoubleLink
{
    /**
     * 头节点
     * @var
     */
    private $head;

    /**
     * SingleLink constructor.
     */
    public function __construct()
    {
        $this->head = null;
    }

    /**
     * 链表是否为空
     * @return bool
     */
    public function isEmpty()
    {
        return is_null($this->head);
    }

    /**
     * 链表长度
     * @return int
     */
    public function length()
    {
        $cur = $this->head;
        $count = 0;
        while(!is_null($cur)){
            $count++;
            $cur = $cur->next;
        }
        return $count;
    }

    /**
     * 遍历整个链表
     */
    public function travel()
    {
        $cur = $this->head;

        $tmp = [];

        while (!is_null($cur)) {
            array_push($tmp,$cur->item);
            $cur = $cur->next;
        }
        return $tmp;
    }

    /**
     * 链表头部添加元素
     * @param $item
     */
    public function add($item)
    {
        $node = new Node($item);
        if($this->isEmpty()){
            $this->head = $node;
        }else{
            //待插入节点后继节点为原本头节点
            $node->next = $this->head;
            //待插入节点为原本头节点的前驱节点
            $this->head->prev = $node;
            //待插入节点变为头节点
            $this->head = $node;
        }
    }

    /**
     * 链表尾部添加元素
     * @param $item
     */
    public function append($item)
    {
        $node = new Node($item);
        if($this->isEmpty()){
            $this->head = $node;
        }else{
            //移动到尾节点
            $cur = $this->head;
            while (!is_null($cur->next)){
                $cur = $cur->next;
            }
            //原本尾节点next指向待插入节点
            $cur->next = $node;
            //待插入节点prev指向原本尾节点
            $node->prev = $cur;
        }
    }

    /**
     * 指定位置添加元素
     * @param $pos
     * @param $item
     */
    public function insert($pos, $item)
    {
        switch ($pos){
            //若指定位置pos为第一个元素之前，则执行头部插入
            case $pos <= 0:
                $this->add($item);
                break;
            //若指定位置超过链表尾部，则执行尾部插入
            case $pos > ($this->length() - 1):
                $this->append($item);
                break;
            //找到位置
            default:
                $node = new Node($item);
                $count = 0;
                $cur = $this->head;

                //移到指定位置的前一个位置
                while ($count < ($pos - 1)){
                    $count++;
                    $cur = $cur->next;
                }
                $node->prev = $cur;
                $node->next = $cur->next;
                $cur->next->prev = $node;
                $cur->next = $node;
        }
    }

    /**
     * 删除节点
     * @param $item
     */
    public function remove($item)
    {
        if($this->isEmpty()){
            return;
        }

        $cur = $this->head;
        //如果第一个就是删除的节点
        if($cur->item == $item){
            //如果只有这一个节点
            if(is_null($cur->next)){
                $this->head = null;
            }else{
                $cur->next->prev = null;
                $this->head = $cur->next;
            }
            return;
        }
        while (!is_null($cur)){
            //找到元素
            if($cur->item == $item){
                $cur->prev->next = $cur->next;
                $cur->next->prev = $cur->prev;
                break;
            }
            $cur = $cur->next;
        }
    }

    /**
     * 查找节点是否存在
     * @param $item
     * @return bool
     */
    public function search($item)
    {
        $cur = $this->head;
        while (!is_null($cur)){
            if($cur->item == $item){
                return true;
            }
            $cur = $cur->next;
        }
        return false;
    }
}

$s = new DoubleLink();
$s->add('23');
$s->add('er');
$s->add('33');
//$s->append('56');
//$s->insert(2,'2222');
//echo $s->length();
//var_dump($s->travel());
//var_dump($s->search('er'));
//$s->remove('er');
var_dump($s->travel());

2 分析代码块 具体分析到代码注释哦 ～

定义一个节点对象

/**
 * 节点实现
 */
class Node
{
    /**
     * 数据元素
     * @var
     */
    public $item;

    /**
     * 前驱节点
     * @var
     */
    public $prev;

    /**
     * 后继节点
     * @var
     */
    public $next;

    /**
     * Node constructor.
     * @param $item
     */
    public function __construct($item)
    {
        $this->item = $item;
        $this->prev = null;
        $this->next = null;
    }
}

链表头部添加元素 小伙伴们要注意哦 这个必须要执行三步骤

/**
     * 链表头部添加元素
     * @param $item
     */
    public function add($item)
    {
        $node = new Node($item);//申明一个节点
        if($this->isEmpty()){//如果头部节点为空的情况下
            $this->head = $node;//把头部节点定义为当前定义的节点
        }
        //如果已经存在头部节点的话
        else{
            //第一步：将插入的节点的下一个节点为头部节点
            $node->next = $this->head;
            //第二步：将头部的上一个节点为当前节点
            $this->head->prev = $node;
            //第三步：将头部节点替换成当前节点
            $this->head = $node;
        }
    }
      /**
     * 链表是否为空
     * @return bool
     */
    public function isEmpty()
    {
        return is_null($this->head);
    }
    $s = new DoubleLink();
    $s->add('23');
    $s->add('er');
    $s->add('33');

链表尾部添加元素 小伙伴们要注意哦 看我画的重点的步骤

/**
     * 链表尾部添加元素
     * @param $item
     */
    public function append($item)
    {
        $node = new Node($item);//定义一个节点对象
        if($this->isEmpty()){//如果头部节点为空的情况下
            $this->head = $node;//把头部节点定义为当前定义的节点
        }else{
            //移动到尾节点 开始 此次为重点
            $cur = $this->head;//定义一个头部节点
            //这边为了找到最后的尾部节点在哪里 因为小哥哥要在尾部插入节点啊
            while (!is_null($cur->next)){//循环输出下一个节点 不为空的情况下
                $cur = $cur->next;//将当前的节点定义为找到的尾部节点的下一个指针 因为是当前的节点
            }
            //移动到尾节点 结束

            //原本尾节点next指向待插入节点
            $cur->next = $node;//当前的下一个节点为要插入的节点
            //待插入节点prev指向原本尾节点
            $node->prev = $cur;//要插入的上一个节点为尾节点
        }
    }
    $s->append('56');

指定位置添加元素 小伙伴们要注意哦 看我画的重点的步骤 四步骤狠关键

/**
     * 指定位置添加元素
     * @param $pos
     * @param $item
     */
    public function insert($pos, $item)
    {
        switch ($pos){
            //若指定位置pos为第一个元素之前，则执行头部插入
            case $pos <= 0:
                $this->add($item);
                break;
            //若指定位置超过链表尾部，则执行尾部插入
            case $pos > ($this->length() - 1):
                $this->append($item);
                break;
            //找到位置 以上二点都不是的情况下怎么办呢
            default:
                $node = new Node($item);//先定义一个节点对象
                $count = 0;//定一个数量为0
                $cur = $this->head;//当前节点为头部节点

                //移到指定位置的前一个位置
                while ($count < ($pos - 1)){ //这边循环要移动到哪个位置上
                    $count++;
                    $cur = $cur->next;//把要插入到哪个位置上的节点 拿出来
                }
                //这里很重要
                $node->prev = $cur;//第一步：要插入的节点上一个就是拿出来的当前节点
                $node->next = $cur->next;//第二步：要插入的节点的下一个节点 就是拿出来的当前的节点的下一个节点
                $cur->next->prev = $node;//第三步：这边是关键步骤：把拿出来的下一个节点的上一个节点 指向要插入的节点
                $cur->next = $node;//第四步：把拿出来的下一个节点指向当前要插入的节点
        }
    }
$s->insert(2,'2222');

删除节点： 小伙伴们要注意哦 这边删除的话看重点 删除要处理前后节点的指针指向才能完全真正的删除

/**
     * 删除节点
     * @param $item
     */
    public function remove($item)
    {
        if($this->isEmpty()){//判断头部是否为空 如果为空就不用处理了
            return;
        }

        $cur = $this->head;//先定义一个当前元素 为头部节点
        //如果第一个就是删除的节点
        if($cur->item == $item){//如果当前节点的值为要删除的值
            //如果只有这一个节点
            if(is_null($cur->next)){//如果这个节点的下一个节点为空的话
                $this->head = null;//直接把头部节点为null
            }
            //如果头部节点有下一个节点的话
            else{
                $cur->next->prev = null;//第一步：就把头部节点的下一个节点的上一个节点为null
                $this->head = $cur->next;//第二步：就把头部节点指向当前节点的下一个节点
            }
            return;
        }
        //如果要删除的值不等于头部节点的值的话 就要循环查找要删除的节点咯
        while (!is_null($cur)){
            //找到元素
            if($cur->item == $item){//查找到了
                $cur->prev->next = $cur->next;//第一步：当前的上一个节点的下一个节点 替换为当前要删除的节点的下一个节点
                $cur->next->prev = $cur->prev;//第二步：当前的下一个节点的上一个节点 替换为当前要删除的节点的上一个节点
                break;
            }
            $cur = $cur->next;//定义当前的节点为下一个节点  作用循环使用
        }
    }
$s->remove('33');

查找节点

/**
     * 查找节点是否存在
     * @param $item
     * @return bool
     */
    public function search($item)
    {
        $cur = $this->head;//定义头部节点
        while (!is_null($cur)){//循环节点
            if($cur->item == $item){//如果找到就找到了 很简单吧

                return true;
            }
            $cur = $cur->next;
        }
        return false;
    }
    var_dump($s->search('er'));

循环节点

/**
     * 遍历整个链表
     */
    public function travel()
    {
        $cur = $this->head;
        var_dump($cur);die();

        $tmp = [];//定义一个数组

        while (!is_null($cur)) {//依次循环
            array_push($tmp,$cur->item);//把值放到数组里面
            $cur = $cur->next;
        }
        return $tmp;
    }
php 数据结构
本作品采用《CC 协议》，转载必须注明作者和本文链接
附言 1  ·  5年前

数据结构是每个程序员必备的～

Krisji
课程读者 282 声望
ooo @ 无组织
一个喜欢捣腾的开发者
《L05 电商实战》
《L05 电商实战》
从零开发一个电商项目，功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L01 基础入门》
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上，本课程教授 Web 开发中专业、实用的技能，如 Git 工作流、Laravel Mix 前端工作流等。
讨论数量: 2
排序：
时间 投票
张小伟
课程读者 24 声望 / @

坐等秦时明月系列 :joy:

5年前 评论
Krisji
课程读者 282 声望 / ooo @ 无组织

哈哈，等后面有时间出go系列

5年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！
支持 MD 帮助
Krisji
ooo @ 无组织
文章
65
粉丝
156
喜欢
105
收藏
119
排名：73
访问：11.3 万
私信
所有博文
文章归档
4 篇 2024 年 12 月 1 篇 2020 年 7 月 1 篇 2020 年 3 月 1 篇 2020 年 2 月 2 篇 2020 年 1 月 4 篇 2019 年 12 月 2 篇 2019 年 11 月 2 篇 2019 年 9 月 2 篇 2019 年 8 月 8 篇 2019 年 5 月 24 篇 2019 年 4 月 14 篇 2019 年 3 月
最新文章 最受欢迎
2个月前 最后一天离职日（2024 12 31） 2个月前 今天最后一天离职日（2024.12.31） 2个月前 10年生涯 2个月前 我写代码10年生涯 4年前 画江湖之23种设计模式
18 画江湖之面试篇 [第三篇] tip:生活没你想的那么容易～你不努力没人能帮你 8 MySQL 定时备份 8 画江湖之面试篇 [第一篇] tip:基础是每个程序员必须的 6 画江湖之数据结构 [第三话:二叉树] 二茶🌲 5 画江湖之数据结构 [第一话:链表] 单向链表
博客标签
php
34
 laravel
4
 docker
4
 swoole
2
 JS
1
 git
1
 vue
3
 算法
4
 数据结构
5
 面试
4
 进程
7
 线程
3
 liunx
2
 go
1
社区赞助商
成为赞助商

关于 LearnKu

LearnKu 是终身编程者的修道场
做最专业、严肃的技术论坛
LearnKu 诞生的故事

资源推荐

  • 《社区使用指南》
  • 《文档撰写指南》
  • 《LearnKu 社区规范》
  • 《提问的智慧》

    • 服务提供商

    其他信息

  • 成为版主
  • 所有测验
  • 联系站长（反馈建议）

    • 粤ICP备18099781号-6 | 粤公网安备 44030502004330号 | 违法和不良信息举报

    由 Summer 设计和编码 ❤

    请登录

    内容举报
    匿名举报，为防止滥用，仅管理员可见举报者。

    我要举报该，理由是：

    取消