画江湖之数据结构【第一话:链表】单向链表

链表

1 单链表

概括:单链表有一个引用指向后续节点
file
请看上图:data为数据,next为指向下一个节点的引用

完整代码块

<?php 

class Node{
    public $data = null;
    public $next = null;
    public function __construct($data,$next=null){
        $this->data = $data;
        $this->next = $next;
    }
}

class singleLinkList{
    private $header = null;
    private $last = null;
    public $size = 0;

    public function __construct(){

    }

    public function add($data){
        $node = new Node($data);
        if($this->header == null and $this->last==null){
            $this->header = $node;
            $this->last = $node;
        }else{
            $this->last->next = $node;
            $this->last = $node;
        }
    }

    public function del($data){
        $node=$this->header;
        if($node->data == $data){
            $this->header = $this->header->next;
            return true;
        }else{
             while($node->next->data != $data){
                $node = $node->next;
             }
            $node->next = $node->next->next;
            return true;
        }
        return false;
    }

    public function update($old,$new){
        $node = $this->header;
        while($node->next != null){
            if($node->data == $old){
                $node->data = $new;
                return true;
            }
            $node = $node->next;
        }
        echo "not found!";
        return false;
    }

    public function find($data){
        $node = $this->header;
        if  ($node->data  ==  $data)  {
            echo  'found!';
            return  true;
        }
        while($node->next != null){
            if($node->data == $data){
                echo "found!";
                return;
            }
            $node = $node->next;
        }
        echo "not found!";
    }

    public function getAll(){
        $node = $this->header;
        while($node->next != null){
            echo $node->data;
            $node = $node->next;
        }
        echo $node->data;
    }
}

$list =  new singleLinkList();
$list->add("1");
$list->add("2");
$list->add("3");
$list->add("4");
$list->add("5");
$list->add("6");
echo "<pre>";
// $list->getAll();

// if($list->del("2")){
//  echo "success";
// }else{
//  echo "false";
// }

// if($list->update("3","7")){
//  var_dump($list);
// }

$list->find(7);
// $list->getAll();

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

添加节点

public function add($data){
        //申明一个节点对象
        $node = new Node($data);
        //如果头部和尾部为null
        if($this->header == null and $this->last==null){
            $this->header = $node;//插入第一个数据到头部
            $this->last = $node;//插入第一个数据到尾部
        }
        //如果头部和尾部不为null 也就是第二次插入节点的时候
        else{
            $this->last->next = $node;//把尾部的下一个节点为当前插入的节点
            $this->last = $node;//把尾部的节点替换成当前插入的节点
        }
    }
$list =  new singleLinkList();
$list->add("1");
$list->add("2");
$list->add("3");
$list->add("4");
$list->add("5");
$list->add("6");

循环节点

public function getAll(){
        //头部节点定义
        $node = $this->header;
        //循环 如果该节点有下个子节点就开始输出
        while($node->next != null){
            echo $node->data;//输出当前节点的数据
            $node = $node->next;//把下个子节点换作到当前节点
        }
        echo $node->data;//最后输出尾部节点数据
    }

删除节点

public function del($data){
        $node=$this->header;//定义所有的节点
        if($node->data == $data){ //如果要删除的节点是头部节点
            $this->header = $this->header->next;//就把头部的节点移动到头部节点的下一个子节点
            return true;
        }else{
            while($node->next->data == $data){//循环节点:删除的节点和当前节点的下一个节点相同时
                $node->next = $node->next->next;//就把要当前的这个节点的下一个节点 指向下一个下一个的节点
                return true;
            }
        }
        return false;
    }
  $list->del("2")

修改节点

 public function update($old,$new){
        $node = $this->header;//先定义头部节点
        while($node->next != null){//如果有下一个节点
            if($node->data == $old){//当前遍历的节点的数据等于你要删除的数据的时候
                $node->data = $new;//替换成新的数据
                return true;
            }
            $node = $node->next;//当前的节点为下一个节点 作用:循环下一个链表
        }
        echo "not found!";//没找到就没了
        return false;
    }
    $list->update("3","7")
 }

查找节点

public function find($data){
$node = $this->header;//先申明一个头部节点
while($node->next != null){//遍历下一个节点
if($node->data == $data){//如果你要查找的数据等于当前的节点的数据的时候 算找到了
echo "found!";
return;
}
$node = $node->next;
}
echo "not found!";
}
$list->find(7);
php
Krisji
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 2

支持 :+1:以前以为数组就是php这样子的,后来发现这玩意儿叫哈希表……

5个月前 评论
j475523225

画江湖我只知道不良人和灵主 :see_no_evil:
链表是啥 :joy:

5个月前 评论

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!