class Algorithmable::DataStructs::LinkedList::Singly
Public Instance Methods
delete(item)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 71 def delete(item) tmp_node = @front prev_node = nil until tmp_node.nil? if tmp_node.item == item if tmp_node == @front next_node = @front.next @back = next_node if @front == @back @front = next_node @size -= 1 else prev_node.next = tmp_node.next @back = prev_node if tmp_node == @back @size -= 1 end return true else prev_node = tmp_node end tmp_node = tmp_node.next end end
merge(other)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 96 def merge(other) front = recursive_merge_imp self.front, other.front list = self.class.new while front list.push_back front.item front = front.next end list end
pop_back()
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 56 def pop_back return unless @back node = @back if @front == @back clear! else prev = @front prev = prev.next while prev.next != @back @back = prev @back.next = nil @size -= 1 end node.item end
pop_front()
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 42 def pop_front return unless @front node = @front if @front == @back clear! else @front = @front.next @size -= 1 end node.item end
push_back(obj)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 29 def push_back(obj) node = new_node(obj) if @back @back.next = node @back = node else @front = node @back = @front end @size += 1 obj end
push_front(obj)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 16 def push_front(obj) node = new_node(obj) if @front node.next = @front @front = node else @front = node @back = @front end @size += 1 obj end
reverse!()
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 106 def reverse! @back = @front @front = reverse_imp @front self end
sort!()
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 112 def sort! sort_linked_list @front end
Private Instance Methods
new_node(item, next_pinter = nil)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 182 def new_node(item, next_pinter = nil) Node.new item, next_pinter end
recursive_merge_imp(node1, node2)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 145 def recursive_merge_imp(node1, node2) return node2 if node1.nil? return node1 if node2.nil? node1 = node1.dup node2 = node2.dup if node1.item < node2.item node1.next = recursive_merge_imp(node1.next, node2) node1 else node2.next = recursive_merge_imp(node2.next, node1) node2 end end
remove_next(prev)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 167 def remove_next(prev) if prev.nil? pop_front elsif prev.next == @back @back = prev @back.next = nil @size -= 1 elsif prev == @back return else prev.next = prev.next.next @size -= 1 end end
reverse_imp(root)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 159 def reverse_imp(root) return root if root.nil? || root.next.nil? node = reverse_imp(root.next) root.next.next = root root.next = nil node end
sort_linked_list(node)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 118 def sort_linked_list(node) return unless node || node.empty? swapped = false prev = nil begin swapped = false current = node until current.next == prev if current.item > current.next.item swap_nodes current, current.next swapped = true end current = current.next end prev = current end while swapped end
swap_nodes(node1, node2)
click to toggle source
# File lib/algorithmable/data_structs/linked_list/singly.rb, line 139 def swap_nodes(node1, node2) tmp = node1.item node1.item = node2.item node2.item = tmp end