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