listas simples

La lista enlazada simple
Junio 2014

La lista enlazada simple

Pre-requisitos
I. Introducción
II. Definición
III. Construcción del modelo de un elemento de la lista
IV. Operaciones sobre las listas enlazadas
A. Inicialización
B. Inserción de un elemento en la lista
1. Inserción en una lista vacía
2. Inserción al inicio de la lista
3. Inserción al final de la lista
4. Inserción enotra parte de la lista
C. Eliminación de un elemento de la lista
1. Eliminación al inicio de la lista
2. Eliminación en otra parte de la lista
D. Visualización de la lista
E. Destrucción de la lista

V. Ejemplo completo
lista.h
lista _function.h
lista.c
VI. Ver también

Pre-requisitos
Los tipos de datos Las estructuras El uso de typedef Los punteros Las funciones usuario

I.Introducción
El objetivo de este artículo es el de comprender el uso de las listas enlazadas simples. Las listas
enlazadas pueden ser utilizadas cuando se necesitan hacer varias operaciones de inserción y
eliminación de elementos.

II. Definición
Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un
elemento no se hace mediante un indice sino mediante unpuntero. La asignación de memoria
es hecha durante la ejecución. En una lista los elementos son contiguos en lo que concierne al
enlazado.

En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista
los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero. En
realidad, en la memoria la representación es aleatoria en función delespacio 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. Si deseas desplazarte en las dos direcciones (hacia delantey
hacia atrás) deberás utilizar las [ listas doblemente enlazadas]

III. Construcción del modelo de un elemento de la lista
Para definir un elemento de la lista, será utilizado el tipo struct. El elemento de la lista contendrá
un campo dato y un puntero siguiente. El puntero siguiente debe ser del mismo tipo que el

elemento, si no, no podrá apuntar hacia el elemento. El puntero siguientepermitirá el acceso al
próximo elemento.
typedef struct ElementoLista {
char
*dato;
struct ElementoLista *siguiente;
}Elemento;
Para tener el control de la lista es preferible guardar ciertos elementos: El primer elemento, el
último elemento, el número de elementos. Para ello será utilizado otra estructura (no es
obligatorio, pueden ser utilizadas variables)
typedef structListaIdentificar {
Elemento *inicio;
Elemento *fin;
int tamaño;
}Lista;
El puntero inicio contendrá la dirección del primer elemento de la lista. El puntero fin contendrá
la dirección del último elemento de la lista. La variable tamaño contiene el número de
elementos. Cualquiera que sea la posición en la lista, los punteros inicio y fin apuntan siempre
al primer y último elemento. El campo tamañocontendrá el numero de elementos de la lista
cualquiera que sea la operación efectuada sobre la lista.

IV. Operaciones sobre las listas enlazadas
Para la inserción y la eliminación, una solo función bastará si está bien concebida de acuerdo a
lo que se necesite. Debo recordar que este artículo es puramente didáctico. Por esta razón he
escrito una función para cada operación de inserción yeliminación.

A. Inicialización
Modelo de la función:
void inicializacion (Lista *lista);
Esta operación debe ser hecha antes de cualquier otra operación sobre la lista. Esta inicializa el
puntero inicio y el puntero fin con el puntero NULL, y el tamaño con el valor 0. La función
void inicializacion (Lista *lista){
lista->inicio = NULL;
lista->fin = NULL;
tamaño = 0;
}

B. Inserción de un...