有限リンクトリストの連結
二つの有限リンクトリストを連結してみます.つまり,
$list1= [ 1, [ 2, [ 3, undef] ] ]; $list2= [ 10, [20, [30, undef] ] ];
から
$list = [ 1, [ 2, [ 3, [ 10, [20, [30, undef] ] ] ] ] ];
を作る操作です.
sub concat{ my ($a,$b)=@_; my $c = $a; while (my $temp = tail($c)){ $c=$temp; } $c->[1]=$b; return $a; } print Dumper concat ($list1, $list2); $VAR1 = [ 1, [ 2, [ 3, [ 10, [ 20, [ 30, undef ] ] ] ] ] ];
二つの有限リンクトリストを受け取って,最初のリンクトリストをtailでたどっていきます.たどっていくときに,今どこにいるのかを知るために$cを用意します.最初は先頭なので$c=$aです.tail($c)で次のノードを得ます,それがundefならばそこが行き止まり,undefでないならばまだ続くので,tail($c)を新たな$cとします*1.
undefになったときにwhileループから抜け,そのとき$cは最初の引数のリンクトリスト$aの最後をさしているので(例の場合は,$c=[3,undef]),このundefのところ($c->[1])に追加のリンクトリストを代入すれば連結ができるわけです.
$cは$aの中の要素を一個一個たどるようにリファレンスしているだけなので,$c(が参照しているもの)に手を加えるのは,$aを操作していることになるるのです.
*1:tailの呼び出し回数を減らしたかったので$tempを経由します.