class LinkedList
Public Class Methods
new()
click to toggle source
# File lib/data_structures/linked_list.rb, line 4 def initialize @head = LinkedListNode.new @tail = LinkedListNode.new @head.send(:next=, @tail) @tail.send(:prev=, @head) end
Public Instance Methods
add_after_key(ref_key, key, val)
click to toggle source
# File lib/data_structures/linked_list.rb, line 80 def add_after_key(ref_key, key, val) ref_node = self.find_by_key(ref_key) raise ArgumentError.new("No Node found with key=#{ref_key}") if ref_node.nil? node = LinkedListNode.new(key, val) next_node = ref_node.send(:next) node.send(:next=, next_node) node.send(:prev=, ref_node) ref_node.send(:next=, node) next_node.send(:prev=, node) node end
add_before_key(ref_key, key, val)
click to toggle source
# File lib/data_structures/linked_list.rb, line 96 def add_before_key(ref_key, key, val) ref_node = self.find_by_key(ref_key) raise ArgumentError.new("No Node found with key=#{ref_key}") if ref_node.nil? node = LinkedListNode.new(key, val) prev_node = ref_node.send(:prev) node.send(:next=, ref_node) node.send(:prev=, prev_node) ref_node.send(:prev=, node) prev_node.send(:next=, node) node end
append(key=nil, val=nil)
click to toggle source
# File lib/data_structures/linked_list.rb, line 54 def append(key=nil, val=nil) node = LinkedListNode.new(key, val) last = @tail.send(:prev) last.send(:next=, node) @tail.send(:prev=, node) node.send(:prev=, last) node.send(:next=, @tail) node end
each(&prc)
click to toggle source
# File lib/data_structures/linked_list.rb, line 153 def each(&prc) current_node = @head.send(:next) return self if current_node.nil? while current_node != @tail prc.call(current_node) current_node = current_node.send(:next) end self end
empty?()
click to toggle source
# File lib/data_structures/linked_list.rb, line 29 def empty? @head.send(:next) == @tail end
find_by_key(key)
click to toggle source
# File lib/data_structures/linked_list.rb, line 112 def find_by_key(key) self.each { |node| return node if node.send(:key) == key } nil end
find_by_val(val)
click to toggle source
# File lib/data_structures/linked_list.rb, line 117 def find_by_val(val) self.each { |node| return node if node.send(:val) == val } nil end
first()
click to toggle source
# File lib/data_structures/linked_list.rb, line 44 def first first = @head.send(:next) first == @tail ? nil : first end
include_key?(key)
click to toggle source
# File lib/data_structures/linked_list.rb, line 122 def include_key?(key) self.each { |node| return true if node.send(:key) == key } false end
include_val?(val)
click to toggle source
# File lib/data_structures/linked_list.rb, line 127 def include_val?(val) self.each { |node| return true if node.send(:val) == val } false end
inspect()
click to toggle source
# File lib/data_structures/linked_list.rb, line 22 def inspect return "-" if self.empty? vals = self.to_a { |n| n.send(:val) } vals.join(' <=> ') end
last()
click to toggle source
# File lib/data_structures/linked_list.rb, line 49 def last last = @tail.send(:prev) last == @head ? nil : last end
length()
click to toggle source
# File lib/data_structures/linked_list.rb, line 33 def length return 0 if self.empty? count = 0 node = self.first until node == @tail count += 1 node = node.send(:next) end count end
prepend(key=nil, val=nil)
click to toggle source
# File lib/data_structures/linked_list.rb, line 67 def prepend(key=nil, val=nil) node = LinkedListNode.new(key, val) first = @head.send(:next) first.send(:prev=, node) @head.send(:next=, node) node.send(:prev=, @head) node.send(:next=, first) node end
remove(key)
click to toggle source
# File lib/data_structures/linked_list.rb, line 132 def remove(key) node = self.find_by_key(key) return nil if node.nil? prev_node = node.send(:prev) next_node = node.send(:next) prev_node.send(:next=, next_node) next_node.send(:prev=, prev_node) node end
to_a()
click to toggle source
# File lib/data_structures/linked_list.rb, line 11 def to_a self.reduce([]) { |arr, n| arr << n.send(:val) } end
to_s()
click to toggle source
# File lib/data_structures/linked_list.rb, line 15 def to_s return "-" if self.empty? vals = self.to_a { |n| n.send(:val) } vals.join(' <=> ') end
update(key, new_val)
click to toggle source
# File lib/data_structures/linked_list.rb, line 145 def update(key, new_val) node = self.find_by_key(key) raise ArgumentError.new("Couldn't find Node with key=#{key}") if node.nil? node.send(:val=, new_val) node end