Estructuras de Datos y Algoritmos en Java

La cienca informática emfatiza dos tópicos importantes: las estructuras de datos y los algoritmos. Estos tópicos son importantes porque las elecciones que usted haga para las estructuras de datos y los algoritmos de un programa afectarán al uso de la memoria (las estructuras de datos) y al tiempo del procesador (los algoritmos que interactúan con esas estructuras de datos). Cuando utiliza una estructura de datos o un algoritmo alguna veces descubre una relación inversa entre la utilización de memoria y el tiempo de CPU: cuanto menos memoria utiliza una estructura de datos, más tiempo de CPU necesitan los algoritmos asociados para procesar los items de datos de la estructura, que son valores de tipos primitivos u objetos, mediante referencias. De igual forma, cuanto más memoria utilice una estructura de datos, menor tiempo de CPU necesitan los algoritmos asociados y el procesamiento de los ítems de datos es mucho más rápido. En la siguiente figura aparece está relación inversa.

Un ejemplo de la relación inversa entre la utilización de memoria y el consumo de CPU implica las estructuras de datos de los arrays unidimensionales y las listas doblemente enlazadas, y sus algoritmos de inserción/borrado. Para una lista de ítems dada, una array unidimensional ocupa menos memoria que una lista doblemente enlzada: este tipo de listas necesita asociar enlaces con ítems de datos para encontrar el predecesor y el sucesor, lo que requiere memoria extra. Por el contrario los algoritmos para insertar/eliminar elementos en un array unidimensional son más lentos que los algoritmos equivalentes de una lista doblemente enlazada: insertar o borrar un ítem en un array unidimensional requiere movimiento de ítems de datos para poder tener un elemento vacío para insertar o para borrar.