PHPのリンクリストの実装方法

PHP リンク リストの実装方法: 最初に PHP サンプル ファイルを作成し、次にヘッド ノードを初期化し、次にノードのデータを特定の位置に設定し、特定の位置にノードを挿入し、最後にノードを削除します。特定の位置にあるノード。

推奨事項: 「PHP ビデオ チュートリアル 」

リンク リスト

リンク リスト (リンク リスト)一般的な基本データ構造は線形テーブルですが、データを線形順序で格納するのではなく、各ノードに次のノードへのポインタを格納します。

リンク リスト構造を使用すると、データ サイズを事前に知る必要があるという配列リンク リストの欠点を克服でき、コンピュータのメモリ空間を最大限に活用し、柔軟な動的メモリ管理を実現できます。 。しかし、リンクリストは配列のランダム読み取りの利点を失い、同時にノードのポインタフィールドの増加によりリンクリストのスペースオーバーヘッドが比較的大きくなります。

リンク リストには、一方向リンク リスト、二重リンク リスト、循環リンク リストなど、さまざまな種類があります。

単一リンク リスト

最も単純なタイプのリンク リストは、情報フィールドとポインタ フィールドの 2 つのフィールドを含む一方向リンク リストです。このリンクはリスト内の次のノードを指し、最後のノードは null 値を指します。

#PHP は単純な一方向リンク リストを実装します

<?php

class Node
{
    private $Data;//节点数据
    private $Next;//存储下个点对象

    public function __construct($data, $next)
    {        $this->Data = $data;        $this->Next = $next;
    }

    public function __set($name, $value)
    {        if (isset($this->$name))            $this->$name = $value;
    }

    public function __get($name)
    {        if (isset($this->$name))            return $this->$name;        else
            return NULL;
    }
}

class LinkList
{
    private $head;//头节点
    private $len;

    /**
     * 初始化头节点
     */
    public function __construct()
    {        $this->init();
    }

    public function setHead(Node $val)
    {        $this->head = $val;
    }

    public function getHead()
    {        return $this->head;
    }

    public function getLen()
    {        return $this->len;
    }

    public function init()
    {        $this->setHead(new Node(NULL, NULL));        $this->len = 0;
    }

    /**
     * 设置某位置节点的数据
     * @param int $index
     * @param $data
     * @return bool
     */
    public function set(int $index, $data)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        $node->Data = $data;        return TRUE;
    }

    /**
     * 获取某位置节点的数据
     * @param int $index
     * @return mixed
     */
    public function get(int $index)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        return $node->Data;
    }

    /**
     * 在某位置处插入节点
     * @param $data
     * @param int $index
     * @return bool
     */
    public function insert($data, int $index = 0)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = new Node($data, $node->Next);        $this->len++;        return TRUE;
    }

    /**
     * 删除某位置的节点
     * @param int $index
     * @return bool
     */
    public function delete(int $index)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = $node->Next->Next;        $this->len--;        return TRUE;
    }
}

二重リンク リスト一より複雑なリンク リストは、「二重リンク リスト」または「両面リンク リスト」です。各ノードには 2 つの接続があります: 1 つは前のノードを指します (この「接続」が最初の「接続」の場合、null 値または空のリストを指します)。もう 1 つは次のノードを指します (この「接続」が最初の「接続」の場合)。 " は最初の "接続" であり、null 値または空のリストを指します); "それが最後の "接続" である場合、null 値または空のリストを指します)

循環リンク リスト循環リンク リストでは、最初のノードと最後のノードが互いに接続されます。このメソッドは、一方向リンク リストと双方向リンク リストの両方で実装できます。循環リンク リストを変換するには、任意のノードから開始して、開始ノードに戻るまでいずれかの方向にリストに従います。別の方法で見ると、循環リンク リストは「頭なし、尾なし」とみなすことができます。このようなリストは、リスト内に 1 つのオブジェクトがあり、他のすべてのオブジェクトを不特定の配置で反復処理する必要がある場合に、データ ストレージ キャッシュを節約するのに役立ちます。 リスト全体へのポインタをアクセスポインタと呼ぶこともある。

基本的なアイデアはほぼ完成しているので、更新を続ける時間があります

以上がPHPのリンクリストの実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。