Listas enlazadas

Definicion

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]

Una lista enlazada tiene un conjunto de nodos, los cuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior.

Construir una 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.

Una lista es una estructura de datos que nos permite agrupar elementos de una manera organizada. Las listas al igual que los algoritmos son importantísimas en la computación y críticas en muchos programas informáticos.

Las listas están compuestas por nodos, estos nodos tienen un dato o valor y un puntero a otro(s) nodo(s).

Existen varios tipos de listas: Simplemente enlazada, doblemente enlazada, circular simplemente enlazada, circular doblemente enlazada.

Vamos a revisar las listas enlazadas simples, por ser el punto de partida y fundamentales para poder entender las otras.

Aquí una ejemplo de un lista enlazada simple.

01 En cristiano:
02 55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL
03
04 Internamente:
05 Nodo-> Dato: 55 Direcion: 0x3d2c00 Siguiente: 0x3d2c80
06 Nodo-> Dato: 60 Direcion: 0x3d2c80 Siguiente: 0x3d2c90
07 Nodo-> Dato: 31 Direcion: 0x3d2c90 Siguiente: 0x3d2ca0
08 Nodo-> Dato: 5  Direcion: 0x3d2ca0 Siguiente: 0x3d2cb0
09 Nodo-> Dato: 4  Direcion: 0x3d2cb0 Siguiente: 0x3d2cc0
10 Nodo-> Dato: 51 Direcion: 0x3d2cc0 Siguiente: 0x3d3ab8
11 Nodo-> Dato: 9  Direcion: 0x3d3ab8 Siguiente: 0x3d3ac8
12 Nodo-> Dato: 27 Direcion: 0x3d3ac8 Siguiente: 0x3d3ad8
13 Nodo-> Dato: 68 Direcion: 0x3d3ad8 Siguiente: 0x3d3ae8
14 Nodo-> Dato: 62 Direcion: 0x3d3ae8 Siguiente: 0

Obviamente, internamente no existen las palabras nodo, dato,dirección y siguiente, es solo una representación.

Como una lista es una estructura de datos dinámica, el tamaño de la misma puede cambiar durante la ejecución del programa.

Como vimos en post anteriores, se puede generar memoria dinámicamente para un array, pero un array es una estructura estática pues su tamaño tiene un limite y así creáramos array dinámicos hay que redimensionar el tamaño si es necesario, lo cual ya implica un costo de volver a generar memoria dinámica.

Entonces podemos ver una ventaja de la listas sobre los arrays: No tener que redimensionar la estructura y poder agregar elemento tras elemento indefinidamente.

Cuando uno ya ha trabajado con arrays (vectores y matrices) y empieza a estudiar las listas, se da cuenta que una restricción de las listas es el acceso a los elementos. En un vector podíamos hacer algo como v[50] y nos estábamos refiriendo al índice 50 del vector v. A esto se le conoce como acceso aleatorio.

En el caso de las listas el acceso es secuencial, es decir, para acceder a un elemento del conjunto debemos de recorrer uno por uno los elementos hasta llegar al solicitado. Rápidamente se puede concluir que el tiempo de acceso a los elementos de un array es muchísimo más rápido que en una lista. Esta es una gran desventaja de las listas, por lo que buscar elementos por índice sería muy costoso. Esto no quiere decir que trabajar con arrays sea mejor que con listas. Las listas son muy flexibles y para muchos casos son imprescindibles.

Bueno, aquí va la primera práctica que hice sobre listas enlazadas. Implementación de una clase Lista, clase Nodo y los siguientes métodos:

  • Añadir un elemento al inicio.
  • Añadir un elemento al final
  • Añadir un elemento de manera ordenada
  • Llenar la lista por teclado
  • Llenar la lista aleatoriamente
  • Imprimir la lista
  • Buscar un elemento
  • Eliminar un elemento por dato
  • Eliminar un elemento por posicion o índice
  • Eliminar toda la lista
  • Invertir una lista
  • Ordernar una lista
  • Cargar una lista desde archivo
  • Guardar la lista en un archivo
  • Concatenar una lista a otra
  • Intersección entre 2 listas

Podrán ver la variable *temp en casi todos los métodos , este es el puntero de tipo Nodo que me va a permitir moverme a través de la lista y que inicialmente es igual a la cabeza (head). Mientras exista algo en la lista, voy avanzado el puntero para que apunte al siguiente. Esto se consigue en casi todos los casos con un while.

While(temp)
temp = temp->gte

Otra operación común en los métodos es preguntar si inicialmente la lista está vacía, es decir, si la cabeza no contiene algo o es igual a Null.

if(!head) o if(head==NULL)

Manejo de 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. 

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 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:

  • 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 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 punterosiguiente 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:

  • 1. Eliminación al inicio de la lista
  • 2. 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 elementoactual
  • el puntero siguiente del elemento actual apuntara hacia el elemento al que apunta el punterosiguiente 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 <= 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;
}

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 - %s\n", 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);
}
Pueden ver el codigo completo aplicando todos los manejos y operaciones con listas enlazadas y depues subire una hecha por mi :'D.

Referencias
http://es.kioskea.net/faq/2842-la-lista-enlazada-simple
http://ronnyml.wordpress.com/2009/07/04/listas-enlazadas-clase-lista-en-c/

1 comentario (+¿añadir los tuyos?)

  1. Elisa Schaeffer
    Jul 07, 2011 @ 13:37:28

    Muy completo; 10.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: