A las listas vistas hasta el momento podemos recorrerlas solamente en una dirección (Listas simplemente encadenadas)
Hay problemas donde se requiere recorrer la lista en ambas direcciones, en estos casos el empleo de listas doblemente encadenadas es recomendable.
Como ejemplo pensemos que debemos almacenar un menú de opciones en una lista, la opción a seleccionar puede ser la siguiente o la anterior, podemos desplazarnos en ambas direcciones.
Representación gráfica de una lista doblemente encadenada:
Observemos que una lista doblemente encadenada tiene dos punteros por cada nodo, uno apunta al nodo siguiente y otro al nodo anterior.
Seguimos teniendo un puntero (raiz) que tiene la dirección del primer nodo de la lista.
El puntero sig del último nodo igual que las listas simplemente encadenadas apunta a NULL, y el puntero ant del primer nodo apunta a NULL.
Se pueden plantear Listas tipo pila, cola y genéricas con enlace doble.
Hay que tener en cuenta que el requerimiento de memoria es mayor en las listas doblemente encadenadas ya que tenemos dos punteros por nodo.
La estructura del nodo es:
struct nodo {
int info;
struct nodo *sig;
struct nodo *ant;
};
Resolveremos algunas funciones para administrar listas genéricas empleando listas doblemente encadenadas para analizar la mecánica de enlace de nodos.
Muchas de las funciones, para listas simple y doblemente encadenadas no varía, como por ejemplo: el vacia, cantidad, liberar etc.
Programa: programa170.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
struct nodo *ant;
};
struct nodo *raiz=NULL;
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
int cantidad()
{
struct nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
void insertar(int pos, int x)
{
if (pos <= cantidad() + 1)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig=NULL;
if (pos == 1)
{
nuevo->sig = raiz;
if (raiz != NULL)
raiz->ant = nuevo;
raiz = nuevo;
}
else
if (pos == cantidad() + 1)
{
struct nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
reco->sig = nuevo;
nuevo->ant = reco;
}
else
{
struct nodo *reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
struct nodo *siguiente = reco->sig;
reco->sig = nuevo;
nuevo->ant = reco;
nuevo->sig = siguiente;
siguiente->ant = nuevo;
}
}
}
int extraer(int pos)
{
if (pos <= cantidad())
{
int informacion;
struct nodo *bor;
if (pos == 1)
{
informacion = raiz->info;
bor = raiz;
raiz = raiz->sig;
if ((raiz != NULL))
raiz->ant = NULL;
}
else
{
struct nodo *reco;
reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
struct nodo *prox = reco->sig;
bor = prox;
reco->sig = prox->sig;
struct nodo *siguiente = prox->sig;
if (siguiente != NULL)
siguiente->ant = reco;
informacion = prox->info;
}
free(bor);
return informacion;
}
else
return -1;
}
void borrar(int pos)
{
if (pos <= cantidad())
{
struct nodo *bor;
if (pos == 1)
{
bor = raiz;
raiz = raiz->sig;
if (raiz != NULL)
raiz->ant = NULL;
}
else
{
struct nodo *reco;
reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
struct nodo *prox = reco->sig;
bor = prox;
reco->sig = prox->sig;
struct nodo *siguiente = prox->sig;
if (siguiente != NULL)
siguiente->ant = reco;
}
free(bor);
}
}
void intercambiar(int pos1, int pos2)
{
if (pos1 <= cantidad() && pos2 <= cantidad())
{
struct nodo *reco1 = raiz;
int f;
for (f = 1; f < pos1; f++)
{
reco1 = reco1->sig;
}
struct nodo *reco2 = raiz;
for (f = 1; f < pos2; f++)
{
reco2 = reco2->sig;
}
int aux = reco1->info;
reco1->info = reco2->info;
reco2->info = aux;
}
}
int mayor()
{
if (!vacia())
{
int may = raiz->info;
struct nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
}
reco = reco->sig;
}
return may;
}
else
return -1;
}
int posMayor()
{
if (!vacia())
{
int may = raiz->info;
int x = 1;
int pos = x;
struct nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
pos = x;
}
reco = reco->sig;
x++;
}
return pos;
}
else
return -1;
}
int ordenada()
{
if (cantidad()>1)
{
struct nodo *reco1 = raiz;
struct nodo *reco2 = raiz->sig;
while (reco2 != NULL)
{
if (reco2->info<reco1->info)
{
return 0;
}
reco2 = reco2->sig;
reco1 = reco1->sig;
}
}
return 1;
}
int existe(int x)
{
struct nodo *reco = raiz;
while (reco != NULL)
{
if (reco->info == x)
return 1;
reco = reco->sig;
}
return 0;
}
int main()
{
insertar(1, 10);
insertar(2, 20);
insertar(3, 30);
insertar(2, 15);
insertar(1, 115);
imprimir();
printf("Luego de Borrar el primero\n");
borrar(1);
imprimir();
printf("Luego de Extraer el segundo\n");
extraer(2);
imprimir();
printf("Luego de Intercambiar el primero con el tercero\n");
intercambiar(1, 3);
imprimir();
if (existe(20))
printf("Se encuentra el 20 en la lista\n");
else
printf("No se encuentra el 20 en la lista\n");
printf("La posicion del mayor es:%i\n", posMayor());
if (ordenada())
printf("La lista esta ordenada de menor a mayor\n");
else
printf("La lista no esta ordenada de menor a mayor\n");
liberar();
getch();
return 0;
}
Para insertar en una determinada posición dentro de la lista:
void insertar (int pos, int x)
Primero con un if verificamos que exista esa posición en la lista (por ejemplo si la lista tiene 4 nodos podemos insertar hasta la posición 5, es decir uno más allá del último):
if (pos <= cantidad() + 1)
Si ingresa al if ya podemos crear el nodo:
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig=NULL;
Ahora debemos analizar si la inserción es al principio de la lista, al final o en medio ya que los enlaces varían según donde se lo inserta.
Para saber si se inserta al principio de la lista preguntamos si en pos llega un 1:
if (pos == 1)
Si llega un 1 luego enlazamos el puntero sig del nodo que creamos con la dirección del primer nodo de la lista (raiz apunta siempre al primer nodo de la lista)
Verificamos si raiz está apuntando actualmente a un nodo, en caso afirmativo enlazamos el puntero ant con el nodo que acabamos de crear y luego desplazamos raiz al nodo creado:
nuevo->sig = raiz;
if (raiz != NULL)
raiz->ant = nuevo;
raiz = nuevo;
Si no se inserta al principio de la lista preguntamos si se inserta al final:
if (pos == cantidad() + 1)
En caso de insertarse al final recorremos la lista hasta el último nodo:
struct nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
reco->sig = nuevo;
nuevo->ant = reco;
y enlazamos el puntero sig del último nodo de la lista con la dirección del nodo que acabamos de crear. El puntero ant del nodo que creamos lo enlazamos con el nodo que era último hasta este momento y está siendo apuntado por reco:
reco->sig = nuevo;
nuevo->ant = reco;
Si no se inserta al principio o al final significa que tenemos que insertar en medio de la lista.
Disponemos un for donde avanzamos un puntero auxiliar y nos detenemos una posición antes a donde tenemos que insertarlo:
struct nodo *reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
Disponemos otro puntero auxiliar que apunte al nodo siguiente a donde está apuntando reco. Ahora enlazamos el puntero sig del nodo apuntado por reco con la dirección del nodo creado y el puntero sig del nodo creado con la dirección del nodo siguiente. El puntero ant del nodo apuntado por nuevo lo enlazamos con el nodo apuntado por reco y el puntero ant del nodo apuntado por siguiente lo apuntamos a nuevo (con esto tenemos actualizados los cuatro punteros internos a la lista):
struct nodo *siguiente = reco->sig;
reco->sig = nuevo;
nuevo->ant = reco;
nuevo->sig = siguiente;
siguiente->ant = nuevo;
La función extraer recibe como parámetro la posición del nodo a extraer:
int extraer (int pos)
Primero verificamos que la posición exista en la lista:
if (pos <= cantidad())
En caso que exista verificamos si el nodo a extraer es el primero de la lista (este análisis debe hacerse ya que si es el primero de la lista se modifica el puntero raiz) y definimos previamente un puntero que utilizaremos para borrar el nodo y un entero que almacenaremos el valor a retornar:
int informacion;
struct nodo *bor;
if (pos == 1)
Si es el primero guardamos en una variable auxiliar la información del nodo y avanzamos el puntero raiz, luego si raiz apunta a un nodo disponemos el puntero ant de dicho nodo a NULL (también inicializamos bor con la dirección que hay que borrar):
informacion = raiz->info;
bor = raiz;
raiz = raiz->sig;
if ((raiz != NULL))
raiz->ant = NULL;
Si el nodo a extraer no está al principio de la lista avanzamos con una estructura repetitiva hasta el nodo anterior a extraer:
struct nodo *reco;
reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
Luego definimos otro puntero auxiliar y lo disponemos en el siguiente nodo a donde está apuntando reco:
struct nodo *prox = reco->sig;
Ahora enlazamos el puntero sig del nodo apuntado por reco al nodo siguiente del nodo apuntado por prox (es decir el nodo apuntado por prox queda fuera de la lista) disponemos finalmente otro puntero llamado siguiente que apunte al nodo que se encuentra una posición más adelante del nodo apuntado por prox, si dicho puntero apunta a un nodo actualizamos el puntero ant de dicho nodo con la dirección del nodo apuntado por reco:
struct nodo *prox = reco->sig;
bor = prox;
reco->sig = prox->sig;
struct nodo *siguiente = prox->sig;
if (siguiente != NULL)
siguiente->ant = reco;
informacion = prox->info;
Finalmente liberamos el espacio del nodo que queremos borrar y retornamos la información:
free(bor);
return informacion;
La función borrar es muy similar a la función extraer con la diferencia de que no retorna valor:
void borrar(int pos)
{
if (pos <= cantidad())
{
struct nodo *bor;
if (pos == 1)
{
bor = raiz;
raiz = raiz->sig;
if (raiz != NULL)
raiz->ant = NULL;
}
else
{
struct nodo *reco;
reco = raiz;
int f;
for (f = 1; f <= pos - 2; f++)
reco = reco->sig;
struct nodo *prox = reco->sig;
bor = prox;
reco->sig = prox->sig;
struct nodo *siguiente = prox->sig;
if (siguiente != NULL)
siguiente->ant = reco;
}
free(bor);
}
}
La función intercambiar recibe dos enteros que representan las posiciones de los nodos que queremos intercambiar sus informaciones:
void intercambiar (int pos1, int pos) {
Mediante un if verificamos que las dos posiciones existan en la lista:
if (pos1 <= cantidad() && pos2 <= cantidad())
Definimos un puntero auxiliar llamado reco1, lo inicializamos con la dirección del primer nodo y mediante un for avanzamos hasta la posición almacenada en pos1:
struct nodo *reco1 = raiz;
int f;
for (f = 1; f < pos1; f++)
{
reco1 = reco1->sig;
}
De forma similar con un segundo puntero auxiliar avanzamos hasta la posición indicada por pos2:
struct nodo *reco2 = raiz;
for (f = 1; f < pos2; f++)
{
reco2 = reco2->sig;
}
Por último intercambiamos las informaciones que almacenan cada nodo:
int aux = reco1->info;
reco1->info = reco2->info;
reco2->info = aux;
La función que retorna el mayor de la lista:
int mayor ()
Verificamos que la lista no esté vacía:
if (!vacia())
Suponemos que el mayor es el primero de la lista e inicializamos un puntero auxiliar con la dirección del segundo nodo de la lista:
int may = raiz->info;
struct nodo *reco = raiz->sig;
Mediante una estructura repetitiva recorremos toda la lista:
while (reco != NULL)
Cada vez que encontramos un nodo con información mayor que la variable may la actualizamos con este nuevo valor y avanzamos el puntero reco para visitar el siguiente nodo:
if (reco->info > may)
{
may = reco->info;
}
reco = reco->sig;
Fuera de la estructura repetitiva retornamos el mayor:
return may;
La función que retorna la posición del mayor es similar al anterior con la salvedad que debemos almacenar en otro auxiliar la posición donde se almacena el mayor:
int ListaGenerica::posMayor()
{
if (!vacia())
{
int may = raiz->info;
int x = 1;
int pos = x;
struct nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
pos = x;
}
reco = reco->sig;
x++;
}
return pos;
}
else
return -1;
}
La función que debe retornar si está ordenada la lista de menor a mayor es:
bool ordenada()
Lo primero que verificamos si la lista tiene más de un nodo significa que debemos controlarla:
if (cantidad()>1)
Disponemos dos punteros auxiliares con las direcciones del primer y segundo nodo de la lista:
struct nodo *reco1 = raiz;
struct nodo *reco2 = raiz->sig;
Mediante un while mientras no se finaliza la lista:
while (reco2 != NULL)
controlamos si la información del segundo nodo es menor al nodo anterior significa que la lista no está ordenada y podemos parar el análisis retornando un false
if (reco2->info<reco1->info)
{
return 0;
}
Dentro del while avanzamos los dos punteros a sus nodos siguientes respectivamente.
reco2 = reco2->sig;
reco1 = reco1->sig;
Fuera del while retornamos true indicando que la lista está ordenada de menor a mayor
return 1;
La función existe:
int existe(int x)
Mediante un while recorremos la la lista:
struct nodo *reco = raiz;
while (reco != NULL)
y en cada nodo que visitamos controlamos si el parámetro x es igual a la información del nodo, en caso afirmativo salimos de la función retornando un 1:
if (reco->info == x)
return 1;
reco = reco->sig;
Fuera del while retornamos 0 indicando que ningún nodo coincide con el parámetro x:
return 0;
Problema propuesto
-
Plantear un programa para administrar una lista genérica doblemente encadenada implementando las siguientes funciones:
a) Insertar un nodo al principio de la lista.
b) Insertar un nodo al final de la lista.
c) Insertar un nodo en la segunda posición. Si la lista está vacía no se inserta el nodo.
d) Insertar un nodo en la ante última posición.
e) Borrar el primer nodo.
f) Borrar el segundo nodo.
g) Borrar el último nodo.
h) Borrar el nodo con información mayor.
programa171.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
struct nodo *ant;
};
struct nodo *raiz=NULL;
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
int cantidad()
{
struct nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
void imprimir()
{
struct nodo *reco=raiz;
printf("Lista completa.\n");
while (reco!=NULL)
{
printf("%i ",reco->info);
reco=reco->sig;
}
printf("\n");
}
void insertarPrimero(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig = raiz;
if (raiz != NULL)
raiz->ant = nuevo;
raiz = nuevo;
}
void insertarUtlimo(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig=NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
struct nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
reco->sig = nuevo;
nuevo->ant = reco;
}
}
void insertarSegundo(int x)
{
if (raiz != NULL)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig=NULL;
if (raiz->sig == NULL)
{
//Hay un solo nodo.
raiz->sig = nuevo;
nuevo->ant = raiz;
}
else
{
struct nodo *segundo = raiz->sig;
nuevo->sig = segundo;
nuevo->ant = raiz;
raiz->sig = nuevo;
segundo->ant = nuevo;
}
}
}
void insertarAnteUltimo(int x)
{
if (raiz != NULL)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
nuevo->ant=NULL;
nuevo->sig=NULL;
if (raiz->sig == NULL) {
//Hay un solo nodo.
nuevo->sig = raiz;
raiz->ant = nuevo;
nuevo->ant = NULL;
raiz = nuevo;
}
else
{
struct nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
struct nodo *anteultimo = reco->ant;
anteultimo->sig = nuevo;
nuevo->ant = anteultimo;
nuevo->sig = reco;
reco->ant = nuevo;
}
}
}
void borrarPrimero()
{
if (raiz != NULL)
{
struct nodo *bor = raiz;
raiz = raiz->sig;
if (raiz != NULL)
raiz->ant = NULL;
free(bor);
}
}
void borrarSegundo()
{
if (raiz != NULL)
{
if (raiz->sig != NULL)
{
struct nodo *bor = raiz->sig;
struct nodo *tercero = raiz->sig;
tercero = tercero->sig;
raiz->sig = tercero;
if (tercero != NULL)
tercero->ant = raiz;
free(bor);
}
}
}
void borrarUltimo()
{
if (raiz != NULL)
{
if (raiz->sig == NULL)
{
free(raiz);
raiz = NULL;
}
else
{
struct nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
struct nodo *ante = reco->ant;
ante->sig = NULL;
free(reco);
}
}
}
void borrarMayor()
{
if (raiz != NULL)
{
struct nodo *reco = raiz;
int may = raiz->info;
while (reco != NULL)
{
if (reco->info>may)
{
may = reco->info;
}
reco = reco->sig;
}
reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
if (reco->info == may)
{
if (reco == raiz)
{
bor = raiz;
raiz = raiz->sig;
if (raiz != NULL)
raiz->ant = NULL;
free(bor);
return;
}
else {
if (reco->sig == NULL)
{
bor = reco;
reco = reco->ant;
reco->sig = NULL;
free(bor);
return;
}
else
{
struct nodo *ante = reco->ant;
bor = reco;
reco = reco->sig;
ante->sig = reco;
reco->ant = ante;
free(bor);
return;
}
}
}
else {
reco = reco->sig;
}
}
}
}
int main()
{
insertarPrimero(10);
insertarPrimero(45);
insertarPrimero(23);
insertarPrimero(89);
imprimir();
printf("Insertamos un nodo al final:\n");
insertarUtlimo(160);
imprimir();
printf("Insertamos un nodo en la segunda posición:\n");
insertarSegundo(13);
imprimir();
printf("Insertamos un nodo en la anteultima posición:\n");
insertarAnteUltimo(600);
imprimir();
printf("Borramos el primer nodo de la lista:\n");
borrarPrimero();
imprimir();
printf("Borramos el segundo nodo de la lista:\n");
borrarSegundo();
imprimir();
printf("Borramos el ultimo nodo de la lista:\n");
borrarUltimo();
imprimir();
printf("Borramos el mayor de la lista:\n");
borrarMayor();
imprimir();
liberar();
getch();
return 0;
}