PHPデータ構造の基礎ダブルリンクリスト-PHPチュートリアル-php.cn

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

不言

リリース： 2023-04-02 18:30:02

オリジナル

1630 人が閲覧しました

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

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

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

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

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

一般的な操作

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

insert
#insertAfter
insertAtFirst
insertAtLast
deleteFirst
deleteLast
delete

まず、二重リンクの 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;
        }
    }
}

ログイン後にコピー

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

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

特別シリーズ