Listas Simplemente y Doblemente enlazadas en Java

Listas Simplemente Enlazadas

Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento. Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas. La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

A continuación les dejo un vídeo explicativo sobre el tema, con ejercicios en java puesto en practica:


/********************************************************************************\

Listas Doblemente Enlazadas

Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.
La asignación de memoria es hecha al momento de la ejecución.

En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).

Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:

• Comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
• Comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.

• Tweet