ArrayList, LinkedList, HashMap…) ocultan su implementación detrás de una interfaz común, pero por dentro son muy distintas y eso cambia el coste de cada operación. Ver cómo están hechas ayuda a elegir la adecuada y a implementar las propias.
Las ideas clave del bloque
Listas
- ArrayList: array contiguo.
get(i)en ; insertar o borrar en medio, . Al llenarse se duplica: añadir al final es amortizado. - Lista enlazada: nodos con referencias. Insertar al principio en ; acceder por índice, .
Tablas hash
La función hash calcula la posición de cada elemento: búsqueda en de media. Las colisiones se resuelven con sondeo (tabla cerrada, con marcas de borrado) o con listas (tabla abierta). El factor de carga decide cuándo redimensionar.Árboles enhebrados
Los enlaces vacíos de un árbol binario se reutilizan como hilos al sucesor y al predecesor en inorden: el recorrido no necesita pila ni recursión.Orden recomendado
1
ArrayList y lista enlazada
Las dos listas en Java paso a paso: capacidad, desplazamientos, recorrido de nodos y coste.
2
Tablas hash
Inserta, busca y borra en una tabla hash cerrada o abierta y mira cada sondeo.
3
Árbol binario enhebrado
Hilos al sucesor y al predecesor en inorden, y recorrido del árbol en Java sin recursión ni pila.
Temas de este bloque
ArrayList y lista enlazada
ArrayList frente a lista enlazada en Java paso a paso: array contiguo con capacidad y redimensionado, nodos enlazados, coste de get, add y remove, coste amortizado y cuándo usar cada una.
Tablas hash
Tablas hash en Java paso a paso: función hash, colisiones, tabla cerrada con sondeo lineal y cuadrático, tabla abierta con listas, borrado con marcas, factor de carga y redimensionado.
Árbol binario enhebrado
Qué es un árbol binario enhebrado: hilos al sucesor y al predecesor en inorden, marcas de hilo, recorrido en inorden e inorden inverso sin recursión ni pila, con código Java.
Simuladores de estructuras de datos en Java en Simulab
ArrayList y lista enlazada
Las dos listas en Java paso a paso: capacidad, desplazamientos, recorrido de nodos y coste.
Tablas hash
Inserta, busca y borra en una tabla hash cerrada o abierta y mira cada sondeo.
Árbol binario enhebrado
Hilos al sucesor y al predecesor en inorden, y recorrido del árbol en Java sin recursión ni pila.