lunes, 20 de diciembre de 2010

Listas enlazadas simples

Hola, hace un tiempo publiqué un ejemplo de lista enlazada simple:

http://alguienenlafisi.blogspot.com/2010/12/lista-enlazada-simple-en-cc.html

Tubo más visitas de las que imaginé, así que ahora les dejo la explicación más detallada de cada operación y como se implementa. Si no se entiende algo del código pueden visitar este link:

http://alguienenlafisi.blogspot.com/2010/12/cc-para-estructuras-de-datos.html

Espero que sea útil y disculpen las faltas ortográficas xD

Listas enlazadas simples

Las listas simples están formadas por nodos con un solo enlace. Este enlace hace referencia al siguiente nodo de la lista o a NULL si es el ultimo nodo. NULL es un valor que representa que la referencia esta vacía. Debido a que poseen una sola referencia el recorrido de las listas simples es en una sola dirección: del primero hacia el ultimo. No es posible ir de un nodo al nodo anterior.


1 Implementación de una lista simple

Para implementar una lista primero debemos definir su nodo. Podemos definir el nodo como una estructura con dos campos: uno para almacenar el valor o la data del nodo y el otro para almacenar la dirección del siguiente nodo. El primer campo puede ser un tipo de dato elemental o una estructura. El segundo debe ser un puntero a una estructura nodo. Veamos:


En código:

struct nodo {
 int data; //almacena la data (un entero en este caso)
 nodo *sgte; //almacena la dirección de otro nodo
};

Una lista se maneja mediante un puntero al primer nodo de la lista. A este puntero se le conoce como cabecera y se declara en la función principal (main). Inicialmente, cuando la lista esta vacía, la cabecera debe de tener el valor NULL. Veamos:

int main() {
 nodo *cab = NULL; //declaración de la cabecera de la lista
 return 0;
}

Por medio de la cabecera podemos acceder a todos los nodos de la lista de la siguiente manera: como la cabecera apunta al primer elemento, accedemos su campo sgte y encontramos la dirección del segundo elemento luego accedemos al campo sgte del segundo elemento y encontramos la dirección del tercero. Así sucesivamente hasta que el campo sgte de un elemento sea igual a NULL entonces diremos que este es el ultimo elemento y que la lista ha terminado.

2 Operaciones sobre una lista simple

Las operaciones sobre una lista las implementamos mediante funciones que reciben como parámetro la cabecera de la lista sobre la que queremos trabajar entre otros parámetros dependiendo de la operación. Ahora veamos las operaciones básicas que se pueden realizar sobre una lista enlazada simple.

2.1 Recorrido de la lista

Esta operación es la mas sencilla de todas y consiste en ir desde el primer elemento de la lista hacia el ultimo. El propósito de esta operación es variado, se puede usar por ejemplo para contar cuantos elementos tiene la lista o para mostrar la data de todos los elementos.

Para recorrer la lista definiremos una función que reciba por parámetro la dirección del primer elemento de la lista (la cabecera). Luego habrá que validar si la lista esta vacía, es decir si la cabecera apunta a NULL. En caso este vacía podemos mostrar un mensaje informando ello y terminar la función. Si no, iniciaremos el recorrido: declaramos un puntero “p” al primer elemento igualándolo a la cabecera. Lo que sigue es un proceso iterativo: asignamos a p el valor del campo sgte del nodo apuntado por p (p=p->sgte), es decir p apuntará al siguiente elemento de la lista y repetimos este proceso mientras que p sea diferente de NULL. Al llegar al ultimo elemento el campo sgte será NULL, p tomará ese valor y la función terminará.

En código:

//Función para recorrer una lista y mostrar la data.
void recorrer(nodo *cab){ 
 //verifica si la lista esta vacía
 if(cab == NULL){
  //si esta vacía muestra este mensaje
  cout<<"La lista esta vacia."<<endl;
 } 
 else{ 
  //si no esta vacía declara un puntero p al primer elemento de la lista 
  nodo *p = cab;
  do{ 
   //muestra la data del nodo referido por p
   cout<<"Elemento: "<<p­->data<<endl;
   //asigna a p la dirección de nodo siguiente o NULL si no lo hay
   p = p­->sgte;
   //repite el proceso mientras p sea diferente de NULL
  }while(p != NULL);
  cout<<"Fin del recorrido."<<endl; 
 } 
}

2.2 Insertar un elemento a la lista

La inserción de un elemento puede hacerse de tres maneras: Inserción por el final, inserción por el inicio e inserción en la posición enésima. En todas la idea es crear un nuevo nodo con la data que se recibe por parámetro y enlazarlo con la lista. Veamos las tres formas de inserción.

