class DataStructures101::LinkedList

@author Rene Hernandez @since 0.1

Attributes

size[R]

Public Class Methods

new(*values) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 30
def initialize(*values)
  @size = 0
  @head = Node.new(nil)
  @tail = Node.new(nil, @head)
  @head.next = @tail

  push(*values)
end

Public Instance Methods

<<(value) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 39
def <<(value)
  push(value)
end
delete(value) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 43
def delete(value)
  curr = @head.next
  return_value = nil
  until curr == @tail
    if curr.value == value
      remove_node(curr)
      return_value = curr.value
    end
    curr = curr.next
  end

  return_value
end
each() { |value| ... } click to toggle source
# File lib/data_structures_101/linked_list.rb, line 57
def each
  return enum_for(:each) unless block_given?

  curr = head.next
  until curr.nil?
    yield curr.value
    curr = curr.next
  end
end
fetch(index) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 67
def fetch(index)
  fetch_node(index).value
end
first(n = nil) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 82
def first(n = nil)
  return @head.next.value if n.nil?

  raise ArgumentError, 'negative array size' if n.negative?

  new_list_from_range(0, n - 1)
end
insert(index, *values) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 71
def insert(index, *values)
  curr = fetch_node(index)

  curr = index.negative? ? curr : curr.prev

  values.each do |value|
    curr = add_node(value, curr.next)
  end
  self
end
last(n = nil) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 90
def last(n = nil)
  return @tail.prev.value if n.nil?

  raise ArgumentError, 'negative array size' if n.negative?

  new_list_from_range(size - n, size - 1)
end
push(*values) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 98
def push(*values)
  values.each do |value|
    add_node(value, @tail)
  end
  self # Allows to concatenate consecutive calls to push
end

Private Instance Methods

add_node(value, next_node) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 123
def add_node(value, next_node)
  node = Node.new(value, next_node.prev, next_node)
  node.prev.next = node
  node.next.prev = node
  @size += 1
  node
end
fetch_node(index) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 107
def fetch_node(index)
  index += size if index.negative?

  error_msg = "index #{index} outside of array bounds: #{-size}...#{size}"
  raise IndexError, error_msg if index.negative? || index >= size

  pos = 0
  curr = @head.next
  while pos < index
    curr = curr.next
    pos += 1
  end

  curr
end
new_list_from_range(start_index, finish_index) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 137
def new_list_from_range(start_index, finish_index)
  new_list = LinkedList.new

  return new_list if size.zero? || start_index == size || finish_index == -1

  start_index = 0 if start_index.negative?
  finish_index = size - 1 if finish_index >= size

  start_node = fetch_node(start_index)
  finish_node = fetch_node(finish_index)

  until start_node == finish_node.next
    new_list << start_node.value
    start_node = start_node.next
  end

  new_list
end
remove_node(node) click to toggle source
# File lib/data_structures_101/linked_list.rb, line 131
def remove_node(node)
  node.prev.next = node.next
  node.next.prev = node.prev
  @size -= 1
end