Listas Doblemente Encadenada

Publicado por rogikato / en 19:27 / /

En una lista doblemente encadenada, cada elemento posee las informaciones de quien es su sucesor y su antecesor.
 
Principales ventajas:
 1. Permite caminar en las dos direcciones de la lista.
 2. Inserción y eliminación de elementos son realizados con más facilidad.

Principales problemas:
 • Mayor espacio reservado
 • Manipulación de un puntero extra Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada. (Fig 4.2)La operación de inserción de un nuevo elemento en la posición anterior al elemento actual puede ser descrito como sigue (suponiendo que actual no es el primer elemento de la lista):
nuevo->proximo = actual; 
nuevo->anterior = actual->anterior; 
actual->anterior->proximo = nuevo; 
actual->anterior = nuevo; 
 Note que en este caso no es necesario un elemento posterior. Especificación: Igual a la del ejemplo estático para listas simplemente encadenadas
Observación: En el ejemplo abajo todavía estamos utilizando un puntero auxiliar llamdo "ant", como ejercicio, realice una nueva implementación de la función inserta_elemento sin utilizar este puntero auxiliar.
 

Código:
  #include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista{ int elem; NO *prox; // guarda la pos. del próx. elem. en la lista NO *ante; // guarda la pos.del elem. ant. en la lista */ }; struct lista { NO *head ; // guarda la dir. de primer elem. de lista }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A){ NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL)//lista ESTA VACIA { aux->prox = NULL; aux->ante = NULL; L->head = aux; } else{ atu = L->head; ant = NULL; while ((atu != NULL) && (atu->elem <= A)) { ant = atu; atu = atu->prox; } if (ant == NULL) // insert en primera pos. de lista { aux->prox = L->head; aux->ante = NULL; L->head->ante = aux; L->head = aux; } else { aux->prox = ant->prox; aux->ante = ant; if (ant->prox != NULL) ant->prox->ante = aux; ant->prox = aux; } } } else exit(0); return; } int Eliminar_Elemento(LE *L, int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) {if(L->head==NULL) return -1; else { act=L->head; if(act->elem==A) {if(act->prox==NULL) L->head=NULL; else{ L->head=act->prox; act->prox->ante=NULL; }return 1; } while(act!=NULL) { if(act->elem==A) { if(act->prox==NULL) {ant->prox=NULL; act->prox=NULL; act->ante=NULL; } else{ ant->prox=act->prox; act->prox->ante=ant; act->prox=NULL; act->ante=NULL; } return 1; } else { ant=act; act=act->prox; } } return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; while (atu != NULL) { tam++; cout<<atu->elem<<" "; atu = atu->prox; } cout<<" de tama\xa4o "<<tam; } } main() { int aux_l; LE *l; int x; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el numero entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }