Class: Lista

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/gematdd/lista/lista.rb

Overview

Implementación de una Lista Doblemente Enlazada

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(node = nil) ⇒ Lista

Returns a new instance of Lista



10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/gematdd/lista/lista.rb', line 10

def initialize(node = nil)
  @head = node
  @tail = node
  @size = 0

  while node
    @size += 1
    @tail = node
    node = node.next
    node.prev = @tail unless node.nil?
  end
end

Instance Attribute Details

#head ⇒ Object (readonly)

Returns the value of attribute head



8
9
10
 
# File 'lib/gematdd/lista/lista.rb', line 8

def head
  @head
end

#size ⇒ Object (readonly)

Returns the value of attribute size



8
9
10
 
# File 'lib/gematdd/lista/lista.rb', line 8

def size
  @size
end

#tail ⇒ Object (readonly)

Returns the value of attribute tail



8
9
10
 
# File 'lib/gematdd/lista/lista.rb', line 8

def tail
  @tail
end

Instance Method Details

#clear ⇒ Object

Limpia la lista completamente



29
30
31
32
 
# File 'lib/gematdd/lista/lista.rb', line 29

def clear
  @head = @tail = nil
  @size = 0
end

#each ⇒ Object

Recorre la lista doblemente enlazada de principio a fin



121
122
123
124
125
126
127
 
# File 'lib/gematdd/lista/lista.rb', line 121

def each
  current = @head
  while current
    yield current.value
    current = current.next
  end
end

#empty? ⇒ Boolean

Comprueba si la lista está vacía

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/gematdd/lista/lista.rb', line 24

def empty?
  @size.zero?
end

#erase(node) ⇒ Object

Elimina el nodo especificado



105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/gematdd/lista/lista.rb', line 105

def erase(node)
  if @size == 1
    @head = @tail = nil
  else
    node.next.prev = node.prev
    node.prev.next = node.next
  end

  node.next = nil
  node.prev = nil

  @size -= 1
  node
end

#insert(node, value) ⇒ Object

Inserta un valor después del nodo especificado



95
96
97
98
99
100
101
102
 
# File 'lib/gematdd/lista/lista.rb', line 95

def insert(node, value)
  inserted = Node.new(value, node.next, node)
  node.next.prev = inserted
  node.next = inserted

  @size += 1
  inserted
end

#pop_back ⇒ Object

Elimina elementos en la lista desde detrás



79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/gematdd/lista/lista.rb', line 79

def pop_back
  node = @tail
  if @size == 1
    node = @tail
    @head = @tail = nil
  else
    @tail.prev.next = nil
    @tail = @tail.prev
    node.prev = nil
  end

  @size -= 1
  node
end

#pop_front ⇒ Object

Elimina elementos en la lista desde el frente



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/gematdd/lista/lista.rb', line 49

def pop_front
  node = @head

  if @size == 1
    node = @head
    @head = @tail = nil
  else
    @head.next.prev = nil
    @head = @head.next
    node.next = nil
  end

  @size -= 1
  node
end

#push_back(value) ⇒ Object

Inserta elementos en la lista desde detrás



66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/gematdd/lista/lista.rb', line 66

def push_back(value)
  node = Node.new(value, nil, @tail)
  if empty?
    @head = @tail = node
  else
    @tail.next = node
    @tail = node
  end

  @size += 1
end

#push_front(value) ⇒ Object

Inserta elementos en la lista desde el frente



35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/gematdd/lista/lista.rb', line 35

def push_front(value)
  node = Node.new(value, @head, nil)

  if empty?
    @head = @tail = node
  else
    @head.prev = node
    @head = node
  end

  @size += 1
end

#sort! ⇒ Object

Ordena la lista (sobre ella misma)



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/gematdd/lista/lista.rb', line 130

def sort!
  swapped = true

  while swapped
    node = @head
    swapped = false
    while node && !node.next.nil?
      if node.next.value < node.value
        node.value, node.next.value = node.next.value, node.value
        swapped = true
      end
      node = node.next
    end
    node = @head if swapped
  end
end