class LinkedList
Public Class Methods
new()
click to toggle source
# File lib/simms_structures/linked_list.rb, line 19 def initialize @head = nil @tail = nil end
Public Instance Methods
[](i)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 24 def [](i) each { |link, j| return link if i == j } nil end
each(&block)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 77 def each(&block) return nil if empty? link = first loop do block.yield(link, link.key) link = link.next break unless link end end
empty?()
click to toggle source
# File lib/simms_structures/linked_list.rb, line 37 def empty? @head == nil end
first()
click to toggle source
# File lib/simms_structures/linked_list.rb, line 29 def first @head end
get(key)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 41 def get(key) self[key].val if include?(key) end
include?(key)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 45 def include?(key) any? {|link| link.key == key} end
insert(key, val)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 49 def insert(key, val) link = Link.new(key, val) if empty? @head = link else @tail.next = link link.prev = @tail end @tail = link end
last()
click to toggle source
# File lib/simms_structures/linked_list.rb, line 33 def last @tail end
remove(key)
click to toggle source
# File lib/simms_structures/linked_list.rb, line 60 def remove(key) link = self[key] #the O(n) step return nil unless link if link == first link.next.prev = nil @head = link.next elsif link == last link.prev.next = nil @tail = link.prev else link.prev.next = link.next link.next.prev = link.prev end end
to_s()
click to toggle source
# File lib/simms_structures/linked_list.rb, line 89 def to_s inject([]) { |acc, link| acc << "[#{link.key}, #{link.val}]" }.join(", ") end