-
Notifications
You must be signed in to change notification settings - Fork 1
/
linkedlist.cpp
233 lines (210 loc) · 6.71 KB
/
linkedlist.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#include "object.h"
#include "tdalist.h"
#include "dllnode.h"
#include "linkedlist.h"
#include <iostream>
#include <string>
#include <sstream>
using std::cout;
using std::endl;
using std::string;
using std::stringstream;
// Para tener la definición del NULL sin declarar más identificadores
// innecesarios
#include <stddef.h>
// Constructor por defecto de LinkedList
LinkedList::LinkedList(){
head = NULL;
}
// Super Destructor de LinkedList, nótese que llamará al destructor
// de la clase DLLNode, que liberará todos los nodos siguientes...
LinkedList::~LinkedList(){
if (head)
delete head;
}
/*
* Inserción en la lista
* En esta operación se consideran cuatro casos generales de inserción:
* (A) La Lista está Vacía
* (B) Se desea Insertar antes de head (pos = 0)
* (C) Se desea Insertar en Medio de la Lista
* (D) Se desea Insertar al Final (pos = ssize)
*/
bool LinkedList::insert(Object* data, int pos) {
// Si se desa meter en una posición inválida
if (pos < 0 || pos > ssize)
return false; // Fracaso en esta Operación
// Creación del Nodo que insertaremos en la lista
DLLNode* neo = new DLLNode(data);
if (!head) // La lista está vacía
head = neo;
else { // La Lista tiene elementos
if (pos == 0){ // Desea insertar al principio de la lista
// Enlace de neo a la lista
head->setPrev(neo);
neo->setNext(head);
// Actualizar la cabeza
head = neo;
}else if (pos > 0 && pos < ssize){ // Desea Insertar en medio
DLLNode* tmp = head;
// Recorrer hasta la posición anterior a la que deseamos insertar
for (int i=1; i<pos; i++)
tmp = tmp->getNext();
// Enlazar el Nodo neo
neo->setPrev(tmp);
neo->setNext(tmp->getNext());
tmp->getNext()->setPrev(neo);
tmp->setNext(neo);
}else { // Desea insertar al final
DLLNode* tmp = head;
// Recorrer la Lista hasta el final
for (int i=1; i<pos; i++)
tmp = tmp->getNext();
// Enlazar el Nodo neo
tmp->setNext(neo);
neo->setPrev(tmp);
}
}
// Incremento del tamaño
ssize++;
// Éxito en la operación
return true;
}
/*
* Búsqueda del índice (posición) de un objeto
* Para que esta operación tenga éxito es necesario que los objetos que sean
* insertados en la lista tengan bien definido el método equals, pues es este
* método el que determinará la igualdad de un objeto con otro.
*/
int LinkedList::indexOf(Object* other)const {
DLLNode* tmp = head;
for (int i=0; i < ssize; i++){
// Compara cada uno de los elementos con el parámetro
if (tmp->getData()->equals(other))
return i;
tmp = tmp->getNext();
}
// En el caso de no encontrarlo
return -1;
}
// Consigue el elemento index de la lista, si index es una posición válida
Object* LinkedList::get(unsigned index)const {
if (index < 0 || index >= ssize)
return NULL;
DLLNode* tmp = head;
for (int i=0; i < index; i++)
tmp = tmp->getNext();
return tmp->getData();
}
/*
* Borra un elemento de la lista, dada la posición del mismo. Se consideran
* tres casos:
* (A) El Elemento es la Cabeza
* (B) El Elemento es el Último
* (C) El Elemento está en Medio
* Es importante recalcar que para borrar un elemento es necesario primero
* desenlazarlo de la lista y luego liberar su memoria, pues en caso contrario
* liberaríamos todos los elementos siguiente a este elemento.
*/
Object* LinkedList::remove(unsigned pos) {
Object* ret = NULL;
// Si es una posición Inválida
if (pos < 0 || pos >= ssize)
return NULL; // Indicar fracaso en la operación
DLLNode* tmp;
if (pos == 0){
ret = head->getData();
head->setData(NULL);
// Desea Borrar la Cabeza
// Desenlazar
tmp = head->getNext();
tmp->setPrev(NULL);
head->setNext(NULL);
// Liberar Memoria
delete head;
// Actualizar head
head = tmp;
}else if (pos == ssize - 1){
// Desea Borrar el último
// Recorrer hasta el final
tmp = head;
for (int i=1; i<pos; i++)
tmp = tmp->getNext();
// Desenlazar
DLLNode* toErase = tmp->getNext();
ret = toErase->getData();
toErase->setData(NULL);
tmp->setNext(NULL);
toErase->setPrev(NULL);
// Liberar Memoria
delete toErase;
}else { // Desea Borrar de enmedio
// Recorrer hasta el nodo anterior al que se desea borrar
tmp = head;
for (int i=1; i<pos; i++)
tmp = tmp->getNext();
// Desenlazar
DLLNode* toErase = tmp->getNext();
ret = toErase->getData();
toErase->setData(NULL);
tmp->setNext(toErase->getNext());
toErase->getNext()->setPrev(tmp);
toErase->setNext(NULL);
toErase->setPrev(NULL);
// Liberar Memoria
delete toErase;
}
ssize--; // Disminuir Tamaño
return ret; // Indicar Éxito
}
// Retorna el anterior a la posición pos
// Implementado de la manera más sencilla, pues podría haberse usado
// DLLNode*
int LinkedList::prev(int pos) const {
return pos - 1;
}
// Retorna el siguiente a la posición pos
// Implementado de la manera más sencilla, pues podría haberse usado
// DLLNode*
int LinkedList::next(int pos) const {
return pos + 1;
}
// Elimina todos los elementos de la lista, coloca ssize en cero, y la cabeza
// en NULL, o sea que hace un poco más que el destructor.
void LinkedList::clear() {
if (head)
delete head;
head = NULL;
ssize = 0;
}
// Retorna el primer elemento de la lista, si es que hay alguno
Object* LinkedList::first()const {
if (head)
return head->getData();
return NULL;
}
// Retorna el último elemento de la lista, si es que hay alguno
Object* LinkedList::last()const {
if (!head)
return NULL;
DLLNode* tmp = head;
for (int i=0; i < ssize-1; i++)
{
//cout << "Vuelta dentro de last(): " << i << endl;
tmp = tmp->getNext();
}
return tmp->getData();
}
// Imprime cada uno de los elementos que hay en la lista, llamando al método
// print de cada nodo.
void LinkedList::print()const {
DLLNode* tmp = head;
for (int i=0; i < ssize-1; i++){
tmp->print();
tmp = tmp->getNext();
}
}
// Retorna si la lista está llena, como nunca es así, retorna false siempre.
bool LinkedList::isFull()const {
return false;
}