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) 


69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/data_structures/linked_list.rb', line 69

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) 


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/data_structures/linked_list.rb', line 85

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 



43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/data_structures/linked_list.rb', line 43

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 



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

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 



101
102
103
104
 
# File 'lib/data_structures/linked_list.rb', line 101

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

#find_by_val(val) ⇒ Object 



106
107
108
109
 
# File 'lib/data_structures/linked_list.rb', line 106

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

#first ⇒ Object 



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

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

#include_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


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

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

#include_val?(val) ⇒ Boolean

Returns:

  • (Boolean) 


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

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 



38
39
40
41
 
# File 'lib/data_structures/linked_list.rb', line 38

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

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



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

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 



121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/data_structures/linked_list.rb', line 121

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) 


134
135
136
137
138
139
140
 
# File 'lib/data_structures/linked_list.rb', line 134

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