php实现数据结构的单向链表

链表是以链式存储数据的结构，其不需要连续的存储空间，链表中的数据以节点来表示，每个节点由元素(存储数据)和指针(指向后继节点)组成。

啥是单向链表

链表是以链式存储数据的结构，其不需要连续的存储空间，链表中的数据以节点来表示，每个节点由元素(存储数据)和指针(指向后继节点)组成。

单向链表（也叫单链表）是链表中最简单的一种形式，每个节点只包含一个元素和一个指针。
它有一个表头，并且除了最后一个节点外，所有节点都有其后继节点。
它的存储结构如下图所示

代码实现

定义节点

class Node
{
    public $data;

    /**
     * @var null | Node
     */
    public $next;

    public function __construct($data)
    {
        $this-&gt;data = $data;
        $this-&gt;next = null;
    }

}

单链表实现

/**
 * Class SingleLinkList
 * 单链接的实现示例，实现简单的填加，插入，删除, 查询，长度，遍历这几个简单操作
 */
class SingleLinkList
{
    /**
     * 链表头结点，头节点必须存在，
     * @var Node
     */
    public $header;

    private $size = 0;

    /**
     * 构造函数，默认填加一个哨兵节点，该节点元素为空
     * SingleLinkList constructor.
     */
    public function __construct()
    {
        $this-&gt;header = new Node(null);
    }

    /**
     * 在链表末尾添加节点
     * @param Node $node
     * @return int
     */
    public function addNode(Node $node)
    {
        $current = $this-&gt;header;
        while ($current-&gt;next != null) {
            $current = $current-&gt;next;
        }
        $current-&gt;next = $node;

        return ++$this-&gt;size;
    }

    /**
     * 在指定位置插入节点
     * @param int $index 节点位置，从1开始计数
     * @param Node $node
     * @return int
     * @throws Exception
     */
    public function insertNodeByIndex($index, Node $node)
    {
        if ($index &lt; 1 || $index &gt; ($this-&gt;size + 1)) {
            throw new Exception(sprintf('你要插入的位置，超过了链表的长度 %d', $this-&gt;size));
        }

        $current = $this-&gt;header;
        $tempIndex = 1;
        do {
            if ($index == $tempIndex++) {
                $node-&gt;next = $current-&gt;next;
                $current-&gt;next = $node;
                break;
            }
        } while ($current-&gt;next != null &amp;&amp; ($current = $current-&gt;next));

        return ++$this-&gt;size;
    }

    /**
     * 删除节点
     * @param int $index 节点位置，从1开始计数
     * @return int
     * @throws Exception
     */
    public function deleteNodeByIndex($index)
    {
        if ($index &lt; 1 || $index &gt; ($this-&gt;size + 1)) {
            throw new Exception('你删除的节点不存在');
        }

        $current = $this-&gt;header;
        $tempIndex = 1;
        do {
            if ($index == $tempIndex++) {
                $current-&gt;next = $current-&gt;next-&gt;next;
                break;
            }
        } while ($current-&gt;next != null &amp;&amp; ($current = $current-&gt;next));

        return --$this-&gt;size;
    }

    /**
     * 查询节点
     * @param int $index 节点位置，从1开始计数
     * @return Node|null
     * @throws Exception
     */
    public function searchNodeByIndex($index) {
        if ($index &lt; 1 || $index &gt; ($this-&gt;size + 1)) {
            throw new Exception('你查询的节点不存在');
        }

        $current = $this-&gt;header;
        $tempIndex = 1;
        do {
            if ($index == $tempIndex++) {
                return $current-&gt;next;
            }
        } while ($current-&gt;next != null &amp;&amp; ($current = $current-&gt;next));
    }

    /**
     * 获取节点长度
     * @return int
     */
    public function getLength()
    {
        return $this-&gt;size;
    }

    /**
     * 遍历列表
     */
    public function showNode()
    {
        $current = $this-&gt;header;
        $index = 1;
        while ($current-&gt;next != null) {
            $current = $current-&gt;next;
            echo 'index --- ' . $index++ . ' --- ';
            echo var_export($current-&gt;data);
            echo PHP_EOL;
        }
    }
}

示例

$link = new SingleLinkList();
$link-&gt;addNode(new Node(1));
$link-&gt;addNode(new Node(2));
$link-&gt;insertNodeByIndex(3, new Node(3));
$link-&gt;addNode(new Node(4));
$link-&gt;addNode(new Node(5));
echo $link-&gt;getLength(), PHP_EOL;
$link-&gt;showNode();
echo '-----------', PHP_EOL;
var_dump($link-&gt;searchNodeByIndex(3));
echo '-----------', PHP_EOL;
$link-&gt;deleteNodeByIndex(3);
$link-&gt;showNode();

发表于 2020-09-02 09:55
阅读 ( 579 )
分类：中间件

php实现数据结构的单向链表

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »