PHPでSingly linked list

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

# Singly Linked list

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

![Singly-linked-list.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/329016/37797c5c-157a-d301-212e-54b77f8d18c3.png)



# PHPで実装してみる

## クラス定義

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

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

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

```

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

```php

class SinglyLinkedList
{
    public $head;

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

}
```

## メソッドの実装

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

内容は以下の通りです。

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

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

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

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

```php
    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に設定。

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

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

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

```php

    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を設定。

```php

    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;
    }
```

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

```php

    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);
    }
```

## 動かしてみる

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

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

```

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

### 最後にノード追加

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

```

```
1
2
3
4
```

### 先頭にノード追加

```php

$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というデータを持つノードの後に追加してみます。

```php

$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
```

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

```php
$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というデータを持つノードを削除します。

```php
$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
```

ちゃんと動いてますね