Class: LinkedList::List

Inherits:
Object
  • Object
show all
Includes:
Conversions
Defined in:
lib/linked-list/list.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Conversions

List, Node

Constructor Details

#initialize ⇒ List

Returns a new instance of List.



10
11
12
13
14
 
# File 'lib/linked-list/list.rb', line 10

def initialize
  @head   = nil
  @tail   = nil
  @length = 0
end

Instance Attribute Details

#length ⇒ Object (readonly) Also known as: size

Returns the value of attribute length.



7
8
9
 
# File 'lib/linked-list/list.rb', line 7

def length
  @length
end

Instance Method Details

#delete(val = nil, &block) ⇒ Object

Removes first matched node.data from the the list by passed block or value.

If val is a Node, removes that node from the list. Behavior is undefined if val is a Node that’s not a member of this list.

Returns:

Deleted node’s data



139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/linked-list/list.rb', line 139

def delete(val = nil, &block)
  if val.respond_to?(:to_node)
    node = val.to_node
    __unlink_node(node)
    return node.data
  end

  each_node.find(&__to_matcher(val, &block)).tap do |node_to_delete|
    return unless node_to_delete
    __unlink_node(node_to_delete)
  end.data
end

#delete_all(val = nil, &block) ⇒ Object

Removes all matched data.data from the the list by passed block or value.

Returns:

Array of deleted nodes



157
158
159
160
161
162
 
# File 'lib/linked-list/list.rb', line 157

def delete_all(val = nil, &block)
  each_node.select(&__to_matcher(val, &block)).each do |node_to_delete|
    next unless node_to_delete
    __unlink_node(node_to_delete)
  end.map(&:data)
end

#each ⇒ Object

Iterates over nodes from top to bottom passing node data to the block if given. If no block given, returns Enumerator.

Returns:

Enumerator or yields data to the block stored in every node on the list.



226
227
228
229
 
# File 'lib/linked-list/list.rb', line 226

def each
  return to_enum(__callee__) unless block_given?
  __each { |node| yield(node.data) }
end

#each_node ⇒ Object

Iterates over nodes from top to bottom passing node(LinkedList::Node instance) to the block if given. If no block given, returns Enumerator.

Returns:

Enumerator or yields list nodes to the block



237
238
239
240
 
# File 'lib/linked-list/list.rb', line 237

def each_node
  return to_enum(__callee__) unless block_given?
  __each { |node| yield(node) }
end

#first ⇒ Object

Returns the first element of the list or nil.



18
19
20
 
# File 'lib/linked-list/list.rb', line 18

def first
  @head && @head.data
end

#insert(to_add, after: nil, before: nil) ⇒ Object

Inserts after or before first matched node.data from the the list by passed block or value.

Returns:

Inserted node data



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/linked-list/list.rb', line 77

def insert(to_add, after: nil, before: nil)
  if after && before || !after && !before
    raise ArgumentError, 'either :after or :before keys should be passed'
  end
  matcher = after || before
  matcher_proc = if matcher.is_a?(Proc)
                   __to_matcher(&matcher)
                 else
                   __to_matcher(matcher)
                 end
  node = each_node.find(&matcher_proc)
  return unless node
  new_node = after ? insert_after_node(to_add, node) : insert_before_node(to_add, node)
  new_node.data
end

#insert_after_node(data, node) ⇒ Object

Inserts data after first matched node.data.

Returns:

Inserted node



98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/linked-list/list.rb', line 98

def insert_after_node(data, node)
  Node(data).tap do |new_node|
    new_node.prev = node
    new_node.next = node.next
    if node.next
      node.next.prev = new_node
    else
      @tail = new_node
    end
    node.next = new_node
    @length += 1
  end
end

#insert_before_node(data, node) ⇒ Object

Inserts data before first matched node.data.

Returns:

Inserted node



117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/linked-list/list.rb', line 117

def insert_before_node(data, node)
  Node(data).tap do |new_node|
    new_node.next = node
    new_node.prev = node.prev
    if node.prev
      node.prev.next = new_node
    else
      @head = new_node
    end
    node.prev = new_node
    @length += 1
  end
end

#inspect ⇒ Object 



273
274
275
 
# File 'lib/linked-list/list.rb', line 273

def inspect
  sprintf('#<%s:%#x %s>', self.class, self.__id__, to_a.inspect)
end

#last ⇒ Object

Returns the last element of the list or nil.



24
25
26
 
# File 'lib/linked-list/list.rb', line 24

def last
  @tail && @tail.data
end

#pop ⇒ Object

Removes data from the end of the list.

Returns:

Data stored in the node or nil.



169
170
171
172
173
174
175
176
177
 
# File 'lib/linked-list/list.rb', line 169

def pop
  return nil unless @head

  tail = __pop
  @head = nil unless @tail

  @length -= 1
  tail.data
end

#push(node) ⇒ Object Also known as: <<

Pushes new nodes to the end of the list.

Parameters:

node

Any object, including Node objects.

Returns:

self of List object.



36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/linked-list/list.rb', line 36

def push(node)
  node = Node(node)
  @head ||= node

  if @tail
    @tail.next = node
    node.prev = @tail
  end

  @tail = node

  @length += 1
  self
end

#reverse ⇒ Object

Reverse list of nodes and returns new instance of the list.

Returns:

New List in reverse order.



199
200
201
 
# File 'lib/linked-list/list.rb', line 199

def reverse
  List(to_a).reverse!
end

#reverse! ⇒ Object

Reverses list of nodes in place.

Returns:

self in reverse order.



208
209
210
211
212
213
214
215
216
217
 
# File 'lib/linked-list/list.rb', line 208

def reverse!
  return self unless @head

  __each do |curr_node|
    curr_node.prev, curr_node.next = curr_node.next, curr_node.prev
  end
  @head, @tail = @tail, @head

  self
end

#reverse_each ⇒ Object

Iterates over nodes from bottom to top passing node data to the block if given. If no block given, returns Enumerator.

Returns:

Enumerator or yields data to the block stored in every node on the list.



250
251
252
253
 
# File 'lib/linked-list/list.rb', line 250

def reverse_each
  return to_enum(__callee__) unless block_given?
  __reverse_each { |node| yield(node.data) }
end

#reverse_each_node ⇒ Object

Iterates over nodes from bottom to top passing node(LinkedList::Node instance) to the block if given. If no block given, returns Enumerator.

Returns:

Enumerator or yields list nodes to the block



261
262
263
264
 
# File 'lib/linked-list/list.rb', line 261

def reverse_each_node
  return to_enum(__callee__) unless block_given?
  __reverse_each { |node| yield(node) }
end

#shift ⇒ Object

Removes data from the beginning of the list.

Returns:

Data stored in the node or nil.



184
185
186
187
188
189
190
191
192
 
# File 'lib/linked-list/list.rb', line 184

def shift
  return nil unless @head

  head = __shift
  @tail = nil unless @head

  @length -= 1
  head.data
end

#to_a ⇒ Object Also known as: to_ary

Converts list to array.



268
269
270
 
# File 'lib/linked-list/list.rb', line 268

def to_a
  each.to_a
end

#to_list ⇒ Object

Conversion function, see Conversions.List.

Returns:

self



282
283
284
 
# File 'lib/linked-list/list.rb', line 282

def to_list
  self
end

#unshift(node) ⇒ Object

Pushes new nodes on top of the list.

Parameters:

node

Any object, including Node objects.

Returns:

self of List object.



60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/linked-list/list.rb', line 60

def unshift(node)
  node = Node(node)
  @tail ||= node

  node.next = @head
  @head.prev = node if @head
  @head = node

  @length += 1
  self
end