public
Created

Linked Lists

  • Download Gist
gistfile1.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.