Buscar: Explicaciones sobre el código de ArrayList y LinkedList
Publicado por Juan José (20 intervenciones) el 07/04/2019 10:34:25
Buenas, necesito ayuda para entender cómo funciona aquí los ArrayList y LinkedList ya que me está costando un poco entenderlo. Por ejemplo:
¿Por qué ArrayList necesta la interfaz iterator?
ArrayList
LinkedList
¿Por qué ArrayList necesta la interfaz iterator?
ArrayList
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
package org.mp.sesion03;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ArrayList<E> extends AbstractList<E> {
private static final int CAPACIDAD_INICIAL = 16;private E[] data = (E[]) new Object[CAPACIDAD_INICIAL];
public ArrayList() {
data = (E[]) new Object[0];
}public ArrayList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}public void add(int index, E e) {
ensureCapacity();
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Indice: " + index + ", Tamaño: " + size);
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}data[index] = e;
size++;
} /**
* Este metodo se utilizara para aumentar el tañano del objeto ArrayList en caso
* de llegar a completarse.
*/private void ensureCapacity() {
E[] a = (E[]) new Object[(data.length * 2) + 1];
for (int i = 0; i < data.length; i++) {
a[i] = data[i];
} data = a; }public void clear() {
size = 0; } /*
* (non-Javadoc) Este metodo recorre toda nuestra ArrayList comprovando si se
* encuentra el valor indicado en la misma
*
* @see org.mp.sesion03.List#contains(java.lang.Object)
*/public boolean contains(E e) {
for (int i = 1; i <= data.length; i++) {
if (null == data[i]) {
return false;
}if (e == data[i]) {
return true;
} }return false;
}public E get(int index) {
checkIndex(index);
return data[index];
} /**
* Comprueba que el valor asignado para nuestro array es valido
*
* @param index
*/private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Indice: " + index + ", Tamaño: " + size);
if (index == -1) {
throw new IndexOutOfBoundsException("" + index);
} } /*
* (non-Javadoc) Devuelve la ubicacion de la primera vez que aparece dentro de
* nuestro arraylist del valor indicado.
*
* @see org.mp.sesion03.List#indexOf(java.lang.Object)
*/public int indexOf(E e) {
for (int i = 0; i < this.size(); i++) {
if (e.equals(data[i])) {
return i;
} } return -1; } /*
* (non-Javadoc) Devuelve la ubicacion de la primera vez que aparece dentro de
* nuestro arraylist del valor indicado.
*
* @see org.mp.sesion03.List#lastIndexOf(java.lang.Object)
*/public int lastIndexOf(E e) {
int a = -1;
for (int i = 0; i < this.size(); i++) {
if (e.equals(data[i])) {
a = i; } }return a;
}public E remove(int index) {
checkIndex(index);
E devolver = data[index];
int i = size;while (index < i) {
data[index] = data[index + 1];
i--;
}size--;
return devolver;
}public E set(int index, E e) {
checkIndex(index);
E antiguo = data[index];
data[index] = e;
return antiguo;
}public String toString() {
StringBuilder resultado = new StringBuilder("[");
for (int i = 0; i < size; i++) {
resultado.append(data[i]);
if (i < size - 1)
resultado.append(", ");
}return resultado.toString() + "]";
}public void trimToSize() {
}public Iterator<E> iterator() {
return new ArrayListIterator();
}private class ArrayListIterator implements Iterator<E> {
private int current;
@Override
public boolean hasNext() {
if (current >= 0 && current < size)
return true;
return false;
// throw new NoSuchElementException("No hay más elementos en la lista");
}@Override
public E next() {
if (current == size) {
throw new NoSuchElementException("No hay más elementos en la lista");
}E e = data[current];
current++;
return e;
}@Override
public void remove() {
ArrayList.this.remove(current);
} }}LinkedList
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
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
package org.mp.sesion04;
import java.util.Iterator;
import java.util.NoSuchElementException;
import org.mp.sesion03.AbstractList;
public class LinkedList<E> extends AbstractList<E> {
// Propiedades
// Estas serán nodos.
private Node<E> tail;
Node<E> head;
/** Crea una lista enlazada por defecto */public LinkedList() {
} /** Crea una lista enlazada a partir de un array de objetos */ // Para crear
public LinkedList(E[] objects) {
super(objects);
} /** Devuelve el primer elemento de la lista */public E getFirst() {
if (size == 0) {
return null;
} else {
return head.element; } } /** Devuelve el último elemento de la lista */public E getLast() {
if (size == 0) {
return null;
} return tail.element; } /** Añade un elemento a la cabeza de la lista */public void addFirst(E e) {
Node<E> nuevoNodo = new Node<E>(e); // Crea un nodo
nuevoNodo.next = head; // enlaza el nuevoNodo con la cabeza
head = nuevoNodo; // la cabeza apunta al nuevoNodo
size++; // Incrementa el tamaño de la lista
if (tail == null) // si la lista está vacía
tail = head; // el nuevo nodo es el único en la lista
} /** Añade un elemento al final de la lista */public void addLast(E e) {
Node<E> nuevoNodo = new Node<E>(e); // Crea un nodo para e e
if (tail == null) {
head = tail = nuevoNodo; // El nodo nuevo es el único de la lista
} else {
tail.next = nuevoNodo; // enlaza el nuevo nodo con el último nodo
tail = tail.next; // la cola apunta ahora al último nodo
}size++; // Incrementa el tamaño
} /**
* Añade el elemento e en la posición index. La posición del elemento head es 0
*/public void add(int index, E e) {
if (index <= 0) { // Inserta al principio
addFirst(e);
} else if (index >= size) { // Inserta al final
addLast(e);
} else { // Inserta en medio
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next; // Situo current
}Node<E> temp = current.next; // Situo temp
current.next = new Node<E>(e); // Inserto elnuevo nodo
(current.next).next = temp;
size++; // incrementa el tamaño
} } /**
* Elimina el primer elemento de la lista y devuelve el elemento eliminado.
*/public E removeFirst() {
if (size == 0) { // Nada que borrar
return null;
} else {
Node<E> temp = head; // conserva el primer nodo temporalmente
head = head.next; // mueve head para apuntar al siguiente nodo
size--; // disminuye el tamaño
if (head == null) {
tail = null; // la lista se pone vacía
}return temp.element; // devuelve el elemento borrado
} } /**
* Elimina el último elemento de la lista y devuelve el elemento eliminado.
*/public E removeLast() {
if (size == 0) { // Nada que eliminar
return null;
} else if (size == 1) { // solo un elemento en la lista
Node<E> temp = head;
head = tail = null; // la lista la hacemos vacía
size = 0; return temp.element;} else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}Node<E> temp = tail;
tail = current;tail.next = null;
size--;
return temp.element; } } /**
* Elimina el elemento en la posición index. Devuelve el elemento que fué
* eliminado de la lista.
*/public E remove(int index) {
if (index < 0 || index >= size) { // Fuera de rango
return null;
} else if (index == 0) { // Elimina el primero
return removeFirst();
} else if (index == size - 1) { // Elimina el último
return removeLast();
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element; } } @Override /** Sobre-escribe toString() */public String toString() {
StringBuilder result = new StringBuilder("[");
if (size == 0)
result.append("]");
else {Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", ");
} else {
result.append("]");
} } }return result.toString();
} /** Elimina todos los elementos de la lista */public void clear() {
size = 0; } /** Devuelve true si la lista contiene el elemento e */public boolean contains(E e) {
Node<E> resultado = new Node<E>(e);
for (int i = 0; i < size; i++) {
if (e == resultado.element)
return true;
}return false;
} /** Devuelve el elemento en la posición index especificada */public E get(int index) {
if (index < 0 || index > size) {
return null;
} else {
Node<E> aux = head;
for (int i = 0; i < size; i++) {
if (i == index) {
aux = head;break;
} } return aux.element; } } /**
* Devuelve el índice de la primera ocurrencia del elemento en la lista.
* Devuelve -1 si no está
*/public int indexOf(E e) {
Node<E> nuevo = head;
for (int i = 0; i < size; i++) {
if (nuevo.element == e)
return i;
else
nuevo = nuevo.next;
} return -1; } /**
* Devuelve el índice de la última ocurrencia del elemento en la lista. Devuelve
* -1 si no está.
*/public int lastIndexOf(E e) {
Node<E> current = head;
int posicion = -1;
for (int i = 0; i < size; i++) {
if (current.element == e)
posicion = i;current = current.next;
}return posicion;
} /**
* Sustituye el elemento de la posición especificada en la lista por el elemento
* especificado.
*/public E set(int index, E e) {
if (index < 0 || index >= size) {
return null;
}E resultado = remove(index);
// Borras el elemento que esta en index y lo guardas para devolverlo
add(index, e);
// en index, que ahora esta vacio, metes el elemento e
return resultado;
}@Override
/** Sobre-escribe el método iterator() definido en Iterable */public Iterator<E> iterator() {
return new LinkedListIterator();
// Devuelve una instancia de LinkedListIterator
} /** Esta clase implementa la interface Iterator */private class LinkedListIterator implements Iterator<E> {
private Node<E> current = head;
@Override
public boolean hasNext() {
return (current != null);
}@Override
public E next() {
if (current == null) {
throw new NoSuchElementException("No hay más elementos en la lista");
}E e = current.element;
current = current.next;
return e;
}@Override
public void remove() {
if (size != 0)
LinkedList.this.remove(current.element);
} }// Esta clase solo se usa en LinkedList, por eso es private.
// Esta clase no necesita acceder a ningún miembro de instancia de LinkedList,
// por lo que se define estática.
private static class Node<E> {
// Propiedades
E element;
Node<E> next;
public Node(E element) {
this.element = element;
} }}Valora esta pregunta
0
