class LinkedList
Singly-Linked List data structure Worst-Case Space Complexity: O(n)
Public Class Methods
new(data_set=[])
click to toggle source
# File lib/algorithm_selector.rb, line 424 def initialize(data_set=[]) @head = LinkNode.new @tail = LinkNode.new @head.next = @tail @tail.prev = @head data_set.each { |i| insert(i) } end
Public Instance Methods
[](i)
click to toggle source
# File lib/algorithm_selector.rb, line 437 def [](i) each_with_index { |link, j| return link if i == j } nil end
each() { |current_link| ... }
click to toggle source
# File lib/algorithm_selector.rb, line 487 def each current_link = @head.next until current_link == @tail yield current_link current_link = current_link.next end end
empty?()
click to toggle source
# File lib/algorithm_selector.rb, line 450 def empty? @head.next == @tail end
first()
click to toggle source
# File lib/algorithm_selector.rb, line 442 def first empty? ? nil : @head.next end
get(val)
click to toggle source
# File lib/algorithm_selector.rb, line 454 def get(val) each { |link| return link.val if link.val == val } nil end
include?(val)
click to toggle source
# File lib/algorithm_selector.rb, line 459 def include?(val) any? { |link| link.val == val } end
insert(val)
click to toggle source
Insertion, Worst-Case Time Complexity: O(1)
# File lib/algorithm_selector.rb, line 464 def insert(val) each { |link| return link.val = val if link.val == val } new_link = LinkNode.new(val) @tail.prev.next = new_link new_link.prev = @tail.prev new_link.next = @tail @tail.prev = new_link new_link end
last()
click to toggle source
# File lib/algorithm_selector.rb, line 446 def last empty? ? nil : @tail.prev end
remove(val)
click to toggle source
Deletion, Worst-Case Time Complexity: O(1)
# File lib/algorithm_selector.rb, line 475 def remove(val) each do |link| if link.val == val link.prev.next = link.next link.next.prev = link.prev link.next, link.prev = nil, nil return link.val end end nil end
search(target)
click to toggle source
Search, Worst-Case Time Complexity: O(n)
# File lib/algorithm_selector.rb, line 433 def search(target) each { |current_link| return current_link.val if current_link.val == target } end