Class: LinkedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/simms_structures/linked_list.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ LinkedList

Returns a new instance of LinkedList.



19
20
21
22
 
# File 'lib/simms_structures/linked_list.rb', line 19

def initialize
  @head = nil
  @tail = nil
end

Instance Method Details

#[](i) ⇒ Object 



24
25
26
27
 
# File 'lib/simms_structures/linked_list.rb', line 24

def [](i)
  each { |link, j| return link if i == j }
  nil
end

#each(&block) ⇒ Object 



77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/simms_structures/linked_list.rb', line 77

def each(&block)
  return nil if empty?

  link = first
  loop do
    block.yield(link, link.key)
    link = link.next
    break unless link
  end

end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


37
38
39
 
# File 'lib/simms_structures/linked_list.rb', line 37

def empty?
  @head == nil
end

#first ⇒ Object 



29
30
31
 
# File 'lib/simms_structures/linked_list.rb', line 29

def first
  @head
end

#get(key) ⇒ Object 



41
42
43
 
# File 'lib/simms_structures/linked_list.rb', line 41

def get(key)
  self[key].val if include?(key)
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/simms_structures/linked_list.rb', line 45

def include?(key)
  any? {|link| link.key == key}
end

#insert(key, val) ⇒ Object 



49
50
51
52
53
54
55
56
57
58
 
# File 'lib/simms_structures/linked_list.rb', line 49

def insert(key, val)
  link = Link.new(key, val)
  if empty?
    @head = link
  else
    @tail.next = link
    link.prev = @tail
  end
  @tail = link
end

#last ⇒ Object 



33
34
35
 
# File 'lib/simms_structures/linked_list.rb', line 33

def last
  @tail
end

#remove(key) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/simms_structures/linked_list.rb', line 60

def remove(key)
  link = self[key]  #the O(n) step

  return nil unless link

  if link == first
    link.next.prev = nil
    @head = link.next
  elsif link == last
    link.prev.next = nil
    @tail = link.prev
  else
    link.prev.next = link.next
    link.next.prev = link.prev
  end
end

#to_s ⇒ Object 



89
90
91
 
# File 'lib/simms_structures/linked_list.rb', line 89

def to_s
  inject([]) { |acc, link| acc << "[#{link.key}, #{link.val}]" }.join(", ")
end