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 



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.

Returns:

Deleted node



136
137
138
139
140
141
 
# File 'lib/linked-list/list.rb', line 136

def delete(val = nil, &block)
  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



148
149
150
151
152
153
 
# File 'lib/linked-list/list.rb', line 148

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.



217
218
219
220
 
# File 'lib/linked-list/list.rb', line 217

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



228
229
230
231
 
# File 'lib/linked-list/list.rb', line 228

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 passed node.

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 passed node.

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 



264
265
266
 
# File 'lib/linked-list/list.rb', line 264

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.



160
161
162
163
164
165
166
167
168
 
# File 'lib/linked-list/list.rb', line 160

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.



190
191
192
 
# File 'lib/linked-list/list.rb', line 190

def reverse
  List(to_a).reverse!
end

#reverse! ⇒ Object

Reverses list of nodes in place.

Returns:

self in reverse order.



199
200
201
202
203
204
205
206
207
208
 
# File 'lib/linked-list/list.rb', line 199

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.



241
242
243
244
 
# File 'lib/linked-list/list.rb', line 241

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



252
253
254
255
 
# File 'lib/linked-list/list.rb', line 252

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.



175
176
177
178
179
180
181
182
183
 
# File 'lib/linked-list/list.rb', line 175

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.



259
260
261
 
# File 'lib/linked-list/list.rb', line 259

def to_a
  each.to_a
end

#to_list ⇒ Object

Conversion function, see Conversions.List.

Returns:

self



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

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