前回のデータ構造のハッシュテーブルを見るの記事でハッシュテーブルに触れたが、ハッシュテーブルの衝突の問題が残っている。
PHPではハッシュテーブルの回避の手段としてチェイン法を採用しているが、チェイン法を見るためにはデータ構造の連結リストを把握する必要があるので、今回は連結リストを見ることにする。
といっても、ここではPHPでシンプルな単方向連結リストのみ触れる事にする。
今回も細かい説明は後回しにして、単方向連結リストに必要な関数を挙げる。
※PHPにはC言語等でいうところの構造体がないので、代替としてクラスを利用する。
class Node { public $x; public $next; } //Nodeの末尾に値を加える function _add(&$l, $x){ $node = new Node(); $node->x = $x; //リストにNodeがない場合は先頭にNodeを付与する if(is_null($l)){ $l = $node; }else{ //Nodeのnextの値がない場合は新たなNodeのアドレスを渡す if(is_null($l->next)){ $l->next = &$node; }else{ //nextの値がないNodeまで再帰的に移動する _add($l->next, $x); } } return true; }
上記の関数を早速使ってみる。
$list = null; _add($list, "サクラ"); _add($list, "エノキ"); _add($list, "カエデ"); _add($list, "ヒノキ");
上記のコードの値を図で可視化すると、
上の図のように各値を矢印で繋いだようになる。
PHPでは配列の要素数の指定がなかったり、連想配列があるので連結リストの恩恵は感じられないが、C言語等のメモリを直接触れるような言語であれば、連結リストは値の追加が無制限になるので重宝する。
この連結リストがハッシュテーブルの衝突を回避する上で重要だと冒頭で記載したので、前回のハッシュテーブルに連結リストを加味してコードを書き換えてみることにする。
追記
双方向連結リストの場合、
class Node { public $x; public $next; public $prev; }
のように次の他に前のノード(prev)のアドレスを持つプロパティを持つことで実現できる