Class: DDQL::LinkedList

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

Defined Under Namespace

Classes: NavigationError, Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(head = nil) ⇒ LinkedList

Returns a new instance of LinkedList.



25
26
27
28
29
30
 
# File 'lib/ddql/linked_list.rb', line 25

def initialize(head=nil)
  @doubly_linked = false
  @head          = head
  @size          = head.nil? ? 0 : 1
  @tail          = @head
end

Instance Attribute Details

#head ⇒ Object (readonly)

Returns the value of attribute head.



23
24
25
 
# File 'lib/ddql/linked_list.rb', line 23

def head
  @head
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



23
24
25
 
# File 'lib/ddql/linked_list.rb', line 23

def size
  @size
end

Instance Method Details

#append(value) ⇒ Object Also known as: << 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/ddql/linked_list.rb', line 32

def append(value)
  if @head
    tail = find_tail
    if Node === value
      value.previous = tail if @doubly_linked
      tail.next = value
    else
      tail.next = Node.new(value)
      tail.next.previous = tail if @doubly_linked
    end
    @tail = tail.next
  else
    @head = @tail = Node === value ? value : Node.new(value)
  end
  @size += 1
end

#append_after(target, value) ⇒ Node|NilClass Also known as: insert

Insert the value after the target

Returns:

  • (Node|NilClass) —

    nil if target is not found, otherwise the inserted node for value



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/ddql/linked_list.rb', line 53

def append_after(target, value)
  node = find(target)
  return unless node
  old_next = node.next
  if @doubly_linked
    if Node === value
      value.previous = node
      value.next     = old_next
      node.next      = value
    else
      node.next = Node.new(value, previous_node: node, next_node: old_next)
    end
  elsif Node === value
    value.next = old_next
    node.next  = value
  else
    node.next = Node.new(value, next_node: old_next)
  end
  @tail = node.next if old_next.nil?
  node.next
end

#at(index) ⇒ Object Also known as: [] 



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

def at(index)
  return nil if index < 0 || index >= size
  return @head if index == 0
  return @tail if index == size - 1

  current_index = 0
  current_node  = head
  while current_node = current_node.next
    current_index += 1
    return current_node if current_index == index
  end
end

#delete(value) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/ddql/linked_list.rb', line 90

def delete(value)
  if value.is_a?(Node) && @head == value
    @head = @head.next
    value.next = value.previous = nil
    @tail = @head if @head.nil? || @head.next.nil?
  elsif @head.value == value
    node = @head.next
    @head.next = @head.previous = nil
    value = @head
    @head = node
    @tail = @head if @head.next.nil?
  else
    node = find_before(value)

    if node && node.next == tail
      @tail = node
      node.next = nil
    end

    node.next = node.next.next if node && node.next
    node.next.previous = node if doubly_linked! && node.next
  end
  @size -= 1
  value
end

#doubly_linked! ⇒ Object 



116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/ddql/linked_list.rb', line 116

def doubly_linked!
  return self if doubly_linked?

  current = nil
  each_node do |node|
    node.previous = current
    current = node
  end
  @doubly_linked = true
  self
end

#doubly_linked? ⇒ Boolean

Returns:

  • (Boolean) 


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

def doubly_linked?
  @doubly_linked
end

#each ⇒ Object 



132
133
134
135
136
137
138
139
 
# File 'lib/ddql/linked_list.rb', line 132

def each
  return to_enum unless block_given?
  node = @head
  while node
    yield node.value
    node = node.next
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


141
142
143
 
# File 'lib/ddql/linked_list.rb', line 141

def empty?
  @size == 0
end

#find(value = nil, &blk) ⇒ Object 



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

def find(value=nil, &blk)
  node = @head
  is_node = value.is_a?(Node)
  return false if !node.next && (!blk || (blk && !yield(node)))
  return node  if (is_node && node == value) || node.value == value || (blk && yield(node))
  while (node = node.next)
    return node if (is_node && node == value) || node.value == value || (blk && yield(node))
  end
end

#find_before(value) ⇒ Object 



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/ddql/linked_list.rb', line 166

def find_before(value)
  node = @head
  return false if !node.next

  is_node = value.is_a?(Node)
  if (is_node && node.next == value) || node.next.value == value
    return node
  end

  while (node = node.next)
    if (is_node && node.next == value) || node.next.value == value
      return node
    end
  end
end

#find_from_tail(value = nil, &blk) ⇒ Object

Raises:



155
156
157
158
159
160
161
162
163
164
 
# File 'lib/ddql/linked_list.rb', line 155

def find_from_tail(value=nil, &blk)
  raise NavigationError, "singly-linked lists don't support finding nodes from the tail" unless doubly_linked?
  node = @tail
  is_node = value.is_a?(Node)
  return false if !node.previous && (!blk || (blk && !yield(node)))
  return node  if (is_node && node == value) || node.value == value || (blk && yield(node))
  while (node = node.previous)
    return node if (is_node && node == value) || node.value == value || (blk && yield(node))
  end
end

#find_tail ⇒ Object Also known as: tail 



182
183
184
185
186
187
188
189
 
# File 'lib/ddql/linked_list.rb', line 182

def find_tail
  if @tail.nil?
    node = @head
    return @tail = node if !node.next
    return @tail = node if !node.next while (node = node.next)
  end
  @tail
end

#peek ⇒ Object 



192
193
194
195
 
# File 'lib/ddql/linked_list.rb', line 192

def peek
  return nil unless @head
  @head.value
end

#poll ⇒ Object 



197
198
199
200
201
202
203
204
205
 
# File 'lib/ddql/linked_list.rb', line 197

def poll
  return nil unless @head
  previous_head = @head
  @head = previous_head.next
  @size -= 1
  @head.previous = nil if @head
  previous_head.next = nil
  previous_head.value
end

#print(stream = STDOUT) ⇒ Object 



207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/ddql/linked_list.rb', line 207

def print(stream=STDOUT)
  node = @head
  prefix = ''
  postfix = ''
  stream.print "(size: #{size}) "
  while node
    postfix = "\n⨂" unless node.next
    stream.print prefix
    stream.print node
    stream.print postfix
    stream.print "\n"
    node = node.next
    prefix = '  ⤿  ' if node
  end
end

#replace!(from:, to:, with:) ⇒ Object

Replace a range of nodes from from to to, inclusive, with the given with. from, to, and with can all be values or nodes.

Returns:

  • self



228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/ddql/linked_list.rb', line 228

def replace!(from:, to:, with:)
  first_node = find(from)
  last_node  = find(to)
  tail       = find_tail
  raise 'cannot find appropriate range for replacement' if first_node.nil? || last_node.nil?

  replacement = Node === with ? with : Node.new(with)
  if first_node == head
    @head = replacement
    unless last_node == tail
      new_tail          = last_node.next
      replacement.next  = new_tail
      new_tail.previous = replacement if doubly_linked?
    end
    return self
  end

  if doubly_linked?
    replacement.previous      = first_node.previous
    replacement.previous.next = replacement
    last_node.next.previous   = replacement
  elsif first_node != head
    previous = find_before(first_node)
    previous.next = replacement
  end
  replacement.next = last_node.next
  self
end

#singly_linked! ⇒ Object 



257
258
259
260
261
262
263
 
# File 'lib/ddql/linked_list.rb', line 257

def singly_linked!
  each_node do |node|
    node.previous = nil
  end
  @doubly_linked = false
  self
end