class LinkedList::List

Attributes

length[R]
size[R]

Public Class Methods

new() click to toggle source
# File lib/linked-list/list.rb, line 9
def initialize
  @head   = nil
  @tail   = nil
  @length = 0
end

Public Instance Methods

<<(node)
Alias for: push
delete(val = nil, &block) click to toggle source

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
delete_all(val = nil, &block) click to toggle source

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
each() { |data| ... } click to toggle source

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
each_node() { |node| ... } click to toggle source

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
first() click to toggle source

Returns the first element of the list or nil.

# File lib/linked-list/list.rb, line 17
def first
  @head && @head.data
end
insert(to_add, after: nil, before: nil) click to toggle source

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
insert_after_node(data, node) click to toggle source

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
insert_before_node(data, node) click to toggle source

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
inspect() click to toggle source
# File lib/linked-list/list.rb, line 272
def inspect
  sprintf('#<%s:%#x %s>', self.class, self.__id__, to_a.inspect)
end
last() click to toggle source

Returns the last element of the list or nil.

# File lib/linked-list/list.rb, line 23
def last
  @tail && @tail.data
end
pop() click to toggle source

Removes data from the end of the list.

Returns:

Data stored in the node or nil.

# File lib/linked-list/list.rb, line 168
def pop
  return nil unless @head

  tail = __pop
  @head = nil unless @tail

  @length -= 1
  tail.data
end
push(node) click to toggle source

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
Also aliased as: <<
reverse() click to toggle source

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

Returns:

New List in reverse order.

# File lib/linked-list/list.rb, line 198
def reverse
  List(to_a).reverse!
end
reverse!() click to toggle source

Reverses list of nodes in place.

Returns:

self in reverse order.

# File lib/linked-list/list.rb, line 207
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() { |data| ... } click to toggle source

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
reverse_each_node() { |node| ... } click to toggle source

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
shift() click to toggle source

Removes data from the beginning of the list.

Returns:

Data stored in the node or nil.

# File lib/linked-list/list.rb, line 183
def shift
  return nil unless @head

  head = __shift
  @tail = nil unless @head

  @length -= 1
  head.data
end
to_a() click to toggle source

Converts list to array.

# File lib/linked-list/list.rb, line 267
def to_a
  each.to_a
end
Also aliased as: to_ary
to_ary()
Alias for: to_a
to_list() click to toggle source

Conversion function, see Conversions.List.

Returns:

self

# File lib/linked-list/list.rb, line 281
def to_list
  self
end
unshift(node) click to toggle source

Pushes new nodes on top of the list.

Parameters:

node

Any object, including Node objects.

Returns:

self of List object.

# File lib/linked-list/list.rb, line 59
def unshift(node)
  node = Node(node)
  @tail ||= node

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

  @length += 1
  self
end

Private Instance Methods

__each() { |curr_node| ... } click to toggle source
# 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
__pop() click to toggle source
# File lib/linked-list/list.rb, line 314
def __pop
  tail = @tail
  @tail = @tail.prev
  @tail.next = nil if @tail
  tail
end
__reverse_each() { |curr_node| ... } click to toggle source
# 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
__shift() click to toggle source
# File lib/linked-list/list.rb, line 307
def __shift
  head = @head
  @head = @head.next
  @head.prev = nil if @head
  head
end
__to_matcher(val = nil, &block) click to toggle source
# 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