Class: DLLModule::DLL

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/food/dll.rb

Overview

Class Doubly Linked List

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil) ⇒ DLL

Constructor of DLL

Parameters:

  • value (defaults to: nil) —

    of Node

  • head (Node) —

    Head of the DLL

  • tail (Node) —

    Tail of the DLL

  • size (int) —

    size of the doubly linked list



23
24
25
26
27
28
29
 
# File 'lib/food/dll.rb', line 23

def initialize (value = nil)
  node = Node.new(value)
  
  @head = node
  @tail = node
  @size = (node.nil?) ? 0 : 1
end

Instance Attribute Details

#size ⇒ Object (readonly) 



16
17
18
 
# File 'lib/food/dll.rb', line 16

def size
  @size
end

Instance Method Details

#delete(value) ⇒ Object

Delete an specific element in DLL head



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/food/dll.rb', line 88

def delete (value)
  current_node = @head
  
  while !current_node.nil?
    if (current_node.value == value)
      if (@size == 1) 
        @head = nil
        @tail = nil
        current_node = nil
      else
        if current_node != @head
          (current_node.prev).next = current_node.next
        end
        if current_node != @tail
          (current_node.next).prev = current_node.prev
        end
        current_node = nil
      end
      @size -= 1
    else
      current_node = current_node.next
    end
  end
end

#each ⇒ Object

Essential method for Enumerable



131
132
133
134
135
136
137
138
 
# File 'lib/food/dll.rb', line 131

def each
  current_node = @head
  
  while !current_node.nil? 
    yield current_node.value
    current_node = current_node.next
  end
end

#empty? ⇒ Boolean

Return if DLL is empty

Returns:

  • (Boolean) 


126
127
128
 
# File 'lib/food/dll.rb', line 126

def empty?
  return size == 0
end

#extract_head ⇒ Node

Extract element in DLL head

Returns:

  • (Node) —

    value of the node that was in the head



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/food/dll.rb', line 53

def extract_head
  if @head.nil?
    return nil
  else
    @size -= 1
    
    node_to_return = @head
    
    @head = @head.next
    @head.prev = nil
    
    node_to_return.next = nil
    return node_to_return.value
  end
end

#extract_tail ⇒ Node

Extract element in DLL tail

Returns:

  • (Node) —

    value of the node that was in the tail



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/food/dll.rb', line 71

def extract_tail
  if @tail.nil?
    return nil
  else
    @size -= 1
    
    node_to_return = @tail
    
    @tail = @tail.prev
    @tail.next = nil
    
    node_to_return.prev = nil
    return node_to_return.value
  end
end

#get_head ⇒ head(#value)

Return head value

Returns:

  • (head(#value)) 


115
116
117
 
# File 'lib/food/dll.rb', line 115

def get_head
  return @head.value
end

#get_tail ⇒ tail(#value)

Return tail value

Returns:

  • (tail(#value)) 


121
122
123
 
# File 'lib/food/dll.rb', line 121

def get_tail
  return @tail.value
end

#insert_head(*value_array) ⇒ Object

Insert element in DLL head

Parameters:

  • *value_array (array) —

    set of values



35
36
37
38
39
40
 
# File 'lib/food/dll.rb', line 35

def insert_head (*value_array)
  value_array.each { |value|
    node = Node.new(value)
    insert_head_private(node);
  }
end

#insert_tail(*value_array) ⇒ Object

Insert element in DLL tail

Parameters:

  • *value_array (array) —

    set of values



44
45
46
47
48
49
 
# File 'lib/food/dll.rb', line 44

def insert_tail (*value_array)
  value_array.each { |value|
    node = Node.new(value)
    insert_tail_private(node);
  }
end