Una lista doblemente enlazada (DLL) es una estructura de datos lineal que contiene un puntero adicional, generalmente llamado puntero anterior , junto con el siguiente puntero y los datos que están allí en una lista enlazada individualmente. A continuación se muestra la imagen para ilustrar lo mismo.
Ventajas de DLL :
- Invertir la lista doblemente enlazada es muy fácil.
- Puede asignar o reasignar memoria fácilmente durante su ejecución.
- Al igual que con una lista de enlaces simples, es la estructura de datos más fácil de implementar.
- El recorrido de esta lista doblemente enlazada es bidireccional, lo que no es posible en una lista enlazada de forma sencilla.
- La eliminación de Nodes es fácil en comparación con una lista enlazada individual . La eliminación de una lista con un solo enlace requiere que se elimine un puntero al Node y al Node anterior, pero en la lista doblemente enlazada, solo se requiere el puntero que se debe eliminar.
Desventajas de DLL :
- Utiliza memoria adicional en comparación con la array y la lista enlazada individualmente.
- Dado que los elementos en la memoria se almacenan aleatoriamente, se accede a los elementos secuencialmente, no se permite el acceso directo.
Usos de DLL :
- Se utiliza en los sistemas de navegación donde se requiere navegación delantera y trasera.
- El navegador lo utiliza para implementar la navegación hacia adelante y hacia atrás de las páginas web visitadas que es un botón de avance y retroceso.
- También se utiliza para representar una baraja de cartas de juego clásico.
- También lo utilizan varias aplicaciones para implementar la funcionalidad de deshacer y rehacer.
- La lista doblemente enlazada también se utiliza en la construcción de caché MRU / LRU (Usado más/menos recientemente).
- Otras estructuras de datos como pilas , tablas hash , árboles binarios también se pueden construir o programar utilizando una lista de doble enlace.
- También en muchos sistemas operativos, el planificador de subprocesos (lo que elige qué proceso debe ejecutarse en qué momento) mantiene una lista doblemente vinculada de todos los procesos que se ejecutan en ese momento.