実戦PHPデータ構造基礎のダブルチェーンテーブル

デュアルチェーン時計とは?
前編実戦PHPデータ構造基礎の単鎖表では
単一チェーンテーブルは、ノードとしてのオブジェクトで構成され、各ノードには次のノードへのポインタがあり、最後のノードのポインタドメインは空を指します.各ノードは、任意のデータ型を格納できます.
一方、デュアルチェーンテーブルの各ノードには、前駆ノードと後続ノードをそれぞれ指す2つのポインタドメインがあります.単一チェーンテーブルは一方向であり、二重チェーンテーブルは双方向である.
一般的な操作
デュアルチェーンテーブルの一般的な操作は次のとおりです.

insert

insertBefore

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言語の特徴に対する深い研究もある.