php实现单链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。
某种程度上避免数组构建时需要连续分配连续内存的缺陷
单链表

单链表
插入：链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点(前驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点（见下图）。
插入单链表
由上图可知，B、C之间插入D，三者之间的关系为

current为插入节点的前驱节点
current->next = new              // B节点指向新节点D
new->next = current->next        // 新节点D指向B的后继节点C

删除：从链表中删除一个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）。

删除单链表
由上图可知，A、C之间删除B，三者之间的关系为

current为要删除节点的前驱节点
current->next = current->next->next    // A节点指向C节点

具体实现代码如下：

//节点类
class Node{

    private $data;
    private $next;
    
    public function __construct($data){
        $this->data = $data;
    }
    
    public function __set($property_name,$value){
        //注意在魔术方法__set和__get中$this是指向变量而非固定属性
        //因此这里为$this->$property_name
        $this->$property_name = $value;
    }
    
    public function __get($property_name){
        return $this->$property_name;
    }

}

//单链表类
class SingleLinkedList{

    private $header;

    public function __construct($data){
        $this->header = new Node($data);
    }
    
    //查找当前节点
    public function findNode($data){
        $currentNode = $this->header;
        //$currentNode->next != null判断返回只含有头节点或者链表的最后一个节点
        //$currentNode->data != $data判断返回查找结果节点
        while($currentNode->next != null && $currentNode->data != $data){
            //当前节点指针移动到下个节点
            $currentNode = $currentNode->next;
        }
        return $currentNode;
    }
    
    //根据当前节点插入节点
    public function insertNode($nodeData,$data){
        //查找当前节点
        $currentNode = $this->findNode($nodeData);
        $newNode = new Node($data);
        //将新节点加入链表
        $newNode->next = $currentNode->next;
        $currentNode->next= $newNode;

        return true;
    }

    //更新节点
    public function updateNode($old,$new){
        $currentNode = $this->findNode($old);
        $currentNode->data = $new;
        return true;
    }

    //查找节点数据的前一个节点
    public function preNode($data){
        $currentNode = $this->header;
        //查找节点的下一个节点的值等于查找数据时，返回当前节点即为查找节点的上一个节点
        while($currentNode->next != null && $currentNode->next->data != $data) {
            $currentNode = $currentNode->next;
        }
        return $currentNode;
    }

    //删除节点
    public function deleteNode($node){
        $preNode = $this->preNode($node);
        $currentNode = $this->findNode($node);
        $preNode->next = $currentNode->next;
        return true;
    }

    //清空链表
    public function clearNode(){
        $this->header = null;
    }

    //展示链表，这里不展示头节点
    public function display(){
        $currentNode = $this->header;
        if($currentNode->next == null){
            echo "链表为空";
        }
        while($currentNode->next != null){
            echo $currentNode->next->data."\t";
            $currentNode = $currentNode->next;
        }
    }

}

$linkedList = new SingleLinkedList("header");
$linkedList->insertNode("header","mayun");
$linkedList->insertNode("mayun","mahuateng");
$linkedList->insertNode("mahuateng","liyanhong");
$linkedList->insertNode("liyanhong","liuqiangdong");
echo "展示链表，这里不展示头节点";
echo "\n";
$linkedList->display();
echo "\n";
echo "删除节点后展示";
echo "\n";
$linkedList->deleteNode("liyanhong");
$linkedList->display();
echo "\n";
echo "更新节点";
echo "\n";
$linkedList->updateNode("liuqiangdong","zhangyiming");
$linkedList->display();
echo "\n";

执行结果如下：

执行结果