Please enable JavaScript.
Coggle requires JavaScript to display documents.
TAD Lista Doble - Coggle Diagram
TAD Lista Doble
-
-
Implementacion
La función de creación debe alojar memoria para la cabecera y hacer que los punteros siguiente y anterior apunten a ella, devolviendo un puntero a dicha cabecera.
-
-
Trabajar con varias posiciones simultáneamente tendrá un comportamiento idéntico al de las listas enlazadas excepto respecto al problema referente al borrado cuando se utilizan posiciones consecutivas.
Nosotros en nuestra implementación final optaremos por pasar un puntero a la posición para el borrado de forma que la posición usada quede apuntando al elemento siguente que se va a borrar al igual que ocurría en el caso de las listas simples.
La inserción se debe hacer a la izquierda del nodo apuntado por la posición ofrecida a la función insertar.
Si se desea, es posible modificar la función de forma que se pase un puntero a la posición de inserción para poder modificarla y hacer que apunte al nuevo elemento insertado.
Operacion borrar
-
-
es práctica común hacer que la cabecera de la lista doblemente enlazada sea una celda que efectivamente complete el círculo, es decir, el anterior a la celda de cabecera sea la última celda de la lista y la siguiente la primera.
Introduccion
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente.
Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera.
Operaciones
con listas
El único precio que pagamos por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas.
typedef struct celda{
tipoelemento elemento;
struct celda
siguiente,anterior;
}tipocelda;
typedef tipocelda *posicion;
Operacion
Siguiente
Es importante notar que aunque la estructura física de la lista puede hacer pensar que mediante la operación siguiente podemos alcanzar de nuevo un nodo de la lista, la estructura lógica es la de una lista y por lo tanto habrá una posición primero y una posición fin de forma que al aplicar una operación anterior o siguiente respectivamente sobre estas posiciones el resultado será un error.
