植物のミカタ

前回のデータ構造のハッシュテーブルを見るの記事でハッシュテーブルに触れたが、ハッシュテーブルの衝突の問題が残っている。

PHPではハッシュテーブルの回避の手段としてチェイン法を採用しているが、チェイン法を見るためにはデータ構造の連結リストを把握する必要があるので、今回は連結リストを見ることにする。

といっても、ここではPHPでシンプルな単方向連結リストのみ触れる事にする。

連結リスト - Wikipedia

今回も細かい説明は後回しにして、単方向連結リストに必要な関数を挙げる。

※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)のアドレスを持つプロパティを持つことで実現できる