doubly linked list java implementation code examples
Este tutorial explica la lista doblemente enlazada en Java junto con la implementación de la lista doble enlazada, el código Java de la lista doble enlazada circular y los ejemplos:
La lista vinculada es una representación secuencial de elementos. Cada elemento de la lista vinculada se denomina 'Nodo'. Un tipo de lista enlazada se llama 'Lista enlazada individualmente'.
En esto, cada nodo contiene una parte de datos que almacena los datos reales y una segunda parte que almacena el puntero al siguiente nodo de la lista. Ya hemos aprendido los detalles de la lista enlazada individualmente en nuestro tutorial anterior.
=> Consulte TODOS los tutoriales de Java aquí.
Lo que vas a aprender:
Lista doblemente enlazada en Java
Una lista enlazada tiene otra variación llamada 'lista doblemente enlazada'. Una lista doblemente enlazada tiene un puntero adicional conocido como puntero anterior en su nodo, además de la parte de datos y el siguiente puntero como en la lista enlazada individualmente.
Un nodo en la lista doblemente enlazada tiene el siguiente aspecto:
ciclo de vida del error en las pruebas de software
Aquí, 'Anterior' y 'Siguiente' son punteros a los elementos anterior y siguiente del nodo, respectivamente. Los 'Datos' son el elemento real que se almacena en el nodo.
La siguiente figura muestra una lista doblemente enlazada.
El diagrama de arriba muestra la lista doblemente enlazada. Hay cuatro nodos en esta lista. Como puede ver, el puntero anterior del primer nodo y el siguiente puntero del último nodo se establecen en nulo. El puntero anterior establecido en nulo indica que este es el primer nodo en la lista doblemente enlazada, mientras que el siguiente puntero establecido en nulo indica que el nodo es el último nodo.
Ventajas
- Como cada nodo tiene punteros que apuntan a los nodos anterior y siguiente, la lista doblemente enlazada se puede recorrer fácilmente en dirección hacia adelante y hacia atrás.
- Puede agregar rápidamente el nuevo nodo simplemente cambiando los punteros.
- De manera similar, para la operación de eliminación, ya que tenemos punteros anteriores y siguientes, la eliminación es más fácil y no necesitamos recorrer toda la lista para encontrar el nodo anterior como en el caso de la lista enlazada individualmente.
Desventajas
- Dado que hay un puntero adicional en la lista doblemente enlazada, es decir, el puntero anterior, se requiere espacio de memoria adicional para almacenar este puntero junto con el siguiente puntero y elemento de datos.
- Todas las operaciones como adición, eliminación, etc. requieren que tanto los punteros anteriores como los siguientes se manipulen, lo que impone una sobrecarga operativa.
Implementación en Java
La implementación de la lista doblemente enlazada en Java comprende la creación de una clase de lista doblemente enlazada, la clase de nodo y la adición de nodos a la lista doblemente enlazada.
La adición de nuevos nodos generalmente se realiza al final de la lista. El siguiente diagrama muestra la adición del nuevo nodo al final de la lista doblemente enlazada.
Como se muestra en el diagrama anterior, para agregar un nuevo nodo al final de la lista, el siguiente puntero del último nodo ahora apunta al nuevo nodo en lugar de nulo. El puntero anterior del nuevo nodo apunta al último nodo. Además, el siguiente puntero del nuevo nodo apunta a nulo, lo que lo convierte en un nuevo último nodo.
El siguiente programa muestra la implementación de Java de una lista doblemente enlazada con la adición de nuevos nodos al final de la lista.
|_+_|Producción:
Nodos de lista doblemente enlazada:
10 20 30 40 50
Además de agregar un nuevo nodo al final de la lista, también puede agregar un nuevo nodo al principio de la lista o entre la lista. Dejamos esta implementación al lector para que los lectores puedan comprender las operaciones de una mejor manera.
Lista circular doblemente enlazada en Java
Una lista circular doblemente enlazada es una de las estructuras complejas. En esta lista, el último nodo de la lista doblemente enlazada contiene la dirección del primer nodo y el primer nodo contiene la dirección del último nodo. Por lo tanto, en una lista circular doblemente vinculada, hay un ciclo y ninguno de los punteros de nodo se establece en nulo.
El siguiente diagrama muestra la lista circular doblemente enlazada.
Como se muestra en el diagrama anterior, el siguiente puntero del último nodo apunta al primer nodo. El puntero anterior del primer nodo apunta al último nodo.
Las listas circulares doblemente enlazadas tienen amplias aplicaciones en la industria del software. Una de esas aplicaciones es la aplicación musical que tiene una lista de reproducción. En la lista de reproducción, cuando termine de reproducir todas las canciones, al final de la última canción, regresará a la primera canción automáticamente. Esto se hace mediante listas circulares.
Ventajas de una lista circular doble enlazada:
- La lista circular doblemente enlazada se puede recorrer de la cabeza a la cola o de la cola a la cabeza.
- Ir de la cabeza a la cola o de la cola a la cabeza es eficiente y solo requiere un tiempo constante O (1).
- Se puede utilizar para implementar estructuras de datos avanzadas, incluido el montón de Fibonacci.
Desventajas:
- Como cada nodo necesita dejar espacio para el puntero anterior, se requiere memoria adicional.
- Necesitamos lidiar con muchos punteros mientras realizamos operaciones en una lista circular doblemente enlazada. Si los punteros no se manejan correctamente, la implementación puede fallar.
El siguiente programa Java muestra la implementación de la lista circular doblemente enlazada.
|_+_|Producción:
Lista circular doblemente enlazada: 40 50 60 70 80
Lista circular doblemente enlazada trazada hacia atrás:
80 70 60 50 40
En el programa anterior, hemos agregado el nodo al final de la lista. Como la lista es circular, cuando se agrega el nuevo nodo, el siguiente puntero del nuevo nodo apuntará al primer nodo y el puntero anterior del primer nodo apuntará al nuevo nodo.
De manera similar, el puntero anterior del nuevo nodo apuntará al último nodo actual, que ahora se convertirá en el penúltimo nodo. Dejamos la implementación de agregar un nuevo nodo al principio de la lista y entre los nodos a los lectores.
Preguntas frecuentes
P # 1) ¿Puede la Lista Doblemente Vinculada ser circular?
Responder: Si. Es una estructura de datos más compleja. En una lista circular doblemente enlazada, el puntero anterior del primer nodo contiene la dirección del último nodo y el siguiente puntero del último nodo contiene la dirección del primer nodo.
P # 2) ¿Cómo se crea una lista enlazada doblemente circular?
Responder: Puede crear una clase para una lista enlazada doblemente circular. Dentro de esta clase, habrá una clase estática para representar el nodo. Cada nodo contendrá dos punteros: anterior y siguiente, y un elemento de datos. Luego, puede tener operaciones para agregar nodos a la lista y recorrer la lista.
P # 3) ¿La lista doblemente enlazada es lineal o circular?
Responder: La lista doblemente enlazada es una estructura lineal pero una lista circular doblemente enlazada que tiene la cola apuntando a la cabeza y la cabeza apuntando a la cola. De ahí que sea una lista circular.
P # 4) ¿Cuál es la diferencia entre la lista doblemente enlazada y la lista enlazada circular?
Responder: Una lista doblemente enlazada tiene nodos que mantienen información sobre sus nodos anteriores y siguientes utilizando los punteros anterior y siguiente, respectivamente. Además, el puntero anterior del primer nodo y el siguiente puntero del último nodo se establecen en nulo en la lista doblemente vinculada.
En la lista enlazada circular, no hay nodos de inicio o final y los nodos forman un ciclo. Además, ninguno de los punteros se establece en nulo en la lista enlazada circular.
P # 5) ¿Cuáles son las ventajas de una lista doblemente vinculada?
cómo declarar una lista vinculada en java
Responder: Las ventajas de la lista doblemente vinculada son:
- Se puede atravesar tanto hacia delante como hacia atrás.
- La operación de inserción es más fácil ya que no es necesario recorrer toda la lista para encontrar el elemento anterior.
- La eliminación es eficiente ya que sabemos que los nodos anterior y siguiente y la manipulación es más fácil.
Conclusión
En este tutorial, discutimos en detalle la lista de enlaces dobles en Java. Una lista doblemente enlazada es una estructura compleja en la que cada nodo contiene punteros a sus nodos anteriores y siguientes. La gestión de estos enlaces a veces es difícil y puede provocar la ruptura del código si no se maneja correctamente.
En general, las operaciones de una lista doblemente vinculada son más eficientes, ya que podemos ahorrar tiempo para recorrer la lista, ya que tenemos los punteros anterior y siguiente.
La lista circular doblemente enlazada es más compleja y forman un patrón circular con el puntero anterior del primer nodo apuntando al último nodo y el siguiente puntero del último nodo apuntando al primer nodo. En este caso, también, las operaciones son eficientes.
Con esto, terminamos con la lista vinculada en Java. Esté atento a muchos más tutoriales sobre técnicas de búsqueda y clasificación en Java.
=> Visite aquí para ver la serie exclusiva de tutoriales de formación en Java.
Lectura recomendada
- Estructura de datos de lista doblemente enlazada en C ++ con ilustración
- Algoritmo de búsqueda binaria en Java: implementación y ejemplos
- Lista de Java: cómo crear, inicializar y usar la lista en Java
- Tutorial de interfaz Java y clase abstracta con ejemplos
- Métodos de lista de Java: ordenar lista, contener, agregar lista, eliminar lista
- Ordenación por inserción en Java: algoritmo y ejemplos de ordenación por inserción
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java
- Clasificación de burbujas en Java: algoritmos de clasificación de Java y ejemplos de código