Class: FibonacciHeap::CircularDoublyLinkedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/fibonacci_heap/circular_doubly_linked_list.rb

Overview

A Circular Doubly Linked List data structure.

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

Defined Under Namespace

Classes: Sentinel

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ CircularDoublyLinkedList

Return a new, empty list.



23
24
25
 
# File 'lib/fibonacci_heap/circular_doubly_linked_list.rb', line 23

def initialize
  @sentinel = Sentinel.new
end

Instance Attribute Details

#sentinel ⇒ Object

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



20
21
22
 
# File 'lib/fibonacci_heap/circular_doubly_linked_list.rb', line 20

def sentinel
  @sentinel
end

Instance Method Details

#concat(list) ⇒ Object

Combine this list with another, destroying the given list.



65
66
67
68
69
70
 
# 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) ⇒ Object

Remove a given node from the list.

The node must already be in the list.



59
60
61
62
 
# 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 ⇒ Object

Yield each element of this list.



73
74
75
76
77
78
79
80
81
82
 
# 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? ⇒ Boolean

Return whether or not the list is empty.

Returns:

  • (Boolean) 


42
43
44
 
# File 'lib/fibonacci_heap/circular_doubly_linked_list.rb', line 42

def empty?
  sentinel.next == sentinel
end

#head ⇒ Object

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



28
29
30
31
32
 
# File 'lib/fibonacci_heap/circular_doubly_linked_list.rb', line 28

def head
  return if empty?

  sentinel.next
end

#insert(x) ⇒ Object

Insert a given node into the list.

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



49
50
51
52
53
54
 
# 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 ⇒ Object

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



35
36
37
38
39
 
# File 'lib/fibonacci_heap/circular_doubly_linked_list.rb', line 35

def tail
  return if empty?

  sentinel.prev
end