Programación en Java: Tipos y Uso de Listas, Pilas y Colas
Después de un tiempo sin actualizar, lo siento :’(, hablaremos de los tipos de listas que se usan en Java, así como su modo de uso y variantes como por ejemplo las pilas (LIFO) y colas (FIFO).
Normalmente hemos usado tablas de datos, llamados Arrays, como forma de almacenar nuestras instancias con una serie de limitaciones, como tener un número fijo de elementos declarados, o tener que reordenar toda la lista cuando se quiere eliminar o insertar un objeto en la tabla.
En lenguajes como C, no ofrece librerías, por lo que la solución consiste en el uso de arrays dinámicos y listas creadas a partir de estructuras que hacen referencia unas a otras con nodos (punteros). En C++ si tenemos a nuestra disposición una serie de librerías que nos permiten hacer esto automáticamente.
Las librerías de Java nos proveen unas clases incluidas en el paquete java.util a través de las cuales realizaremos la tarea correspondiente.
Clases:
- ArrayList: Clase que proporciona los métodos necesarios para el uso de listas basadas en arrays dinámicos. Al tratarse de un array, permiten el acceso aleatorio a los elementos, al contrario que otros tipos de listas secuenciales.
- LinkedList: Clase que proporciona los métodos necesarios para el uso de listas basadas en nodos enlazados entre sí. Debido a esta propiedad, solo están indicadas para colas FIFO y pilas LIFO, ya que no permiten acceder directamente a un elemento, sino que éste debe ser buscado siguiendo los distintos nodos de la lista.
- Vector: Clase en desuso, que se mantiene por compatibilidades con el código antiguo. Al contrario que ArrayList, son thread-safe.
- Collections: Clase que nos provee una gran cantidad de métodos para interactuar con listas.
Interfaces:
- Collection: Colecciones, son la interfaz básica a partir de la cual heredan el resto de interfaces basadas en listas. Normalmente optaremos por las siguientes interfaces, más avanzadas.
- List: Las listas suelen ser la opción más común, ofrecen acceso a los métodos básicos para el manejo de listas.
- Queue: Colas, ofrece acceso a los métodos para el manejo de colas FIFO, First In First Out, es decir el primero en entrar es el primero en salir, obteniendo siempre el objeto de la cabecera e insertando por el final de la cola. Solo LinkedList.
- Deque: Esta interfaz ha sido introducida con Java 1.6, ofrece acceso a los métodos básicos para el manejo de colas heredado de Queue y pilas, LIFO, Last In First Out, es decir el último en entrar es el primero en salir, obteniendo e insertando siempre el objeto al final de la lista. Solo LinkedList.
- Stack: Esta interfaz de pilas se encuentra actualmente en desuso al igual que ocurre con la clase Vector.
- Iterator: Esta interfaz proporciona accesos a una serie de métodos que nos permitirán recorrer las listas mediante iteración en lugar de enumeración.
Para los ejemplos utilizaremos objetos del tipo Persona. Como observamos, las clase Persona implementa la interfaz Cloneable y un método llamado clone, que nos permitirá duplicar el objeto, ya que en las listas se guardan referencias, por lo que puede darse el caso de que un mismo objeto exista en varias listas simultaneamente. También incluiremos la interfaz Comparable.
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 | /** * * @author Francisco Javier Guerrero <www.desarrollador-web.com> */ public class Persona implements Cloneable, Comparable { private String nombre; private String apellidos; public Persona(String nombre, String apellidos) { setNombre(nombre); setApellidos(apellidos); } public String getApellidos() { return apellidos; } public void setApellidos(String apellidos) { this.apellidos = apellidos; } public String getNombre() { return nombre; } public void setNombre(String nombre) { this.nombre = nombre; } @Override protected Object clone() throws CloneNotSupportedException { return super.clone(); } @Override public String toString() { return "Persona: Nombre[" + getNombre() + "] Apellidos [" + getApellidos() + "]"; } public int compareTo(Object o) { Persona p = (Persona) o; int valor = getNombre().compareTo(p.getNombre()); if (valor == 0) { valor = getApellidos().compareTo(p.getApellidos()); } return valor; } } |
Ejemplo 1:
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 | import java.util.List; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.logging.Level; import java.util.logging.Logger; /** * * @author Francisco Javier Guerrero <www.desarrollador-web.com> */ public class EjemploListas { public EjemploListas() { try { inicio(); } catch (CloneNotSupportedException ex) { Logger.getLogger(EjemploListas.class.getName()).log(Level.SEVERE, null, ex); } } public static void main(String[] args) { new EjemploListas(); } public void inicio() throws CloneNotSupportedException { System.out.println("Inicio de la aplicación.\n"); //Declaración de las listas List dinamica = new ArrayList(); List enlazada = new LinkedList(); /* * Se inicializarán las listas con objetos del tipo Persona, al no hacer * uso de clone, veremos un ejemplo de como el objeto de una lista está * referenciada en la otra. */ for (int i = 0; i < 5; i++) { Persona persona = new Persona("Nombre " + i, "Apellidos" + i); //Añadimos el objeto dinamica.add(persona); enlazada.add(persona); } /* * Ahora modificaremos el nombre del objeto numero 2 en la lista * enlazada comprobando así que el objeto se modifica en ambas listas */ ((Persona) enlazada.get(2)).setNombre("Nombre Modificado"); System.out.println("Sin clonación: "); System.out.println("Objeto 2 en la lista dinamica: " + dinamica.get(2)); System.out.println("Objeto 2 en la lista enlazada: " + enlazada.get(2)); /* * Por lo tanto pondremos especial cuidado cuando trabajemos con listas. * Ahora usemos la clonación de objetos. Para ello vaciaremos las * listas. */ dinamica.clear(); enlazada.clear(); for (int i = 0; i < 5; i++) { Persona persona = new Persona("Nombre " + i, "Apellidos" + i); //Añadimos el objeto dinamica.add(persona.clone()); enlazada.add(persona.clone()); } ((Persona) enlazada.get(2)).setNombre("Nombre Modificado"); System.out.println("Con clonación: "); System.out.println("Objeto 2 en la lista dinamica: " + dinamica.get(2)); System.out.println("Objeto 2 en la lista enlazada: " + enlazada.get(2)); /* * Ahora recorreremos las listas con distintos métodos */ /* * Método clásico, enumeración. */ System.out.println("\nEnumeración: "); for (int i = 0; i < dinamica.size(); i++) { Persona p = (Persona) dinamica.get(i); System.out.println(p); } /* * Método Iteración 1. */ System.out.println("\nIteración 1: "); //obtenemos el iterator de la lista dinámica Iterator it1 = dinamica.iterator(); //hasNext comprueba si existe un siguiente objeto while (it1.hasNext()) { //next devuelve el objeto siguiente Persona p = (Persona) it1.next(); System.out.println(p); } /* * Método Iteración 2. */ System.out.println("\nIteración 2: "); for (Iterator it2 = dinamica.iterator(); it2.hasNext();) { Persona p = (Persona) it2.next(); System.out.println(p); } /* * Método for each * Las etiquetas <> indican el tipo del que se compone la colección, * indicando así que la lista se compone exclusivamente de elementos * del tipo Persona. */ System.out.println("\nFor Each: "); //Copiamos la lista directamente en la inicialización. List<Persona> lista = new ArrayList<Persona>(dinamica); //El objeto p recibirá cada uno de los objetos de la lista for (Persona p : lista) { System.out.println(p); } /* * A continuación como ejemplo de uso de Collections, desordenaremos la * lista. */ Collections.shuffle(lista); System.out.println("\nLista desordenada: "); for (Persona p : lista) { System.out.println(p); } /* * Copiamos el objeto que se encuentra en la posición 3, y lo insertamos * en la posición 1 y eliminaremos la posición 2. */ lista.set(1, lista.get(3)); lista.remove(2); /* * Modificamos el Objeto para observar que se realiza por referencia. */ ((Persona) lista.get(1)).setNombre("Modificado"); /* * Ordenaremos la lista, para ello se necesita que implemente la * interfaz Comparable o contar con un objeto Comparator */ Collections.sort(lista); System.out.println("\nLista ordenada: "); for (Persona p : lista) { System.out.println(p); } System.out.println("\nFin de la aplicación."); } } |
Ejemplo 2:
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 | import java.util.Deque; import java.util.LinkedList; import java.util.Queue; import java.util.logging.Level; import java.util.logging.Logger; /** * * @author Francisco Javier Guerrero <www.desarrollador-web.com> */ public class EjemploPilasColas { public EjemploPilasColas() { try { inicio(); } catch (CloneNotSupportedException ex) { Logger.getLogger(EjemploListas.class.getName()).log(Level.SEVERE, null, ex); } } public static void main(String[] args) { new EjemploPilasColas(); } public void inicio() throws CloneNotSupportedException { System.out.println("Inicio de la aplicación.\n"); //Declaración de las listas Deque<Persona> pila = new LinkedList<Persona>(); Queue<Persona> cola = new LinkedList<Persona>(); /* * Se inicializará la pila */ for (int i = 0; i < 5; i++) { //offerLast tiene en cuenta restricciones de tamaño pila.addLast(new Persona("Nombre " + i, "Apellidos" + i)); } /* * Se inicializará la cola */ for (int i = 0; i < 5; i++) { //offer tiene en cuenta restricciones de tamaño cola.add(new Persona("Nombre " + i, "Apellidos" + i)); } /* * Manejo de pilas */ System.out.println("\nMostrar el primer elemento de la pila: "); System.out.println(pila.peekLast()); System.out.println(pila.getLast()); System.out.println("\nExtraer el primer elemento de la pila: "); System.out.println(pila.removeLast()); System.out.println(pila.pollLast()); /* * Manejo de colas */ System.out.println("\nMostrar el primer elemento de la cola: "); System.out.println(cola.peek()); System.out.println("\nExtraer el primer elemento de la cola: "); System.out.println(cola.remove()); System.out.println(cola.poll()); System.out.println("\nFin de la aplicación."); } } |
Ejemplos de Listas, Pilas y Colas: Enlace de descarga
Además de las clases explicadas, existen una serie de clases muy interesantes para determinados momentos como pueden ser las interfaces Map o Set, o las clases HashMap TreeMap, todo es cuestión de estudiar la API y saber elegir la adecuada para cada necesidad.
Enlaces de interés:
http://www.mkyong.com/java/while-loop-for-loop-and-iterator-performance-test-java/
http://stackoverflow.com/questions/256859/is-there-a-performance-difference-between-a-for-loop-and-a-for-each-loop




Comentarios Recientes