class DDQL::LinkedList

Attributes

head[R]
size[R]

Public Class Methods

new(head=nil) click to toggle source
# 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

Public Instance Methods

<<(value)
Alias for: append
[](index)
Alias for: at
append(value) click to toggle source
# 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
Also aliased as: <<
append_after(target, value) click to toggle source

Insert the value after the target

@return [Node|NilClass] nil if target is not found, otherwise the inserted node for value

# 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
Also aliased as: insert
at(index) click to toggle source
# 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
Also aliased as: []
delete(value) click to toggle source
# 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!() click to toggle source
# 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?() click to toggle source
# File lib/ddql/linked_list.rb, line 128
def doubly_linked?
  @doubly_linked
end
each() { |value| ... } click to toggle source
# 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?() click to toggle source
# File lib/ddql/linked_list.rb, line 141
def empty?
  @size == 0
end
find(value=nil) { |node| ... } click to toggle source
# 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) click to toggle source
# 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) { |node| ... } click to toggle source
# 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() click to toggle source
# 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
Also aliased as: tail
insert(target, value)
Alias for: append_after
peek() click to toggle source
# File lib/ddql/linked_list.rb, line 192
def peek
  return nil unless @head
  @head.value
end
poll() click to toggle source
# 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) click to toggle source
replace!(from:, to:, with:) click to toggle source

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

@return self

# 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!() click to toggle source
# File lib/ddql/linked_list.rb, line 257
def singly_linked!
  each_node do |node|
    node.previous = nil
  end
  @doubly_linked = false
  self
end
tail()
Alias for: find_tail

Private Instance Methods

each_node() { |node| ... } click to toggle source
# File lib/ddql/linked_list.rb, line 266
def each_node
  raise 'requires a block' unless block_given?
  node = @head
  while node
    yield node
    node = node.next
  end
end