Les escribiré un poco acerca de las listas enlazadas.
La lista enlazada es un tipo de estructura de datos que permite almacenar datos de forma organizada de igual manera que los vectores, con la diferencia de que ahora la estructura es dinámica, queriendo decir que no tenemos que saber los elementos que pueda contener. En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.
Este es un ejemplo gráfico de lo que es una lista simplemente enlazada:
Una lista simplemente enlazada tiene las siguientes características:
- Los elementos son contiguos en cuanto al enlazado.
- Los elementos están dispersos en la memoria.
- El enlace entre los elementos se hace por medio de un puntero.
- En la memoria la representación es aleatoria en función al espacio asignado.
- El puntero “siguiente” del último elemento debe apuntar hacia NULL (el fin de la lista)
- Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero “siguiente” permite el desplazamiento hacia el próximo elemento.
- El desplazamiento se hace en una sola dirección, del primer al último elemento.
A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.
I. Inserción en una lista vacía:
- Se asigna memoria para el nuevo elemento
- Se rellena el campo de datos del nuevo elemento
- El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero inicio que vale NULL)
- Los punteros inicio y fin apuntaran hacia el nuevo elemento
- El tamaño es actualizado
Aquí un ejemplo gráfico:
Código en C:
int ins_en_lista_vacia (Lista * lista, char *dato){
Element *nuevo_elemento;
if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nuevo _elemento->dato = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = NULL;
lista->inicio = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
II. Inserción al inicio:
- Se asigna memoria al nuevo elemento
- Rellenar el campo de datos del nuevo elemento
- El puntero siguiente del nuevo elemento apunta hacia el primer elemento
- El puntero inicio apunta hacia el nuevo elemento
- El puntero fin no cambia
- El tamaño es incrementado
Ejemplo gráfico:
Código en C:
int ins_inicio_lista (Lista * lista, char *dato){
Element *nuevo_elemento;
if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = lista->inicio
lista->inicio = nuevo_elemento;
lista->tamaño++;
return 0;
}
III. Inserción al final:
- Asignación de memoria al nuevo elemento
- Rellenar el campo de datos del nuevo elemento
- El puntero siguiente del ultimo elemento apunta hacia el nuevo elemento
- El puntero fin apunta hacia el nuevo elemento
- El puntero inicio no cambia
- El tamaño es incrementado
Ejemplo gráfico:
El código en C:
/*inserción al final de la lista */
int ins_fin_lista (Lista * lista, Element * actual, char *dato){
Element *nuevo_elemento;
if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
actual->siguiente = nuevo_elemento;
nuevo_elemento->siguiente = NULL;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
IV. Inserción en otra parte de la lista:
- Asignación de memoria al nuevo elemento
- Rellenar el campo de datos del nuevo elemento
- Elegir una posición en la lista (la inserción se hará después de haber elegido la posición)
- El puntero siguiente del nuevo elemento apunta hacia la dirección a la que apunta el puntero siguiente del elemento actual.
- El puntero siguiente del elemento actual apunta al nuevo elemento
- Los punteros inicio y fin no cambian
- El tamaño se incrementa en una unidad
Ejemplo gráfico:
Código en C:
int ins_lista (Lista * lista, char *dato, int pos){
if (lista->tamaño < 2)
return -1;
if (pos < 1 || pos >= lista->tamaño)
return -1;
Element *actual;
Element *nuevo_elemento;
int i;
if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
actual = lista->inicio;
for (i = 1; i < pos; ++i)
actual = actual->siguiente;
if (actual->siguiente == NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
lista->tamaño++;
return 0;
V. Eliminación al inicio de la lista:
- el puntero sup_elem contendrá la dirección del 1er elemento
- el puntero inicio apuntara hacia el 2do elemento
- el tamaño de la lista disminuirá un elemento
Ejemplo gráfico:
int sup_inicio (Lista * lista){
if (lista->tamaño == 0)
return -1;
Element *sup_elemento;
sup_element = lista->inicio;
lista->inicio = lista->inicio->siguiente;
if (lista->tamaño == 1)
lista->fin = NULL;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño--;
return 0;
}
VI. Eliminación en otra parte:
- el puntero sup_elem contendrá la dirección hacia la que apunta el puntero siguiente del elemento actual
- el puntero siguiente del elemento actual apuntara hacia el elemento al que apunta el puntero siguiente del elemento que sigue al elemento actual en la lista
*Si el elemento actual es el penúltimo elemento, el puntero fin debe ser actualizado
Ejemplo gráfico:
Código en C:
int sup_en_lista (Lista * lista, int pos){
if (lista->tamaño <= 1 || pos < 1 || pos >= lista->tamaño)
return -1;
int i;
Element *actual;
Element *sup_elemento;
actual = lista->inicio;
for (i = 1; i < pos; ++i)
actual = actual->siguiente;
sup_elemento = actual->siguiente;
actual->siguiente = actual->siguiente->siguiente;
if(actual->siguiente == NULL)
lista->fin = actual;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño--;
return 0;
}
VI. Visualización de la lista
- Para mostrar la lista entera hay que posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego utilizando el puntero siguiente de cada elemento la lista es recorrida del 1ero al último elemento.
La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL.
Código en C:
void visualización (Lista * lista){
Element *actual;
actual = lista->inicio;
while (actual != NULL){
printf ("%p - %s\n", actual, actual->dato);
actual = actual->siguiente;
}
}
Aquí les dejo una liga que encontré en dónde se puede descargar en un archivo .txt un código bastante completo en C de listas simplemente enlazadas, en dónde se pueden hacer las acciones anteriores:http://www.mediafire.com/?s6vab8x0sk4c7h8
Referencias:
Bien; 8.
ResponderEliminar