Listas en C

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 un puntero. 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 del 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. Si deseas desplazarte en las dos direcciones (hacia delante y 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 siguiente permitirá 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 struct ListaIdentificar {

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ño contendrá 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 y eliminació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;

}

Inserción de un elemento en la lista

A continuación el algoritmo de inserción y registro de los elementos:

• declaración del elemento a insertar

• asignación de la memoria para el nuevo elemento

• rellenar el contenido del campo de datos

• actualizar los punteros hacia el primer y ultimo elemento si es necesario.

• Caso particular: en una lista con un solo elemento, el primero es al mismo tiempo el último.

• Actualizar el tamaño de la lista

Para añadir un elemento a la lista hay varios casos:

• Inserción en una lista vacía

• Inserción al inicio de la lista

• Inserción al final de la lista

• Inserción en otra parte de la lista.

1. Inserción en una lista vacía

Ejemplo de la función:

int ins_en_lista_vacia (Lista *lista, char *dato);

La función devuelve 1 en caso de error, si no devuelve 0. Etapas:

• asignación de memoria para el nuevo elemento

• rellenar 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

La función

/* inserción en una lista vacía */

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;

}

2. Inserción al inicio de la lista

Ejemplo de la función:

int ins_inicio_lista (Lista *lista,char *dato);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• asignación de 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

La función

/* inserción al inicio de la lista */

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;

}

3. Inserción al final de la lista

Ejemplo de la función:

int ins_fin_lista (Lista *lista, Element *actual, char *dato);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• 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

La función

/*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;

}

4. Inserción en otra parte de la lista

Ejemplo de la función:

int ins_lista (Lista *lista, char *dato,int pos);

La función devuelve -1 en caso de error, si no devuelve 0. La inserción se efectuará después de haber pasado a la función una posición como argumento. Si la posición indicada no tiene que ser el último elemento. En ese caso hay que utilizar la función de inserción al final de la lista. Etapas:

• 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

La función

/* inserción en la posición solicitada */

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;

C. Eliminación de un elemento de la lista

A continuación un algoritmo para eliminar un elemento de la lista:

• uso de un puntero temporal para guardar la dirección de los elementos a eliminar

• el elemento a eliminar se encuentra después del elemento actual

Apuntar el puntero siguiente del elemento actual hacia la dirección del puntero siguiente del elemento a eliminar

• liberar la memoria ocupada por el elemento eliminado

• actualizar el tamaño de la lista

Para eliminar un elemento de la lista hay varios casos:

• Eliminación al inicio de la lista

• Eliminación en otra parte de la lista

1. Eliminación al inicio de la lista

Ejemplo de la función:

int sup_inicio (Lista *lista);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• 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

La función

/* eliminación al inicio de la lista */

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;

}

2. Eliminación en otra parte de la lista

Ejemplo de la función:

int sup_en_lista (Lista *lista, int pos);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• 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.

• el tamaño de la lista será disminuido en un elemento

La función

/* eliminar un elemento después de la posición solicitada */