2.2.1 Inserción por el final

Consiste en enlazar el ultimo nodo de la lista al nodo nuevo. Para ello primero evaluamos si la lista esta vacía. Si esta vacía hacemos que la cabecera apunte al nuevo nodo y terminamos. Si la lista no esta vacía la recorremos hasta llegar al ultimo elemento y modificamos su campo sgte para que apunte al nuevo nodo. El campo sgte del nuevo nodo debe ser igual a NULL.

Importante: Para modificar el valor al que apunta la cabecera debemos pasar la cabecera por referencia. Pero como la cabecera es un puntero, para recibir la dirección de memoria de un puntero usaremos en los parámetros de la función un puntero a puntero.

En código:

//Función que inserta un nodo nuevo al final de la lista
void insertarFinal(nodo **pcab, int data){ 
 //crea un nuevo nodo dinámicamente e inicia sus campos
 nodo *nuevo = new nodo; 
 nuevo->data = data; 
 nuevo->sgte = NULL; 
 
 //valida si la lista esta vacia (pcab apunta a la cabecera osea pcab==&cab)
 if(*pcab == NULL){
  //modifica la cabecera para que apunte al nuevo nodo 
  *pcab = nuevo; 
 } 
 else{ 
  //declara un puntero p que apunta al primer nodo (p==cab)
  nodo *p = *pcab; 
  //avanza p hasta que llega al ultimo nodo (el que tiene NULL en sgte)
  while(p->sgte != NULL){ 
   p = p->sgte; 
  } 
  //asigna la dirección del nuevo nodo al campo sgte del ultimo nodo
  p->sgte = nuevo; 
 } 
}

2.2.2 Inserción por el inicio

Consiste en enlazar el nuevo nodo al primer nodo de la lista y modificar la cabecera para que apunte al nuevo nodo. También es necesario pasar la cabecera por referencia.

En código:

//Funcion que inserta un nodo nuevo al inicio de la lista
void insertarInicio(nodo **pcab, int data){ 
 //crea un nodo nuevo
 nodo *nuevo = new nodo; 
 //inicia el campo data del nuevo nodo con la data recibida por parámetro
 nuevo->data = data; 
 //asigna al campo sgte del nuevo nodo el valor de la cabecera (*pcab==cab)
 //si la lista esta vacia (cab==NULL) sgte sera NULL
 //si la lista no esta vacia sgte apuntara al primer elemento
 nuevo->sgte = *pcab; 
 //modifica la cabecera para que apunte al nuevo nodo
 //el nuevo nodo sera ahora el primero
 *pcab = nuevo; 
}

2.2.3 Inserción en la posición enésima

En esta función se recibe además un índice “n” que indica la posición en que será insertado el nuevo nodo (0 es la primera posición convencionalmente).

Primero contaremos el numero de nodos de la lista para poder validar si el índice es correcto, esto lo podemos hacer dentro de la misma función o en una función aparte. Luego de validar que el índice esté entre cero y el número de nodos, evaluamos 3 casos bien definidos:
  • El primero es que el indice sea 0, es decir se inserta al inicio. En este caso podemos llamar a la función insertarInicio() definida anteriormente.
  • El segundo caso es que el índice sea igual al numero de nodos, es decir se inserta al final de la lista. Podemos llamar a la función insertarFinal() ya explicada.
  • En el tercer caso el índice estará en la zona intermedia de la lista.
Para insertar en el tercer caso declaramos un puntero “p” que apunte inicialmente al primer elemento y hacemos que avance hasta llegar a una posición antes de la posición en la que queremos insertar. Luego creamos el nuevo nodo y asignamos a su campo sgte la dirección almacenada en el campo sgte de p. Finalmente modificamos el campo sgte de p para que apunte al nuevo nodo.

En código:

