Skip to content

@danielcooper /gist:4058973
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Linked Lists
class LinkedListNode
attr_accessor :next, :value
def initialize(value)
@value = value
end
end
class LinkedList
attr_reader :last, :first
def initialize(starting_values = [])
starting_values.each{|a| add(a)}
end
def add(item)
set_last_as LinkedListNode.new(item)
end
def add_at(index, what)
add_after(at(index),what)
end
def add_after(item, what)
what = LinkedListNode.new(what)
what.next = item.next if item.next
item.next = what
end
def at(index)
i = 0
each{|a| return a if i == index; i +=1}
end
def each(&block)
i = first
while i
yield i
i = i.next
end
end
def each_value(&block)
each_in_box{|a| yield a.value}
end
protected
def set_last_as(node)
if first
@last.next = node
@last = node
else
@first = @last = node
end
end
end
require "benchmark"
puts 'Adding to the end'
puts 'Array'
time = Benchmark.measure do
a = Array.new()
(0..10000).each do |i|
a << i
end
end
puts time
puts 'LinkedList'
time = Benchmark.measure do
a = LinkedList.new()
(0..10000).each do |i|
a.add i
end
end
puts time
puts 'Adding lots of items to a few indexes'
puts 'Array'
a = (1..10000).to_a
time = Benchmark.measure do
10.times do
el = rand(1000)
10000.times do
a.insert(el, "hello world")
end
end
end
puts time
puts 'LinkedList'
a = LinkedList.new((1..10000).to_a)
time = Benchmark.measure do
10.times do
el = a.at(rand(1000))
10000.times do
a.add_after(el, "hello world")
end
end
end
puts time
#=> Output
#Array
# 0.000000 0.000000 0.000000 ( 0.003510)
#LinkedList
# 0.020000 0.000000 0.020000 ( 0.021374)
#Adding lots of items to a few indexes
#Array
# 3.420000 0.020000 3.440000 ( 3.441180)
#LinkedList
# 0.260000 0.000000 0.260000 ( 0.263655)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.