Tarea IV Actividad II

Listas 

Una LISTA es un conjunto ordenado de elementos homogéneos, en la que no hay restricciones de acceso, la introducción y borrado de elementos puede realizarse en cualquier posición de la misma.

Representación gráfica:


Representación en Memoria:



Tipos o Clasificación. Listas simples enlazadas. 

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo. 

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo. 

Listas enlazadas circulares 

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Listas enlazadas circulares simples.

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciando  Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 

Lista Enlazada Doblemente Circular

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada. 

Nodo cabecera.

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciado de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio. 

Bibliografía. 

- Algoritmos, estructuras de datos y programación orientada a objetos. Escrito por Roberto Flórez Rueda 

- Cómo programar en Java.  Escrito por Harvey M. Deitel, Paul J. Deitel 

- Estructuras de datos: Referencia práctica con orientación a objetos. Escrito por Román Martínez, Elda Quiroga


No hay comentarios:

Publicar un comentario