rubyでlistなんてシュールだねぇと一瞬思ったんだけど，
実際，自作listと組み込みArrayのどちらが速いのか
気になったので試してみた．

結果から言うと，listの方が速かった．
Arrayの使い方を多少変えても，大勢は変わらい．
まあ実際には，ランダムアクセスしなきゃならん
アルゴリズムなのかどうかも関係してくるし，
プログラムの作りやすさの方が大事な事もあるだろうから
一概には言えないけども．

以下に実行結果．
$ cat list.rb
class Node
attr_accessor :prev,:next,:data
def initialize(data)
@data = data
end
end
firstnode = lastnode = nil
datas = [1,2,3,4,5,6,7,8,9]
datas.each do |x|
node = Node.new(x)
node.next = nil
unless lastnode.nil?
lastnode.next = node
node.prev = lastnode
lastnode = node
else
firstnode = lastnode = node
node.prev = nil
end
end
n = firstnode
100000.times{
x = 0
8.times{
x += n.data
n = n.next
}
x += n.data
8.times{
x += n.data
n = n.prev
}
x += n.data
}
$ time ruby list.rb
real 0m1.680s
user 0m1.261s
sys 0m0.418s

$ cat array1.rb
datas = [1,2,3,4,5,6,7,8,9]
100000.times{
x = 0
datas.each{|data| x += data }
datas.reverse_each{|data| x += data}
}
$ time ruby array1.rb
real 0m2.274s
user 0m1.430s
sys 0m0.843s

$ cat array2.rb
datas = [1,2,3,4,5,6,7,8,9]
100000.times{
x = 0
datas.each{|data| x += data }
datas.each{|data| x += data }
}
$ time ruby array2.rb
real 0m2.127s
user 0m1.369s
sys 0m0.756s

$ cat array3.rb
datas = [1,2,3,4,5,6,7,8,9]
100000.times{
x = 0
9.times{|i| x += datas[i] }
9.times{|i| x += datas[i] }
}
$ time ruby array3.rb
real 0m2.396s
user 0m1.647s
sys 0m0.747s

[...] ツリー構造とは樹形図のようになったデータ構造のことです。Windowsのファイル構造はツリー構造ですね。 難しそうに感じますが、以前やったリスト構造では、データが次のノードへのポインタを一つしかもっていなかったものを複数にするというだけで実現できます。 [...]

>class Node
> attr_accessor :prev,:next,:data
本のなかでは、この前と後ろのノードのアドレスを示すprevとnextはC言語のポインタを使っていますが、Rubyにはポインタはないので参照を使ったという意味です。

ポインタと参照は同じものではありませんが、今回は参照でも同じ機能を果たせるので参照を使用しています。