class FibonacciHeap::CircularDoublyLinkedList

A Circular Doubly Linked List data structure.

An unsorted, linear, circular list with a sentinel to simplify boundary conditions.

Attributes

sentinel[RW]

Return the special “sentinel” or Nil node for this list.

Public Class Methods

new() click to toggle source

Return a new, empty list.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 23
def initialize
  @sentinel = Sentinel.new
end

Public Instance Methods

concat(list) click to toggle source

Combine this list with another, destroying the given list.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 65
def concat(list)
  list.sentinel.prev.next = sentinel.next
  sentinel.next.prev = list.sentinel.prev
  sentinel.next = list.sentinel.next
  list.sentinel.next.prev = sentinel
end
delete(x) click to toggle source

Remove a given node from the list.

The node must already be in the list.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 59
def delete(x)
  x.prev.next = x.next
  x.next.prev = x.prev
end
each() { |current| ... } click to toggle source

Yield each element of this list.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 73
def each
  x = sentinel.next

  while x != sentinel
    current = x
    x = x.next

    yield current
  end
end
empty?() click to toggle source

Return whether or not the list is empty.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 42
def empty?
  sentinel.next == sentinel
end
head() click to toggle source

Return the first element of the list or nil if it is empty.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 28
def head
  return if empty?

  sentinel.next
end
insert(x) click to toggle source

Insert a given node into the list.

New nodes will be placed at the head of the list.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 49
def insert(x)
  x.next = sentinel.next
  sentinel.next.prev = x
  sentinel.next = x
  x.prev = sentinel
end
tail() click to toggle source

Return the last element of the list or nil if it is empty.

# File lib/fibonacci_heap/circular_doubly_linked_list.rb, line 35
def tail
  return if empty?

  sentinel.prev
end