class LinkedList::List
Attributes
Public Class Methods
# File lib/linked-list/list.rb, line 9 def initialize @head = nil @tail = nil @length = 0 end
Public Instance Methods
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
# File lib/linked-list/list.rb, line 138 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
Removes all matched data.data from the the list by passed block or value.
Returns:¶ ↑
Array of deleted nodes
# File lib/linked-list/list.rb, line 156 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
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.
# File lib/linked-list/list.rb, line 225 def each return to_enum(__callee__) unless block_given? __each { |node| yield(node.data) } end
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
# File lib/linked-list/list.rb, line 236 def each_node return to_enum(__callee__) unless block_given? __each { |node| yield(node) } end
Returns the first element of the list or nil.
# File lib/linked-list/list.rb, line 17 def first @head && @head.data end
Inserts after or before first matched node.data from the the list by passed block or value.
Returns:¶ ↑
Inserted node data
# File lib/linked-list/list.rb, line 76 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
Inserts data after first matched node.data.
Returns:¶ ↑
Inserted node
# File lib/linked-list/list.rb, line 97 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
Inserts data before first matched node.data.
Returns:¶ ↑
Inserted node
# File lib/linked-list/list.rb, line 116 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
# File lib/linked-list/list.rb, line 272 def inspect sprintf('#<%s:%#x %s>', self.class, self.__id__, to_a.inspect) end
Returns the last element of the list or nil.
# File lib/linked-list/list.rb, line 23 def last @tail && @tail.data end
Pushes new nodes to the end of the list.
Parameters:¶ ↑
- node
-
Any object, including
Node
objects.
Returns:¶ ↑
self
of List
object.
# File lib/linked-list/list.rb, line 35 def push(node) node = Node(node) @head ||= node if @tail @tail.next = node node.prev = @tail end @tail = node @length += 1 self end
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.
# File lib/linked-list/list.rb, line 249 def reverse_each return to_enum(__callee__) unless block_given? __reverse_each { |node| yield(node.data) } end
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
# File lib/linked-list/list.rb, line 260 def reverse_each_node return to_enum(__callee__) unless block_given? __reverse_each { |node| yield(node) } end
Converts list to array.
# File lib/linked-list/list.rb, line 267 def to_a each.to_a end
Private Instance Methods
# File lib/linked-list/list.rb, line 329 def __each curr_node = @head while(curr_node) yield curr_node curr_node = curr_node.next end end
# File lib/linked-list/list.rb, line 314 def __pop tail = @tail @tail = @tail.prev @tail.next = nil if @tail tail end
# File lib/linked-list/list.rb, line 321 def __reverse_each curr_node = @tail while(curr_node) yield curr_node curr_node = curr_node.prev end end
# File lib/linked-list/list.rb, line 307 def __shift head = @head @head = @head.next @head.prev = nil if @head head end
# File lib/linked-list/list.rb, line 301 def __to_matcher(val = nil, &block) raise ArgumentError, 'either value or block should be passed' if val && block_given? block = ->(e) { e == val } unless block_given? ->(node) { block.call(node.data) } end
# File lib/linked-list/list.rb, line 287 def __unlink_node(node) @head = node.next if node.prev.nil? @tail = node.prev if node.next.nil? if node.prev.nil? node.next.prev = nil if node.next elsif node.next.nil? node.prev.next = nil if node.prev else node.prev.next, node.next.prev = node.next, node.prev end @length -= 1 end