Class: LinkedList

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ LinkedList

Returns a new instance of LinkedList.



4
5
6
7
8
9
 
# File 'lib/data_structures/linked_list.rb', line 4

def initialize
  @head = LinkedListNode.new
  @tail = LinkedListNode.new
  @head.send(:next=, @tail)
  @tail.send(:prev=, @head)
end

Instance Method Details

#add_after_key(ref_key, key, val) ⇒ Object

Raises:

  • (ArgumentError) 


80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/data_structures/linked_list.rb', line 80

def add_after_key(ref_key, key, val)
  ref_node = self.find_by_key(ref_key)
  raise ArgumentError.new("No Node found with key=#{ref_key}") if ref_node.nil?

  node = LinkedListNode.new(key, val)
  next_node = ref_node.send(:next)

  node.send(:next=, next_node)
  node.send(:prev=, ref_node)

  ref_node.send(:next=, node)
  next_node.send(:prev=, node)

  node
end

#add_before_key(ref_key, key, val) ⇒ Object

Raises:

  • (ArgumentError) 


96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/data_structures/linked_list.rb', line 96

def add_before_key(ref_key, key, val)
  ref_node = self.find_by_key(ref_key)
  raise ArgumentError.new("No Node found with key=#{ref_key}") if ref_node.nil?

  node = LinkedListNode.new(key, val)
  prev_node = ref_node.send(:prev)

  node.send(:next=, ref_node)
  node.send(:prev=, prev_node)

  ref_node.send(:prev=, node)
  prev_node.send(:next=, node)

  node
end

#append(key = nil, val = nil) ⇒ Object 



54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/data_structures/linked_list.rb', line 54

def append(key=nil, val=nil)
  node = LinkedListNode.new(key, val)
  last = @tail.send(:prev)

  last.send(:next=, node)
  @tail.send(:prev=, node)

  node.send(:prev=, last)
  node.send(:next=, @tail)

  node
end

#each(&prc) ⇒ Object 



153
154
155
156
157
158
159
160
161
162
163
 
# File 'lib/data_structures/linked_list.rb', line 153

def each(&prc)
  current_node = @head.send(:next)
  return self if current_node.nil?

  while current_node != @tail
    prc.call(current_node)
    current_node = current_node.send(:next)
  end

  self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @head.send(:next) == @tail
end

#find_by_key(key) ⇒ Object 



112
113
114
115
 
# File 'lib/data_structures/linked_list.rb', line 112

def find_by_key(key)
  self.each { |node| return node if node.send(:key) == key }
  nil
end

#find_by_val(val) ⇒ Object 



117
118
119
120
 
# File 'lib/data_structures/linked_list.rb', line 117

def find_by_val(val)
  self.each { |node| return node if node.send(:val) == val }
  nil
end

#first ⇒ Object 



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

def first
  first = @head.send(:next)
  first == @tail ? nil : first
end

#include_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


122
123
124
125
 
# File 'lib/data_structures/linked_list.rb', line 122

def include_key?(key)
  self.each { |node| return true if node.send(:key) == key }
  false
end

#include_val?(val) ⇒ Boolean

Returns:

  • (Boolean) 


127
128
129
130
 
# File 'lib/data_structures/linked_list.rb', line 127

def include_val?(val)
  self.each { |node| return true if node.send(:val) == val }
  false
end

#inspect ⇒ Object 



22
23
24
25
26
27
 
# File 'lib/data_structures/linked_list.rb', line 22

def inspect
  return "-" if self.empty?

  vals = self.to_a { |n| n.send(:val) }
  vals.join(' <=> ')
end

#last ⇒ Object 



49
50
51
52
 
# File 'lib/data_structures/linked_list.rb', line 49

def last
  last = @tail.send(:prev)
  last == @head ? nil : last
end

#length ⇒ Object 



33
34
35
36
37
38
39
40
41
42
 
# File 'lib/data_structures/linked_list.rb', line 33

def length
  return 0 if self.empty?
  count = 0
  node = self.first
  until node == @tail
    count += 1
    node = node.send(:next)
  end
  count
end

#prepend(key = nil, val = nil) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/data_structures/linked_list.rb', line 67

def prepend(key=nil, val=nil)
  node = LinkedListNode.new(key, val)
  first = @head.send(:next)

  first.send(:prev=, node)
  @head.send(:next=, node)

  node.send(:prev=, @head)
  node.send(:next=, first)

  node
end

#remove(key) ⇒ Object 



132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/data_structures/linked_list.rb', line 132

def remove(key)
  node = self.find_by_key(key)
  return nil if node.nil?

  prev_node = node.send(:prev)
  next_node = node.send(:next)

  prev_node.send(:next=, next_node)
  next_node.send(:prev=, prev_node)

  node
end

#to_a ⇒ Object 



11
12
13
 
# File 'lib/data_structures/linked_list.rb', line 11

def to_a
  self.reduce([]) { |arr, n| arr << n.send(:val) }
end

#to_s ⇒ Object 



15
16
17
18
19
20
 
# File 'lib/data_structures/linked_list.rb', line 15

def to_s
  return "-" if self.empty?

  vals = self.to_a { |n| n.send(:val) }
  vals.join(' <=> ')
end

#update(key, new_val) ⇒ Object

Raises:

  • (ArgumentError) 


145
146
147
148
149
150
151
 
# File 'lib/data_structures/linked_list.rb', line 145

def update(key, new_val)
  node = self.find_by_key(key)
  raise ArgumentError.new("Couldn't find Node with key=#{key}") if node.nil?

  node.send(:val=, new_val)
  node
end