PHPデータ構造の基礎 ダブルリンクリスト

この記事では、PHP のデータ構造の基礎となる、参照価値のある二重リンクリストを中心に紹介します。必要な友人は参考にしてください。

double とは-リンクされたリスト?

実践的なPHPデータ構造の基礎 - 単結合リストの前回の記事

単結合リストは、1つずつノードとなるオブジェクトで構成されており、各ノードは次のノードへのポインタを持っています。最後のノードのポインタ フィールドは null を指します。各ノードは任意のデータ型を保存できます。

ダブル リンク リストの各ノードには 2 つのポインター フィールドがあり、それぞれ先行ノードと後続ノードを指します。単一リンクリストは一方向ですが、二重リンクリストは双方向です。

一般的な操作

二重リンク リストに対する一般的な操作は次のとおりです:

• insert

• #insertAfter

• insertAtFirst

• insertAtLast

• deleteFirst

• deleteLast

• delete

#reverse
getNthNode
...
PHP 言語の実装

まず、二重リンクの ListNode を実装します。定義の種類に応じたリスト。

class ListNode
{
    public $data = null;
    public $next = null;
    public $prev = null;

    public function __construct(string $data)
    {
        $this->data = $data;
    }
}

リンク リスト クラスを見ると、最初に 3 つのプライベート属性、つまり先頭ノード、末尾ノード、および長さが必要です。

class DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;
}

次のステップは、古いルールに固執し、最初の一般的に使用される挿入の実装方法を直接検討することです。これは、平均時間計算量が O(n) の操作です。

/**
 * 插入一个节点
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);
    if ($this->head) {
        $currentNode = $this->head;
        while ($currentNode) {
            if ($currentNode->next === null) {
                $currentNode->next = $newNode;
                $newNode->prev = $currentNode;
                $this->last = $newNode;
                $this->length++;
                return true;
            }

            $currentNode = $currentNode->next;
        }
    } else {
        $this->head = &$newNode;
        $this->last = $newNode;
        $this->length++;
        return true;
    }

}

ノードを削除する方法を見てみましょう。

/**
 * 删除一个节点
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function delete(string $query = null)
{
if ($this->head) {
    $currentNode = $this->head;
    $prevNode = null;

    while ($currentNode) {
        if ($currentNode->data === $query) {
            if ($nextNode = $currentNode->next) {
                if ($prevNode) {
                    $prevNode->next = $nextNode;
                    $nextNode->prev = $prevNode;
                } else {
                    $this->head = $nextNode;
                    $nextNode->prev = null;
                }

                unset($currentNode);
            } else {
                if ($prevNode) {
                    $this->last = $prevNode;
                    $prevNode->next = null;
                    unset($currentNode);
                } else {
                    $this->head = null;
                    $this->last = null;
                }
            }

            $this->length--;
            return true;
        }

        $prevNode = $currentNode;
        $currentNode = $currentNode->next;
    }
}

    return false;
}

二重リンクリストを逆にすることもそれほど複雑ではありません。

public function reverse()
{
    if ($this->head !== null) {

        if ($this->head->next !== null) {
            $reversedList = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reversedList;
                $currentNode->prev = $next;

                $reversedList = $currentNode;
                $currentNode = $next;

            }

            $this->last = $this->head;
            $this->head = $reversedList;
        }
    }
}

二重リンクリストに対するその他の操作の詳細な実装については、ここを参照してください。

ダブル リンク リストは、シングル リンク リストと比較して、リンク リスト アクセス データ構造の特別な部分です。シングル リンク リスト、循環リンク リスト、マルチ リンク リストもリンク リスト構造に属します。

特別シリーズ

PHP基本データ構造特別シリーズディレクトリアドレス: https://github.com/... 主にPHPの構文を使用して基本的なデータ構造とアルゴリズムをまとめています。また、日常の PHP 開発で見落とされがちな基本的な知識や、最新の PHP 開発における標準化、展開、最適化に関する実践的な提案も含まれており、JavaScript 言語の特性についても詳しく説明されています。

上記がこの記事の全内容です。皆様の学習に少しでもお役に立てれば幸いです。その他の関連コンテンツについては、PHP 中国語 Web サイトをご覧ください。

関連する推奨事項:

PHP データ構造の基本スタック

php7 の php-fpm パラメータ設定に関する注意事項

以上がPHPデータ構造の基礎 ダブルリンクリストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。