<?php
/**
 * @desc PHP7.4 实现单链表
 */
//链表节点
class ListNode
{
    public ?int $id;//节点id
    public ?string $val;//节点值
    public ?ListNode $next;//下一个节点

    public function __construct($id, $val)
    {
        $this->id = $id;
        $this->val = $val;
        $this->next = null;
    }

}

//有序链表
class SingleList
{
    private ListNode $header;//链表头节点

    //初始化头节点
    public function __construct($id = null, $val = null)
    {
        $this->header = new ListNode($id, $val);
    }

    //链表长度
    public function length()
    {
        $count = 0;
        $current = $this->header;
        while ($current->next != null) {
            $count++;
            $current = $current->next;
        }
        echo "链表长度: {$count}";
        echo PHP_EOL;
    }

    //插入节点
    public function add(ListNode $node)
    {
        //初始当前节点为头节点
        $current = $this->header;
        //循环当前节点的下一个节点信息，以查找真正的当前节点信息
        while ($current->next != null) {
            //若当前节点的下一个节点id值大于要插入节点的id值，循环结束
            if ($current->next->id > $node->id) {
                break;
            }
            //将当前节点置为 当前的next节点信息
            $current = $current->next;
        }
        $node->next = $current->next;
        //当前节点的next节点信息置为插入的节点信息
        $current->next = $node;
    }

    //删除节点
    public function delete(int $id)
    {
        $current = $this->header;
        $findFlag = false;
        while ($current->next != null) {
            if ($current->next->id == $id) {
                $findFlag = true;
                break;
            }
            $current = $current->next;
        }
        if ($findFlag) {
            //重置链接
            $current->next = $current->next->next;
        } else {
            echo "未找到要删除的节点[id:{$id}]";
            echo PHP_EOL;
        }
    }

    //遍历链表
    public function foreachList()
    {
        $current = $this->header;
        $list = [];
        while ($current->next != null) {
            $list[] = '[' . $current->next->id . ',' . $current->next->val . ']';
            $current = $current->next;
        }
        $list = $list ? implode('->', $list) : "空链表";
        echo "遍历链表: {$list}";
        echo PHP_EOL;
    }

    //查询
    public function search($id)
    {
        $current = $this->header;
        $info = '';
        $i = 0;
        while ($current->next != null) {
            $i++;
            if ($current->next->id == $id) {
                $info = '[' . $current->next->id . ',' . $current->next->val . '], 查找次数:' . $i;
                break;
            }
            $current = $current->next;
        }
        if ($info) {
            echo "查找id:{$id}节点信息: {$info}";
        } else {
            echo "未找到id:{$id}节点信息";
        }
        echo PHP_EOL;
    }
}

//初始化链表
$list = new SingleList();
//添加节点
for ($i = 1; $i <= 10; $i++) {
    $list->add(new ListNode($i, $i . $i . $i));
}

//获取链表长度
$list->length();
//获取链表
$list->foreachList();
//查找
$list->search(4);
$list->search(6);
$list->search(9);