PHPでSingly linked list

まじめにデータ構造などの学習をしてなかったんですが、最近ちょっとずつやり始めたので、業務で使用しているPHPでアウトプットしてみます。

Singly Linked list

データを持つノードが連なったデータ構造で、各ノードは次or前のノードへのリンクを持っています。
いくつか種類がありますが、今回扱う Singly linked listは、データと次のノードへのリンクのみを持つノードが連なったものです。

PHPで実装してみる

クラス定義

まずノードのクラスを実装。
データ用フィールドと次のノードへのリンク用のフィールドを持っています。

<?php
class NodeSingly
{
    public $data;
    public $next;

    public function __construct($data, NodeSingly $nextNode = null)
    {
        #データ
        $this->data = $data;
        #次のノード
        $this->next = $nextNode;
    }
}

次にlinked listのクラスを実装。
先頭ノード用のフィールドを持っています。

class SinglyLinkedList
{
    public $head;

    public function __construct(NodeSingly $head = null)
    {
        $this->head = $head;
    }

}

メソッドの実装

linked listをいろいろ操作するためのメソッドを、SinglyLinkedListクラスにいくつか実装してみます。

内容は以下の通りです。

• 新しいノードをリストの最後に追加
• 新しいノードをリストの先頭に追加
• 新しいノードを任意のデータを持つノードの後に追加
• 任意のデータを持つノードを削除
• リストを逆順に並び替え

なお、コーナーケース的なものは今回考慮してないです

新しいノードをリストの最後に追加

リストにノードがない場合は先頭に追加。それ以外の場合はループ処理で終端ノードを見つけ、終端ノードのnextを新しいノードに設定。

    public function insertAtEnd($data)
    {
        $newNode = new NodeSingly($data);
        #リストが空の場合は先頭に追加
        if (is_null($this->head)) {
            $this->head = $newNode;
            return;
        }

        $lastNode = $this->head;
        while ($lastNode->next) {
            $lastNode = $lastNode->next;
        }
        $lastNode->next = $newNode;
    }

新しいノードをリストの先頭に追加

既存の先頭ノードを新しいノードのnextに設定し、新しいノードをheadに設定。

    public function insertAtStart($data)
    {
        $newNode = new NodeSingly($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

新しいノードを任意のデータを持つノードの後に追加

ループさせて対象のデータを持つノードを探して、そのノードのnextに新しいノードを設定。
対象のデータを持つノードがなければなにもしない。

    public function insertAfterNode($targetData, $data)
    {
        $currentNode = $this->head;

        while ($currentNode->next) {
            if ($currentNode->data === $targetData) {
                break;
            }
            $currentNode = $currentNode->next;
        }

        if (is_null($currentNode)) {
            return;
        }

        $newNode = new NodeSingly($data);
        $newNode->next = $currentNode->next;
        $currentNode->next = $newNode;
    }

任意のデータを持つノードを削除

先頭ノードのデータが対象のデータだった場合、先頭ノードのnextを先頭ノードに設定。
それ以外の場合はループさせて対象のノードを見つける。見つけたらそのノードを飛ばすようにnextを設定。

    public function remove($data)
    {
        #先頭ノードの場合
        $currentNode = $this->head;

        if ($currentNode && $currentNode->data === $data) {
            $this->head = $currentNode->next;
            $currentNode = null;
            return;
        }

        $prevNode = null;
        while ($currentNode && $currentNode->data !== $data) {
            $prevNode = $currentNode;
            $currentNode = $currentNode->next;
        }

        if (is_null($currentNode)) {
            return;
        }
        #対象ノードを飛ばしてリンクを設定
        $prevNode->next = $currentNode->next;
        $currentNode = null;
    }

リストを逆順に並び替え

先頭ノードから順番に、リンクを逆方向に設定してゆきます。
最終的に終端ノードが返ってきたら、それを先頭に設定します。

    public function reverse()
    {
        $sort = function (NodeSingly $targetNode = null, NodeSingly $prevNode = null) use(&$sort) {
            if (is_null($targetNode)) {
                #nextがnullのノード(終端)を返す
                return $prevNode;
            }
            #nextの値が変わるので一旦変数に格納
            $nextNode = $targetNode->next;
            #次のノードへのリンクを逆方向に設定
            $targetNode->next = $prevNode;
            #操作が終わったノードは '前のノード' とする
            $prevNode = $targetNode;
            #次に見るノード
            $targetNode = $nextNode;
            return $sort($targetNode, $prevNode);
        };

        #終端が返ってくるのでそれを先頭に設定する
        $this->head = $sort($this->head, null);
    }

動かしてみる

メソッドを実装したので動作させてみます。
その前に出力用に整形するメソッドを実装しておきます。

    public function output()
    {
        $currentNode = $this->head;
        while ($currentNode) {
            echo $currentNode->data."\n";
            $currentNode = $currentNode->next;
        }
    }

それではリストを作成して出力してみます。

最後にノード追加

$list = new SinglyLinkedList();
$list->insertAtEnd(1);
$list->insertAtEnd(2);
$list->insertAtEnd(3);
$list->insertAtEnd(4);
$list->output();

1
2
3
4

先頭にノード追加

$list = new SinglyLinkedList();
$list->insertAtEnd(1);
$list->insertAtEnd(2);
$list->insertAtEnd(3);
$list->insertAtEnd(4);
$list->insertAtStart(420);
$list->output();

420
1
2
3
4

任意のノードの後ろに追加

3というデータを持つノードの後に追加してみます。

$list = new SinglyLinkedList();
$list->insertAtEnd(1);
$list->insertAtEnd(2);
$list->insertAtEnd(3);
$list->insertAtEnd(4);
$list->insertAfterNode(3, 420);
$list->output();

1
2
3
420
4

逆順に並び替え

さきほどのリストを逆順に並び替えます。

$list = new SinglyLinkedList();
$list->insertAtEnd(1);
$list->insertAtEnd(2);
$list->insertAtEnd(3);
$list->insertAtEnd(4);
$list->insertAfterNode(3, 420);
$list->reverse();
$list->output();

4
420
3
2
1

ノードの削除

さきほどのリストから3というデータを持つノードを削除します。

$list = new SinglyLinkedList();
$list->insertAtEnd(1);
$list->insertAtEnd(2);
$list->insertAtEnd(3);
$list->insertAtEnd(4);
$list->insertAfterNode(3, 420);
$list->reverse();
$list->remove(3);
$list->output();

4
420
2
1

ちゃんと動いてますね