Embedded Files
De nuevo tenemos el mismo repertorio de operaciones sobre este tipo listas:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Añadir un elemento
Añadir un elemento
Nos encontramos ahora ante un tipo de estructura algo diferente de las que hemos estado viendo, así que entraremos en más detalles.
Vamos a intentar ver todos los casos posibles de inserción de elementos en listas doblemente enlazadas.
Añadir elemento en una lista doblemente enlazada vacía
Añadir elemento en una lista doblemente enlazada vacía
Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL:
El proceso es muy simple, bastará con que:
lista apunta a nodo.
lista->siguiente y lista->anterior apunten a null.
Insertar un elemento en la primera posición de la lista
Insertar un elemento en la primera posición de la lista
Partimos de una lista no vacía. Para simplificar, consideraremos que lista apunta al primer elemento de la lista doblemente enlazada:
El proceso es el siguiente:
nodo->siguiente debe apuntar a Lista.
nodo->anterior apuntará a Lista->anterior.
Lista->anterior debe apuntar a nodo.
Recuerda que Lista no tiene por qué apuntar a ningún miembro concreto de una lista doblemente enlazada, cualquier miembro es igualmente válido como referencia.
Insertar un elemento en la última posición de la lista
Insertar un elemento en la última posición de la lista
gual que en el caso anterior, partiremos de una lista no vacía, y de nuevo para simplificar, que Lista está apuntando al último elemento de la lista:
El proceso es el siguiente:
nodo->siguiente debe apuntar a Lista->siguiente (NULL).
Lista->siguiente debe apuntar a nodo.
nodo->anterior apuntará a Lista.
Insertar un elemento a continuación de un nodo cualquiera de una lista
Insertar un elemento a continuación de un nodo cualquiera de una lista
Bien, este caso es más genérico, ahora partimos de una lista no vacía, e insertaremos un nodo a continuación de uno nodo cualquiera que no sea el último de la lista:
El proceso sigue siendo muy sencillo:
Hacemos que nodo->siguiente apunte a lista->siguiente.
Hacemos que Lista->siguiente apunte a nodo.
Hacemos que nodo->anterior apunte a lista.
Hacemos que nodo->siguiente->anterior apunte a nodo.
o que hemos hecho es trabajar como si tuviéramos dos listas enlazadas, los dos primeros pasos equivalen a lo que hacíamos para insertar elementos en una lista abierta corriente.
Los dos siguientes pasos hacen lo mismo con la lista que enlaza los nodos en sentido contrario.
El paso 4 es el más oscuro, quizás requiera alguna explicación.
Supongamos que disponemos de un puntero auxiliar, "p" y que antes de empezar a insertar nodo, hacemos que apunte al nodo que quedará a continuación de nodo después de insertarlo, es decir p = Lista->siguiente.
Ahora empezamos el proceso de inserción, ejecutamos los pasos 1, 2 y 3. El cuarto sería sólo hacer que p->anterior apunte a nodo. Pero nodo->siguiente ya apunta a p, así que en realidad no necesitamos el puntero auxiliar, bastará con hacer que nodo->siguiente->anterior apunte a nodo.
Buscar o localizar un elemento de una lista doblemente enlazada
Buscar o localizar un elemento de una lista doblemente enlazada
En muchos aspectos, una lista doblemente enlazada se comporta como dos listas abiertas que comparten los datos. En ese sentido, todo lo dicho en el capítulo sobre la localización de elementos en listas abiertas se puede aplicar a listas doblemente enlazadas.
Pero además tenemos la ventaja de que podemos avanzar y retroceder desde cualquier nodo, sin necesidad de volver a uno de los extremos de la lista.
Por supuesto, se pueden hacer listas doblemente enlazadas no ordenadas, existen cientos de problemas que pueden requerir de este tipo de estructuras. Pero parece que la aplicación más sencilla de listas doblemente enlazadas es hacer arrays dinámicos ordenados, donde buscar un elemento concreto a partir de cualquier otro es más sencillo que en una lista abierta corriente.
Pero de todos modos veamos algún ejemplo sencillo.
Para recorrer una lista procederemos de un modo parecido al que usábamos con las listas abiertas, ahora no necesitamos un puntero auxiliar, pero tenemos que tener en cuenta que Lista no tiene por qué estar en uno de los extremos:
Retrocedemos hasta el comienzo de la lista, asignamos a lista el valor de lista->anterior mientras lista->anterior no sea NULL.
Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.
Dentro del bucle asignaremos a lista el valor del nodo siguiente al actual.
Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
struct _nodo *anterior;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
...
pNodo = indice;
...
indice = Lista;
while(indice->anterior) indice = indice->anterior;
while(indice) {
printf("%d\n", indice->dato);
indice = indice->siguiente;
}
...
Es importante que no perdamos el nodo Lista, si por error le asignáramos un valor de un puntero a un nodo que no esté en la lista, no podríamos acceder de nuevo a ella.
Es por eso que tendremos especial cuidado en no asignar el valor NULL a Lista.
Eliminar un elemento de una lista doblemente enlazada
De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior, si no es NULL o Lista->siguiente en caso contrario.
Si nodo apunta a Lista,
Si Lista->anterior no es NULL hacemos que Lista apunte a Lista->anterior.
Si Lista->siguiente no es NULL hacemos que Lista apunte a Lista->siguiente.
Si ambos son NULL, hacemos que Lista sea NULL.
Si nodo->anterior no es NULL, hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.
Si nodo->siguiente no es NULL, hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
Borramos el nodo apuntado por nodo.
Código del ejemplo completo
Código del ejemplo completo
#include <stdio.h>
#define ASCENDENTE 1
#define DESCENDENTE 0
typedef struct _nodo {
int valor;
struct _nodo *siguiente;
struct _nodo *anterior;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
/* Funciones con listas: */
void Insertar(Lista *l, int v);
void Borrar(Lista *l, int v);
void BorrarLista(Lista *);
void MostrarLista(Lista l, int orden);
int main() {
Lista lista = NULL;
pNodo p;
Insertar(&lista, 20);
Insertar(&lista, 10);
Insertar(&lista, 40);
Insertar(&lista, 30);
MostrarLista(lista, ASCENDENTE);
MostrarLista(lista, DESCENDENTE);
Borrar(&lista, 10);
Borrar(&lista, 15);
Borrar(&lista, 45);
Borrar(&lista, 30);
MostrarLista(lista, ASCENDENTE);
MostrarLista(lista, DESCENDENTE);
BorrarLista(&lista);
return 0;
}
void Insertar(Lista *lista, int v) {
pNodo nuevo, actual;
/* Crear un nodo nuevo */
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->valor = v;
/* Colocamos actual en la primera posición de la lista */
actual = *lista;
if(actual) while(actual->anterior) actual = actual->anterior;
/* Si la lista está vacía o el primer miembro es mayor que el nuevo */
if(!actual || actual->valor > v) {
/* Añadimos la lista a continuación del nuevo nodo */
nuevo->siguiente = actual;
nuevo->anterior = NULL;
if(actual) actual->anterior = nuevo;
if(!*lista) *lista = nuevo;
}
else {
/* Avanzamos hasta el último elemento o hasta que el siguiente tenga
un valor mayor que v */
while(actual->siguiente &&actual->siguiente->valor <= v)
actual = actual->siguiente;
/* Insertamos el nuevo nodo después del nodo anterior */
nuevo->siguiente = actual->siguiente;
actual->siguiente = nuevo;
nuevo->anterior = actual;
if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo;
}
}
void Borrar(Lista *lista, int v) {
pNodo nodo;
/* Buscar el nodo de valor v */
nodo = *lista;
while(nodo && nodo->valor < v) nodo = nodo->siguiente;
while(nodo && nodo->valor > v) nodo = nodo->anterior;
/* El valor v no está en la lista */
if(!nodo || nodo->valor != v) return;
/* Borrar el nodo */
/* Si lista apunta al nodo que queremos borrar, apuntar a otro */
if(nodo == *lista)
if(nodo->anterior) *lista = nodo->anterior;
else *lista = nodo->siguiente;
if(nodo->anterior) /* no es el primer elemento */
nodo->anterior->siguiente = nodo->siguiente;
if(nodo->siguiente) /* no es el último nodo */
nodo->siguiente->anterior = nodo->anterior;
free(nodo);
}
void BorrarLista(Lista *lista) {
pNodo nodo, actual;
actual = *lista;
while(actual->anterior) actual = actual->anterior;
while(actual) {
nodo = actual;
actual = actual->siguiente;
free(nodo);
}
*lista = NULL;
}
void MostrarLista(Lista lista, int orden) {
pNodo nodo = lista;
if(!lista) printf("Lista vacía");
nodo = lista;
if(orden == ASCENDENTE) {
while(nodo->anterior) nodo = nodo->anterior;
printf("Orden ascendente: ");
while(nodo) {
printf("%d -> ", nodo->valor);
nodo = nodo->siguiente;
}
}
else {
while(nodo->siguiente) nodo = nodo->siguiente;
printf("Orden descendente: ");
while(nodo) {
printf("%d -> ", nodo->valor);
nodo = nodo->anterior;
}
}
printf("\n");
}
Page updated
Report abuse