//Función que inserta un nodo nuevo en la posición enésima
void insertarEnN(nodo **pcab, int data, int n){ 
 //contamos el numero de nodos de la lista
 int nNodos = contarNodos(*pcab); 
 //validamos que el índice n este en un rango valido
 if(n > nNodos || n < 0){ 
  //si no esta, mostramos un mensaje de error
  cout<<"Posicion no valida. Hay "<<nNodos<<" nodos en la lista"<<endl; 
 } 
 //si n es 0 (primera posición) llamamos a insertarInicio() 
 else if(n == 0){ 
  insertarInicio(pcab, data); 
 } 
 //si n es igual al numero de nodos (ultima posición) llamamos a insertarFinal()
 else if(n == nNodos){ 
  insertarFinal(pcab, data); 
 }
 //En este caso n debe estar en la zona intermedia de la lista 
 else{ 
  //declaramos un puntero p al primer elemento de la lista
  nodo *p = *pcab;
  //avanzamos p hasta la posición n-1
  for(int i=0; i<n-1; i++) 
   p = p->sgte; 
  //creamos el nuevo nodo e iniciamos su data
  nodo *nuevo = new nodo; 
  nuevo->data = data; 
  //el campo sgte del nuevo elemento apuntara al nodo siguiente de p
  nuevo->sgte = p->sgte; 
  //el campo sgte de p apuntara al nuevo nodo
  p->sgte = nuevo; 
 } 
}

//Función que devuelve el numero de nodos de una lista.
int contarNodos(nodo *cab){ 
 int cont = 0; 
 while(cab!=NULL){ 
  cab = cab->sgte; 
  cont++; 
 } 
 return cont; 
}

2.3 Buscar un elemento

Esta operación consiste en recorrer la lista comparando la información que almacenan los nodos con la información buscada. Por ejemplo, en una lista de alumnos nos puede interesar programar una función de búsqueda por código de alumno, en este caso compararemos el código buscado con el código que almacenan los nodos. Al encontrar una coincidencia se devuelve la dirección del nodo que contiene la información buscada.

En código:

//Función que busca un nodo y devuelve una referencia al nodo.
//Si no lo encuentra devuelve NULL. 
nodo *buscar(nodo *cab, int data){ 
 //valida si la lista esta vacia 
 if(cab == NULL){ 
  cout<<"La lista esta vacia."<<endl; 
 } 
 else{ 
  //declara un puntero p al primer elemento de la lista 
  nodo *p = cab; 
  do{ 
   //valida si la data del nodo es la data buscada 
   if(p->data == data){ 
    //devuelve la referencia al nodo y termina la función 
    return p; 
   } 
   else{ 
    //p apunta al siguiente nodo 
    p = p->sgte; 
   } 
  //se repite mientras no se llegue al final de la lista 
  }while(p!=NULL); 
 } 
 //si termina la lista y no encontro el nodo buscado retorna NULL 
 return NULL; 
}

2.4 Eliminar un elemento de la lista

La eliminación de un elemento consiste retirarlo de la lista sin alterar su funcionamiento normal, es decir se debe redireccionar los enlaces de los elementos contiguos al elemento eliminado de modo que aún sea posible recorrer la lista sin problemas. Una vez fuera de la lista se debe liberar el espacio de memoria del elemento eliminado.

En código:

//Función que elimina un nodo usando como criterio de busqueda la data del nodo. 
void eliminar(nodo **pcab, nodo *n){ 
 //valida si la lista esta vacia 
 if(*pcab == NULL){ 
  cout<<"La lista esta vacia."<<endl; 
 } 
 else{ 
  //valida si el nodo a eliminar existe 
  if(n != NULL){ 
   //valida si el nodo a eliminar es el primero 
   if(n == *pcab){ 
    //hace que la cabecera apunte al segundo elemento 
    *pcab = (*pcab)->sgte; 
   } 
   else{ 
    //declara un puntero p al primer elemento de la lista 
    nodo *p = *pcab; 
    //hace que p apunte al nodo anterior al que se va a eliminar 
    while(p->sgte!=NULL && p->sgte!=n){ 
     p = p->sgte; 
    } 
    //enlaza al nodo anterior con el siguiente 
    p->sgte = n->sgte; 
   } 
   //libera el espacio de memoria del nodo eliminado 
   delete n; 
   cout<<"El elemento se ha eliminado correctamente."<<endl; 
  } 
  else{ 
   cout<<"No se encontro el elemento."<<endl; 
  } 
 } 
}

Actualización:

Por otra parte, si lo que deseamos el eliminar un nodo según su posición dentro de la lista, haremos lo siguiente: primero debemos validar que la posición del nodo a eliminar esté entre 1 y el número de nodos de la lista; luego se debe hacer un recorrido de la lista hasta la posición indicada a fin de obtener un puntero al nodo que deseamos retirar, en ese mismo recorrido también debemos conseguir otro puntero hacia el nodo anterior; por último se procede de forma similar al ejemplo anterior.

