Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Linked Lists

View gist:4058973
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 131
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.