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