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