Estructuras de Datos
Archivos necesarios:
Para poder representar datos hay veces en que las variables no son suficiente. Para estos casos utilizamos una herramienta llamada estructura de datos en la que podemos representar datos de diferentes maneras, como lista, como árbol, como red, etc. En este trial veremos tres de las estructuras de datos más utilizadas, que son la base fundamental de todas las demás estructuras. No veremos cómo crear estas estructuras sino únicamente veremos cómo utilizarlas y veremos un poco de justificación en cuanto a desempeño.
Para este trial vamos a utilizar un programa que nos permite medir el tiempo que se tardan diferentes maneras de agregar y leer datos en las tres estructuras de datos que vamos a utilizar. Todos los tiempos que utilicemos en el trial van a ser para estructuras de 65,535 elementos.
¿Qué estructuras hay?
Arreglos
La estructura de datos más sencilla es el arreglo. Un arreglo es un conjunto de posiciones de memoria adyacentes. Podemos pensar en un arreglo como una fila de varias cajas en las que podemos guardar cosas. Como las posiciones de memoria de un arreglo son adyacentes tiene la ventaja de tener un tiempo de acceso muy rápido, pero tiene la desventaja de que todas las posiciones de memoria deben estar reservadas, por lo que gasta grandes cantidades de memoria.
- Tiempo escritura: 17 milisegundos.
- Tiempo lectura: 4 milisegundos.
Lista Ligada
La segunda estructura que vamos a ver es la lista ligada. Una lista ligada es un conjunto de nodos que pueden contener valores y que apuntan hacia el siguiente nodo de la lista. Podemos imaginarlo como una fila de personas que se están tomando de las manos, la primera persona agarra a la segunda y esta a su vez apunta a la tercera. Una lista ligada tiene muchas ventajas sobre un arreglo, la más importante es que puede cambiar de tamaño ya que lo único que se debe hacer es crear un nuevo nodo y decirle al último nodo que apunte hacia este.
- Tiempo escritura con addFirst(): 38 milisegundos.
- Tiempo escritura con addLast(): 64 milisegundos.
- Tiempo lectura: 36,874 milisegundos.
Vector
Un vector busca tener las ventajas de un arreglo pero con la posibilidad de crecer que tiene una lista ligada. Un vector implementa la interfaz List para tener los métodos de la lista ligada, pero en la codificación en realidad es un arreglo. Ya que para que un arreglo pueda crecer necesitan crear una copia y mover las posiciones de memoria adyacentes insertar elementos al inicio o al centro de un vector es muy lento (lo que hace que los algoritmos de ordenamiento tengan un pésimo desempeño en un vector), pero insertar elementos al final brinda un desempeño muy bueno.
- Tiempo escritura con add(): 17 milisegundos.
- Tiempo escritura con insertElementAt(): 3988 milisegundos
- Tiempo lectura: 2 milisegundos.
¿Cómo utilizar las estructuras?
Arreglo
Lista Ligada
Vector
Aqui es muy importante fijarnos en un par de cosas. Primero que nada, el objeto LinkedList implementa algo llamado Templates, lo que nos da la libertad de seleccionar cualquier clase como el tipo de objetos que guarda una lista ligada, pero sólo podemos guardar un tipo de objetos. Para utilizar templates lo único que tenemos que hacer es poner el nombre de la clase entre símbolos de mayor y menor que como se ve en la imagen. Por ejemplo, para declarar un LinkedList que guarde objetos String podemos utilizar el constructor:
LinkedList<String> list = new LinkedList<String>();
El Vector nos permite guardar cualquier tipo de objeto pero cuando sacamos el objeto con el método get() debemos utilizar un cast al tipo de dato que guardamos.
También es muy importante darse cuenta de que la lista ligada y el vector no pueden guardar tipos de datos primitivos, es por eso que en el ejemplo estamos utilizando la clase Integer que únicamente nos sirve como una envoltura para un tipo de dato int.
Regresar