//Función que elimina el enesimo elemento de la lista
void eliminarPos(nodo **pcab, int pos) {
  //obtiene el numero de elementos
  int n = contarNodos(*pcab);
  //valida si la posicion esta en el rango [1,n]
  if( pos < 1 || pos > n ) {
   cout<<"Posicion "<<pos<<" no valida. Hay "<<n<<" elementos en la lista."<<endl;
  } else {
   //declara un puntero "p" al primer nodo y un puntero auxiliar "q"
   nodo *p = *pcab, *q;
   //avanza el puntero "p" hasta la posicion indicada
   //"q" debe quedar una posicion antes
   for(int i=1; i<pos; i++) {
    q = p;
    p = p->sgte;
   }
   //si el nodo a eliminar es el primero
   if(p == *pcab) {
    //se avanza la cabecera al siguiente elemento
    *pcab = (*pcab)->sgte;
   } else {
    //enlaza el nodo anterior con el nodo siguiente
    q->sgte = p->sgte;
   }
   //libera la memoria del nodo eliminado
   delete p;
   cout<<"El elemento se ha eliminado correctamente."<<endl;
  }
}

17 comentarios:

  1. wow me ayudo mucho, muchas gracias

    ResponderEliminar
  2. ushhhhhh gracias amigo :)

    ResponderEliminar
  3. y una función eliminar nodo.. pero con criterio de un numero.. eje:
    Si recibe 1 (uno) elimina el primer elemento, si recibo 5 elimina el quinto elemento, etc. Si el número que recibe como parámetro es mayor a la cantidad de nodos en la lista que avise al usuario que el número es mayor a la cantidad de nodos.

    ResponderEliminar
  4. Hola Oscar, actualicé el post, revisalo

    Saludos.

    ResponderEliminar
    Respuestas
    1. muchísimas gracias y saludos desde paraguay...
      http://www.facebook.com/oskarwsantacruz
      añademe.. un amigo como vos.. nunca esta de mas =)

      Eliminar
  5. me puedes explicar exactamente que hace la flechita
    q->sgte = p->sgte;

    ResponderEliminar
  6. Imagina que tienes esta lista enlazada:

    |A|-->|B|-->|C|-->|D|-->|E|

    y quieres borrar el nodo C. Segun el algoritmo recorres el vector hasta tener a "*p" apuntando a "C" y a "*q" apuntando a "B" (un nodo antes)

    Con la instruccion "q->sgte = p->sgte", asignas como nodo siguiente de "B", el nodo siguiente de "C", es decir "D". Por lo que la nueva lista quedaría así:

    |A|-->|B|-->|D|-->|E|

    Luego ya puedes liberar la memoria del nodo C.

    Saludos.

    ResponderEliminar
  7. muchas gracias muy util desde nicaragua

    ResponderEliminar
  8. Entendi la gran mayoria pero no puede implementarlo en el main
    una pregunta es simplemente enlazada solamente vdd

    ResponderEliminar
  9. Sí, es una lista simple, es decir un nodo solo esta enlazado con su nodo siguiente y no con el anterior.

    La implementación puedes verla aquí: http://alguienenlafisi.blogspot.com/2010/12/lista-enlazada-simple-en-cc.html

    Saludos

    ResponderEliminar
    Respuestas
    1. Ya me salio muchas gracias una ultima duda
      yo lo hice con clases, use métodos
      pero no entendí como funcionaban los parámetros
      ejemplo:
      void NODO :: insertarFinal(nodo **pcab)
      main ()
      Nodo * Inicio = NULL;
      Inicio -> insertarFinal (&Inicio)

      Mandas la dirección de inicio pero por que otro asterisco??
      de hecho si no pongo doble asterisco no funciona por que?
      como funciona este paso de referencia??

      gracias de antemano bro muy útil

      Eliminar
    2. Hola, que bueno que te haya servido :)

      Bueno, en el método "insertarFinal" defines el parámetro **pcab con doble asterisco pues esperas recibir en él un "puntero a puntero", es decir, la dirección de memoria de un puntero.

      Por ello en el main defines un puntero "*inicio" y le pasas a insertarFinal su dirección de memoria con "&inicio".

      Gráficamente sería:


      **pcap ===> *inicio ===> NULL


      La razón de pasar el puntero "*inicio" por referencia es porque dentro del método insertarFinal necesitarás modificar "la dirección de memoria a la que apunta", es decir, el valor del puntero.

      Saludos.

      Eliminar
  10. para hacerlo con String como lo haria?

    ResponderEliminar
  11. Cambia el tipo dato de la variable "data" en la estructura "Nodo" y cambia las operaciones de asignación, comparación, etc. por funciones de manejo de cadenas.

    ResponderEliminar
  12. mil gracias por compartir esta información, no se imagina cuanto me ha ayudado

    ResponderEliminar