PHP でリンクリストを実装する

1. PHP で SplDoublyLinkedList クラスを使用してリンクリストを実装する
2. push() メソッドを使用して、リンクリストに値を挿入する
3. add() メソッドを使用して、リンクリストに値を挿入する
4. pop() メソッドを使用して、リンクリストの要素を削除する
5. リンクリストから上位と下位の値を見つける

この記事では、PHP でのリンクリストの実装を紹介します。

PHP で SplDoublyLinkedList クラスを使用してリンクリストを実装する

リンクリストは、多くのプログラミング言語で実装されている一般的なデータ構造です。これは線形であり、相互にリンクされたノードが含まれています。

各ノードには、データと隣接ノードへのリンクが含まれています。したがって、リンクリストはノードのチェーンを形成します。リンクリストにはさまざまなバリエーションがあります。

1. 単一リンクリスト：単方向です。順方向にのみ移動します。
2. 二重リンクリスト：双方向です。順方向と逆方向の両方に移動します。
3. 循環リンクリスト：一方向および循環です。
4. 循環二重リンクリスト：双方向で循環的です。

リンクリストでは、さまざまな操作を実行できます。基本的な操作は次のとおりです。

• トラバーサル
• 挿入
• 消す
• アップデート
• 検索

PHP は、リンクリストを実装するためのクラス SplDoublyLinkedList を提供しています。二重リンクリストです。

push() メソッドを使用して、リンクリストに値を挿入する

push() メソッドは、プッシュされるパラメーターを受け入れ、リスト内の値を追加できるようにします。要素はリンクリストの最後にプッシュされます。

たとえば、クラス SplDoublyLinkedList のインスタンスを作成し、それを $list 変数に割り当てます。push() メソッドを呼び出し、要素を挿入します。

サンプルコード：

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

以下の例では、空のリンクリストに要素 10、20、30、40、および 40 を追加しています。要素 40 が 2 回追加されることに注意してください。

次の関数を使用して、リストの要素を表示できます。

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

rewind() メソッドは、リンクリストの先頭からイテレータを巻き戻します。たとえば、イテレータはリストの最初の要素に移動します。

valid() メソッドはリンクリストにさらにノードが含まれているかどうかをチェックし、next() メソッドはリンクリストの次の項目に移動します。したがって、上記の例のように for ループでこれらのメソッドを使用して、リンクリストの要素を反復処理できます。

ループ内では、current() メソッドが現在の要素を示します。したがって、現在の要素が印刷されます。

リスト要素を出力する必要があるときはいつでも、この関数 displayList() を呼び出すことができます。この記事では、この関数を複数回使用します。

以下は、引数として $list を指定して displayList() 関数を呼び出したときの出力です。

出力：

10
20
30
40
40

add() メソッドを使用して、リンクリストに値を挿入する

add() メソッドを使用して、位置を指定することでリンクリストに要素を挿入できます。このメソッドは 2つのパラメーターを取ります。

最初のパラメーターはアイテムが挿入されるインデックスであり、2 番目のパラメーターは挿入されるアイテムです。たとえば、パラメータとして 4 と 50 を指定して add() メソッドを呼び出し、displayList() メソッドを呼び出します。

サンプルコード：

$list->add(4,50);
displayList($list);

上記のコードは、作成したリンクリストの 4 番目のインデックスに要素 50 を追加します。

出力：

10
20
30
40
50
40

その結果、要素 50 が 4 番目のインデックスに表示されます。以前は 4 番目のインデックスにあった要素 40 は、リンクリストの最後にシフトされます。

pop() メソッドを使用して、リンクリストの要素を削除する

pop() メソッドを使用して、リンクリストから最後の要素を削除できます。このメソッドはパラメーターを取りません。

上記の最後の出力の時点で、リストには次の要素が含まれています。

10
20
30
40
50
40

pop() メソッドは、リンクリストから最後の要素（40）を削除します。

サンプルコード：

$list->pop();
displayList($list);

出力：

10
20
30
40
50

リンクリストから上位と下位の値を見つける

リンクリストの一番上の値は top() メソッドを使用して見つけることができ、一番下の値には bottom() メソッドを使用できます。以下の例は、上記の例の続きでもあります。

リストには以下の項目が含まれています。

10
20
30
40
50

$list オブジェクトを使用して top() および bottom() 関数を呼び出し、echo 関数を使用してそれらを出力できます。

サンプルコード：

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

その結果、一番上のアイテムは 50 と表示され、一番下のアイテムは 10 と表示されます。

出力：

10
20
30
40
50
the top value: 50
the bottom value: 10