# create a struct with :value and :next
Cell = Struct.new(:value, :next)
# create a head of our list
list = Cell.new("head. hi", nil)
# array
a = []
# method which create one more cell and return the struct
def linked_list(value, cell)
return Cell.new(value, cell)
end
# simple benchmark timer. t1 - t2 = waiting time ;)
def bench type
t1 = Time.now
yield
t2 = Time.now
p "#{type}'s took #{t2 - t1}s"
end
bench ("array") {
100000.times { a.insert 0,10} # O(n)
}
bench ("linked list") {
100000.times { list = linked_list(10, list) } # O(1)
}
http://khakimov.com/blog/2012/05/11/back-to-school-linked-list-with-ruby/
无引用文章
在头上插入链表比数组快不是很正常的事情么，这种数据结构特性不同啊，而且原文最后也说到：
Of course Arrays are cool, because you can do many other things faster than linked list (trade offs)
不同的数据结构有不同的特点嘛
基本没实用意义的，一是有 map, reduce 等优化过性能的高级方法，我们很少需要操作底层插入，二是我们用数组的时候都是在尾插入而不是在头插入...
在尾插入数组，最后 reverse, 比 list 快多了：
bench ("array") {
100000.times { a << 10 }
a.reverse!
}