int sup_en_lista (Lista * lista, int pos){

if (lista->tamaño = 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;

}

D. 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 ultimo elemento. La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL. La función

/* visualización de la lista */

void visualización (Lista * lista){

Element *actual;

actual = lista->inicio;

while (actual != NULL){

printf ("%p – %sn", actual, actual->dato);

actual = actual->siguiente;

}

}

E. Destrucción de la lista

Para destruir la lista entera, he utilizado la eliminación al inicio de la lista ya que el tamaño es mayor a cero. La función

/* destruir la lista */

void destruir (Lista * lista){

while (lista->tamaño > 0)

sup_inicio (lista);

}

V. Ejemplo completo

lista.h

/* ———- lista.h ———– */

typedef struct ElementoLista

{

char *dato;

struct ElementoLista *siguiente;

} Elemento;

typedef struct ListaIdentificar

{

Elemento *inicio;

Elemento *fin;

int tamaño;

} Lista;

/* inicialización de la lista */

void inicialización (Lista * lista);

/* INSERCION */

/* inserción en une lista vacía */

int ins_en_lista_vacia (Lista * lista, char *dato);

/* inserción al inicio de la lista */

int ins_inicio_lista (Lista * lista, char *dato);

/* inserción al final de la lista */

int ins_fin_lista (Lista * lista, Elemento * actual, char *dato);

/* inserción en otra parte */

int ins_lista (Lista * lista, char *dato, int pos);

/* SUPRESION */

int sup_inicio (Lista * lista);

int sup_en_lista (Lista * lista, int pos);

int menu (Lista *lista,int *k);

void muestra (Lista * lista);

void destruir (Lista * lista);

/* ——– FIN lista.h ——— */

lista _function.h

/***************************

* lista_function.h *

***************************/

void

inicialisacion (Lista * lista)

{

lista ->inicio = NULL;

lista ->fin = NULL;

lista ->tamaño = 0;

}

/* insercion en une lista vacia */

int ins_en_lista _vacia (Lista * lista, char *dato){

Elemento *nuevo_elemento;

if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == 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;

}

/* inserción al inicio de la lista */

int ins_inicio_lista (Lista * lista, char *dato){

Elemento *nuevo_elemento;

if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == 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;

}

/*insercion al final de la lista */

int ins_fin_lista (Lista * lista, elemento * actual, char *dato){

Elemento *nuevo_elemento;

if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == 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;

}

/* insercion en la posicion solicitada */

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;

Elemento *actual;

Elemento *nuevo_elemento;

int i;

if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == 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;

}

/* supresión al inicio de la lista */

int sup_inicio (Lista * lista){

if (lista ->tamaño == 0)

return -1;

Elemento *sup_elemento;

sup_elemento = 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;

}

/* suprimir un elemento después de la posición solicitada */

int sup_en_lista (Lista * lista, int pos){

if (lista ->tamaño = lista ->tamaño)

return -1;

int i;

Elemento *actual;

Elemento *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;

}

/* visualización de la Lista */

void muestra (Lista * lista){

Elemento *actual;

actual = lista ->inicio;

while (actual != NULL){

printf ("%p – %sn", actual, actual->dato);

actual = actual->siguiente;

}

}

/* destruir la Lista */

void destruir (Lista * Lista){

while (lista ->tamaño > 0)

sup_inicio (lista);

}

int menu (Lista *lista,int *k){

int elección;

printf("********** MENU **********n");

if (lista ->tamaño == 0){

printf ("1. Adición del1er elementon");

printf ("2. Quitarn");

}else if(lista ->tamaño == 1 || *k == 1){

printf ("1. Adición al inicio de la listan");

printf ("2. Adición al final de la listan");

printf ("4. Supresión al inicio de la listan");

printf ("6. Destruir la listan");

printf ("7. Quitarn");

}else {

printf ("1. Adición al inicio de la listan");

printf ("2. Adición al final de la listan");

printf ("3. Adición después de la posición indicadan");

printf ("4. Supresión al inicio de la listan");

printf ("5. Supresión después de la posición indicadan");

printf ("6. Destruir la listan");

printf ("7. Quitarn");

}

printf ("nnElegir: ");

scanf ("%d", &elección);

getchar();

if(lista->tamaño == 0 && elección == 2)

elección = 7;

return elección;

}

/* ——– FIN lista_function.h ——— */

lista.c

/**********************

* lista.c *

**********************/

#include

#include

#include

#include "lista.h"

#include "lista _function.h"

int main (void)

