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