A Simple LinkedList Implementation in Ruby

2008-11-11

Being bored out of my mind on Monday night, and not having anything interesting to watch on TV, I decided I’d try my hand at implementing a linked list in Ruby. For the impatient:

1 $ sudo gem install linked_list

Unfortunately, performance is very poor:

Building a list of 1 million random strings
Took 4.389 seconds
Converting to an array
Took 1.686 seconds
                      user     system      total        real
list#push/pop     0.350000   0.000000   0.350000 (  0.364001)
array#push/pop    0.000000   0.000000   0.000000 (  0.009894)
                      user     system      total        real
list#last         0.000000   0.000000   0.000000 (  0.000027)
array#last        0.000000   0.000000   0.000000 (  0.000012)
                      user     system      total        real
list#first        0.010000   0.000000   0.010000 (  0.001188)
array#first       0.000000   0.000000   0.000000 (  0.000449)
                      user     system      total        real
list#reverse      7.540000   0.170000   7.710000 (  7.806306)
array#reverse     0.010000   0.010000   0.020000 (  0.008443)
                      user     system      total        real
list#dup         23.080000   0.380000  23.460000 ( 24.039316)
array#dup         0.000000   0.000000   0.000000 (  0.000017)

NOTE: #dup is implemented as self.reverse.reverse, which is pretty inefficient, I know. Thanks for asking.

I probably have implementation issues, but I expected #push and #pop to be as fast as the Array implementation. Anyway, if anyone’s interested, there’s a GitHub repository.

blog comments powered by Disqus