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