php实现单链表

标签：node head 单链 no 实现 next insertNode php 节点

今天记录下使用php实现单向链表的功能操作

先创建一个节点类用来生成节点对象

<?php
class node{
    public $name = null;
    public $no = null;
    public $next = null;
    public function __construct($name = '',$no = null,$next=null){
        $this->name = $name;
        $this->no = $no;
        $this->next = $next;
    }
}

此类对象有三个属性名称，编号，下一个节点的地址

创建链表操作类，实现了简单的添加，查找，展示，删除操作

<?php
class single{
    //查询
    public function findLinkOne($head,$no){
        $currentNode = $head;
        $findNode = null;

        while($currentNode->next != null){
            if($currentNode->no == $no){
                $findNode = $currentNode;
                break;
            }

            $currentNode = $currentNode->next;
        }

        if($findNode){
            return $findNode;
        }

        return -1;
    }
    
    //展示
    public function showAll($head){
        $cursor = $head;

        if(!$cursor->next){
            echo "Nothing to find! <br/>";
            return;
        }

        while($cursor->next != null){
            echo "No:{$cursor->next->no},Name:{$cursor->next->name} <br/>";
            $cursor = $cursor->next;
        }

        echo "Show all of this list <br/>";
        return;
    }

    //添加
    public function addLinkOne($head,$node){
        $insertNode = $head;
        $afterNode = null;

        while($insertNode->next != null){
            
            if($insertNode->next->no > $node->no){
                $afterNode = $insertNode->next;
                break;
            }else if($insertNode->next->no == $node->no){
                echo "This node in list !<br/>";
                return;
            }

            $insertNode = $insertNode->next;
        }

        if($afterNode){
            $node->next = $afterNode;
        }
        
        $insertNode->next = $node;
    }

    //删除
    public function delLinkOne($head,$no){
        $cursor = $head;
        $preNode = $head;

        while($cursor->next != null){
            $preNode = $cursor;
            $cursor = $cursor->next;
            if($cursor->no == $no){
                $preNode->next = $cursor->next;
            }
        }

        return true;
    }
}

下面开始调用测试

$singleObj = new single();
$head = new node();

实例化链表类和节点类生成一个头节点

$singleObj->addLinkOne($head,new node('赵不亮',1));
$singleObj->addLinkOne($head,new node('钱不够',2));
$singleObj->addLinkOne($head,new node('孙悟空',3));
$singleObj->addLinkOne($head,new node('王梓',8));
$singleObj->addLinkOne($head,new node('郑品',7));
$singleObj->addLinkOne($head,new node('周围',5));
$singleObj->addLinkOne($head,new node('吴发',6));
$singleObj->addLinkOne($head,new node('李四',4));

$singleObj->showAll($head);

调用链表添加方法加入8个顺序混乱的节点对象，最后调用展示方法查看生成的链表

 

 可以看到节点对象都存入链表并按no编号从小到大顺序保存好了

$singleObj->delLinkOne($head,3);
$singleObj->delLinkOne($head,5);
$singleObj->showAll($head);

调用删除方法按no编号删除指定节点

 

 可以看到编号3和编号5的节点已经从链表中移除了

 

在这个链表类中核心代码就是链表的添加和删除两个方法现在来具体分析下其思路

 

 在这个方法中，进入方法先定义了一个游标节点，并将其赋值为头节点（这就是为什么要创建一个空的头节点，没有这个我们不知道从哪里开始找）

在添加第一个节点时，$insertNode节点是头节点它的下一个节点的地址是空的，因此不会进入循环，$afterNode节点也是空的所以会直接走最后一行将传入的节点直接挂在头节点的后面，即将$node对象的地址存入$insertNode->next属性

在添加第二个节点时，仍然从头节点开始找起，但此时头结点next属性挂载了no 为1的节点因此会进入到循环体中执行，

　　判断$insertNode->next->no > $node->no的结果，注意此时是添加节点2的首次循环，因此$insertNode当前是头节点，$insertNode->next->no即代表的是他挂载的下一个节点的no属性也就是节点1的no属性，他的值是1因此判断条件不成立

　　而此时$insertNode->next->no == $node->no条件也不成立，所以本次循环只执行了循环体的最后一步将当前节点的下一个节点地址赋值给游标，即游标向前移动一步。

　　所有的按从小到大顺序加入的节点都会是这个流程，无论其no属性是否连贯。

但是直到添加节点7时情况发生了变化。此时游标移动到节点3时，判断$insertNode->next->no > $node->no的结果此时结果成立会进入if分支执行

　　此时我们找到了节点7的插入点，他应是在3之后8之前

　　这里我们会先将3节点的下一个节点，即no=8的节点地址记录到$afterNode，此时$insertNode代表的是节点3因此获取节点8的地址要使用next属性获取

　　找到插入点，记录好需要向后移动的节点8地址后，我们就可以跳出循环体了（循环体的作用就是找到插入点并记录向后移动的节点地址）

　　最后我们只需要把$afterNode（节点8）挂载到$node->next属性，将$node(节点7)挂载到$insertNode(节点3)的next属性即可完成节点插入

删除操作和添加相反，这里我们要记录的是游标的上一个节点，当游标的no属性与传入的参数$no相等时我们找到了要删除的节点，此时我们要把游标节点的地址赋值给游标上级节点的next属性，即在遍历链表时找不到此时的游标节点即认为其被删除。

查找和展示没什么逻辑上的难点，只需要注意遍历完一个节点后向后移动游标即可。

标签：node,head,单链,no,实现,next,insertNode,php,节点
From： https://www.cnblogs.com/python-gulp-php/p/16880963.html