Embedded Files
Con las listas tendremos un pequeño repertorio de operaciones básicas que se pueden realizar:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar un nodo en una lista vacía, o al principio de una lista no vacía, o la final, o en una posición intermedia.
Insertar elementos en una lista
Insertar elementos en una lista
Veremos primero los casos sencillos y finalmente construiremos un algoritmo genérico para la inserción de elementos en una lista.
Insertar un elemento en una lista vacía
Insertar un elemento en una lista vacía
Este es, evidentemente, el caso más sencillo. Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la lista valdrá NULL:
El proceso es muy simple, bastará con que:
nodo->siguiente apunte a NULL.
Lista apunte a nodo.
Insertar un elemento en la primera posición
Insertar un elemento en la primera posición
Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que en el caso anterior la lista es una lista vacía, pero siempre podemos, y debemos considerar una lista vacía como una lista. De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso no vacía:
El proceso sigue siendo muy sencillo:
Hacemos que nodo->siguiente apunte a Lista.
Hacemos que Lista apunte a nodo.
Insertar un elemento en la última posición
Insertar un elemento en la última posición
Este es otro caso especial. Para este caso partiremos de una lista no vacía:
El proceso en este caso tampoco es excesivamente complicado:
Necesitamos un puntero que señale al último elemento de la lista. La manera de conseguirlo es empezar por el primero y
avanzar hasta que el nodo que tenga como siguiente el valor NULL.
Hacer que nodo->siguiente sea NULL.
Hacer que ultimo->siguiente sea nodo.
Insertar un elemento a continuación de un nodo cualquiera
Insertar un elemento a continuación de un nodo cualquiera
De nuevo podemos considerar el caso anterior como un caso particular de este. Ahora el nodo "anterior" será aquel a continuación del cual insertaremos el nuevo nodo:
Suponemos que ya disponemos del nuevo nodo a insertar, apuntado por nodo, y un puntero al nodo a continuación del que lo insertaremos.
El proceso a seguir será:
Hacer que nodo->siguiente señale a anterior->siguiente.
Hacer que anterior->siguiente señale a nodo.
Localizar elementos
Localizar elementos
Muy a menudo necesitaremos recorrer una lista, ya sea buscando un valor particular o un nodo concreto. Las listas abiertas sólo pueden recorrerse en un sentido, ya que cada nodo apunta al siguiente, pero no se puede obtener, por ejemplo, un puntero al nodo anterior desde un nodo cualquiera si no se empieza desde el principio.
Para recorrer una lista procederemos siempre del mismo modo, usaremos un puntero auxiliar como índice:
Asignamos al puntero índice el valor de Lista.
Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.
Dentro del bucle asignaremos al índice el valor del nodo siguiente al índice actual.
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
...
pNodo indice;
...
indice = Lista;
while(indice) {
printf("%d\n", indice->dato);
indice = indice->siguiente;
}
...
Supongamos que sólo queremos mostrar los valores hasta que encontremos uno que sea mayor que 100, podemos sustituir el bucle por:
...
indice = Lista;
while(indice && indice->dato <= 100) {
printf("%d\n", indice->dato);
indice = indice->siguiente;
}
...
Si analizamos la condición del bucle, tal vez encontremos un posible error: ¿Qué pasaría si ningún valor es mayor que 100, y alcancemos el final de la lista?. Podría pensarse que cuando indice sea NULL, si intentamos acceder a indice->dato se producirá un error.
En general eso será cierto, no puede accederse a punteros nulos. Pero en este caso, ese acceso está dentro de una condición y forma parte de una expresión "and". Recordemos que cuando se evalúa una expresión "and", se comienza por la izquierda, y la evaluación se abandona cuando una de las expresiones resulta falsa, de modo que la expresión "indice->dato <= 100" nunca se evaluará si indice es NULL.
Si hubiéramos escrito la condición al revés, el programa nunca funcionaría bien. Esto es algo muy importante cuando se trabaja con punteros.
Eliminar elementos en una lista
Eliminar elementos en una lista
En todos los demás casos, eliminar un nodo se puede hacer siempre del mismo modo. Supongamos que tenemos una lista con al menos dos elementos, y un puntero al nodo anterior al que queremos eliminar. Y un puntero auxiliar nodo.
El proceso es parecido al del caso anterior:
Hacemos que nodo apunte al nodo que queremos borrar.
Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: anterior->siguiente = nodo->siguiente.
Eliminamos la memoria asociada al nodo que queremos eliminar.
Si el nodo a eliminar es el último, es procedimiento es igualmente válido, ya que anterior pasará a ser el último, y anterior->siguiente valdrá NULL.
Código del ejemplo completo
Código del ejemplo completo
#include <stdlib.h>
#include <stdio.h>
typedef struct _nodo {
int valor;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
/* Funciones con listas: */
void Insertar(Lista *l, int v);
void Borrar(Lista *l, int v);
int ListaVacia(Lista l);
void BorrarLista(Lista *);
void MostrarLista(Lista l);
int main() {
Lista lista = NULL;
pNodo p;
Insertar(&lista, 20);
Insertar(&lista, 10);
Insertar(&lista, 40);
Insertar(&lista, 30);
MostrarLista(lista);
Borrar(&lista, 10);
Borrar(&lista, 15);
Borrar(&lista, 45);
Borrar(&lista, 30);
Borrar(&lista, 40);
MostrarLista(lista);
BorrarLista(&lista);
return 0;
}
void Insertar(Lista *lista, int v) {
pNodo nuevo, anterior;
/* Crear un nodo nuevo */
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->valor = v;
/* Si la lista está vacía */
if(ListaVacia(*lista) || (*lista)->valor > v) {
/* Añadimos la lista a continuación del nuevo nodo */
nuevo->siguiente = *lista;
/* Ahora, el comienzo de nuestra lista es en nuevo nodo */
*lista = nuevo;
} else {
/* Buscar el nodo de valor menor a v */
anterior = *lista;
/* Avanzamos hasta el último elemento o hasta que el siguiente tenga
un valor mayor que v */
while(anterior->siguiente && anterior->siguiente->valor <= v)
anterior = anterior->siguiente;
/* Insertamos el nuevo nodo después del nodo anterior */
nuevo->siguiente = anterior->siguiente;
anterior->siguiente = nuevo;
}
}
void Borrar(Lista *lista, int v) {
pNodo anterior, nodo;
nodo = *lista;
anterior = NULL;
while(nodo && nodo->valor < v) {
anterior = nodo;
nodo = nodo->siguiente;
}
if(!nodo || nodo->valor != v) return;
else { /* Borrar el nodo */
if(!anterior) /* Primer elemento */
*lista = nodo->siguiente;
else /* un elemento cualquiera */
anterior->siguiente = nodo->siguiente;
free(nodo);
}
}
int ListaVacia(Lista lista) {
return (lista == NULL);
}
void BorrarLista(Lista *lista) {
pNodo nodo;
while(*lista) {
nodo = *lista;
*lista = nodo->siguiente;
free(nodo);
}
}
void MostrarLista(Lista lista) {
pNodo nodo = lista;
if(ListaVacia(lista)) printf("Lista vacía\n");
else {
while(nodo) {
printf("%d -> ", nodo->valor);
nodo = nodo->siguiente;
}
print("\n");
}
}
Page updated
Report abuse