{

char elección;

char *nom;

Lista *lista;

Elemento *actual;

if ((lista = (Lista *) malloc (sizeof (Lista))) == NULL)

return -1;

if ((nom = (char *) malloc (50)) == NULL)

return -1;

actual = NULL;

elección = 'o';

inicialisacion (lista);

int pos, k;

while (elección!= 7){

elección = menu (lista, &k);

switch (elección){

case 1:

printf ("Ingrese un elemento : ");

scanf ("%s", nom);

getchar ();

if (lista->tamaño == 0)

ins_en_lista_vacia (lista, nom);

else

ins_inicio_lista (lista, nom);

printf ("%d elementos:ini=%s,fin=%sn", lista->tamaño,

lista->inicio->dato, lista->fin->dato);

muestra (lista);

break;

case 2:

printf ("Ingrese un elemento: ");

scanf ("%s", nom);

getchar ();

ins_fin_lista (lista, lista->fin, nom);

printf ("%d elementos:ini=%s,fin=%sn", lista->tamaño,

lista->inicio->dato, lista->fin->dato);

muestra (lista);

break;

case 3:

printf ("Ingrese un elemento: ");

scanf ("%s", nom);

getchar ();

do{

printf ("Ingrese la posicion: ");

scanf ("%d", &pos);

}

while (pos < 1 || pos > lista->tamaño);

getchar ();

if (lista->tamaño == 1 || pos == lista->tamaño){

k = 1;

printf("———————————————–n");

printf("/!\Fracaso la insercion.Utilice el menu {1|2} /!\n");

printf("———————————————–n");

break;

}

ins_lista (lista, nom, pos);

printf ("%d elementos:ini=%s,fin=%sn", lista->tamaño,

lista->inicio->dato, lista->fin->dato);

muestra (lista);

break;

case 4:

sup_inicio (lista);

if (lista->tamaño != 0)

printf ("%d elementos:ini=%s,fin=%sn", lista->tamaño,

lista->inicio->dato, lista->fin->dato);

else

printf ("lista vacian");

muestra (lista);

break;

case 5:

do{

printf ("Ingrese la posicion : ");

scanf ("%d", &pos);

}

while (pos < 1 || pos > lista->tamaño);

getchar ();

sup_en_lista (lista, pos);

if (lista->tamaño != 0)

printf ("%d elementos:ini=%s,fin=%sn", lista->tamaño,

lista->inicio->dato, lista->fin->dato);

else

printf ("lista vacian");

muestra (lista);

break;

case 6:

destruir (lista);

printf ("la lista ha sido destruida: %d elementosn", lista->tamaño);

break;

}

}

return 0;

}

Listas doblemente enlazadas

• Requisitos

• Introducción

• Definición

• La construcción del modelo de un elemento de la lista

• Operaciones sobre la lista doblemente enlazadas

• Inicialización

• Inserción de un elemento en la lista

• Inserción en una lista vacía

• Inserción al inicio de la lista

• Inserción al final de la lista

• Inserción antes de un elemento de la lista

• Inserción después de un elemento de la lista

• C. Eliminación de un elemento de la lista

• Eliminación en la lista

• D. Visualización de la lista

• E. Destrucción de la lista

• V. Ejemplo completo

• dlista.h

• dlista_function.h

• dlista.c

Requisitos

Los tipos de datos Las estructuras El uso de typedef Los punteros Las funciones usuario Las listas enlazadas simples

I. Introducción

El objetivo de este artículo es la comprensión de las listas doblemente enlazadas. Las listas doblemente enlazadas pueden ser utilizadas cuando son necesarias varias operaciones de inserción o eliminación de elementos.

II. Definición

Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples. La asignación de memoria es hecha al momento de la ejecución. En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista). El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista). Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:

• comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.

• comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.

Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al ultimo elemento y/o del ultimo al primer elemento.

III. La 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, un puntero anterior y un puntero siguiente. Los punteros anterior y siguiente deben ser del mismo tipo que el elemento, en caso contrario no podrán apuntar hacia un elemento de la lista. El puntero anterior permitirá el acceso hacia el elemento anterior mientras que el puntero siguiente permitirá el acceso hacia el próximo elemento.

typedef struct dl_ElementoLista {

char *dato;

struct dl_ElementoLista *anterior;

struct dl_ElementoLista *siguiente;

}dl_Elemento;

Para tener el control de la lista es preferible conservar algunos elementos: el primer elemento, el último elemento, el número de elementos. Para ello, será utilizada otra estructura (no es obligatorio, pueden ser utilizadas variables).

typedef struct dl_ListaIdentificacion {

dl_Elemento *inicio;

dl_Elemento *fin;

int tamaño;

}dl_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ño contendrá el numero de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.

IV. Operaciones sobre la lista doblemente enlazadas

Para la inserción y la eliminación, una solo función bastará si está bien concebida en función de las necesidades. Sin embargo, 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 y eliminación.

A. Inicialización

Modelo de la función:

void inicialización (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 inicialización (Liste *liste){

lista->inicio = NULL;

lista->fin = NULL;

tamaño = 0;

}

Inserción de un elemento en la lista

A continuación el algoritmo de inserción y registro de los elementos:

• declaración del elemento a insertar

• asignación de la memoria para el nuevo elemento

• rellenar el contenido del campo de datos

• actualizar los punteros hacia el elemento anterior y el elemento siguiente

• actualizar los punteros hacia el 1er y ultimo elemento si es necesario.

• Caso particular: en una lista con un solo elemento, el primero es al mismo tiempo el último.

• Actualizar el tamaño de la lista

Para añadir un elemento a la lista hay varias situaciones:

• Inserción en una lista vacía

• Inserción al inicio de la lista

• Inserción al final de la lista

• Inserción antes de un elemento

• Inserción después de un elemento

1. Inserción en una lista vacía

Modelo de la función:

int ins_en_lista_vacia (dl_Lista *lista, char *dato);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• asignación de memoria para el nuevo elemento

• rellenar el campo de datos del nuevo elemento

• el puntero anterior del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía utilizamos la dirección del puntero inicio que vale NULL)

• 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 fin que vale NULL)

• los punteros inicio y fin apuntaran hacia el nuevo elemento

• el tamaño es actualizado

La función

int insercion_en_lista_vacia (dl_Lista * lista, char *dato){

dl_Elemento *nuevo_elemento;

if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

return -1;

strcpy (nuevo_elemento->dato, dato);

nuevo_elemento->anterior = lista->inicio;

nuevo_elemento->siguiente = lista->fin;

lista->inicio = nuevo_elemento;

lista->fin = nuevo_elemento;

lista->tamaño++;

return 0;

}

2. Inserción al inicio de la lista

Modelo de la función:

int ins_inicio_lista(dl_Lista * lista, char *dato);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• asignación de memoria al nuevo elemento

• rellenar el campo de datos del nuevo elemento

• el puntero anterior del nuevo elemento apunta hacia NULL

• el puntero siguiente del nuevo elemento apunta hacia el 1er elemento

• el puntero anterior del 1er elemento apunta hacia el nuevo elemento

• el puntero inicio apunta hacia el nuevo elemento

• el puntero fin no cambia

• el tamaño es incrementado

La función

int ins_inicio_lista(dl_Lista * lista, char *dato){

dl_Elemento *nuevo_elemento;

if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

return -1;

strcpy (nuevo_elemento->dato, dato);

nuevo_elemento->anterior = NULL;

nuevo_elemento->siguiente = lista->inicio;

lista->inicio->anterior = nuevo_elemento;

lista->inicio = nuevo_elemento;

lista->tamaño++;

return 0;

}

3. Inserción al final de la lista

Modelo de la función:

int ins_fin_lista(dl_Lista * lista, char *dato);

La función devuelve -1 en caso de error, si no devuelve 0. Etapas:

• asignación de memoria al nuevo elemento

• rellenar el campo de datos del nuevo elemento

• el puntero siguiente del nuevo elemento apunta hacia NULL

• el puntero anterior del nuevo elemento apunta hacia el ultimo elemento (es el puntero fin que contiene por ahora su dirección)

• el puntero siguiente del ultimo elemento apuntará hacia el nuevo elemento

• el puntero fin apunta hacia el nuevo elemento

• el puntero inicio no cambia

• el tamaño es incrementado

La función

int ins_fin_lista(dl_Lista * lista, char *dato){

dl_Elemento *nuevo_elemento;

if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)

return -1;

strcpy (nuevo_elemento->dato, dato);

nuevo_elemento->siguiente = NULL;

nuevo_elemento->anterior = lista->fin;

lista->fin->siguiente = nuevo_elemento;

lista->fin = nuevo_elemento;

lista->tamaño++;

return 0;

}

4. Inserción antes de un elemento de la lista

Modelo de la función:

int ins_antes (dl_Lista * lista, char *dato, int pos);

La función devuelve -1 en caso de error, si no devuelve 0. La inserción se efectuara antes de cierta posición pasado como argumento a la función. La posición indicada no debe ser ni el primer ni el último elemento. En ese caso hay que utilizar las funciones de inserción al inicio y/o al final de la lista. Etapas:

• 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 la posición elegida)

• el puntero siguiente del nuevo elemento apunta hacia el elemento actual.

• el puntero anterior del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero anterior del elemento actual.

Partes: 1, 2