Listas enlazadas – Clase Lista,Nodo en c++

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.

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.

Aquí una ejemplo de un lista enlazada simple.

En cristiano:
55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL

Internamente:
Nodo-> Dato: 55 Direcion: 0x3d2c00 Siguiente: 0x3d2c80
Nodo-> Dato: 60 Direcion: 0x3d2c80 Siguiente: 0x3d2c90
Nodo-> Dato: 31 Direcion: 0x3d2c90 Siguiente: 0x3d2ca0
Nodo-> Dato: 5  Direcion: 0x3d2ca0 Siguiente: 0x3d2cb0
Nodo-> Dato: 4  Direcion: 0x3d2cb0 Siguiente: 0x3d2cc0
Nodo-> Dato: 51 Direcion: 0x3d2cc0 Siguiente: 0x3d3ab8
Nodo-> Dato: 9  Direcion: 0x3d3ab8 Siguiente: 0x3d3ac8
Nodo-> Dato: 27 Direcion: 0x3d3ac8 Siguiente: 0x3d3ad8
Nodo-> Dato: 68 Direcion: 0x3d3ad8 Siguiente: 0x3d3ae8
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)

Apliqué mis limitados conocimientos de templates para tener una lista genérica y así pueda funcionar con varios tipos de datos y de verdad funciona.

Ahí la definición e implementación de la clase, lista, clase nodo y el main para ver el funcionamiento. Cualquier crítica, sugerencia o comentarios son bienvenidos siempre.

Nodo.h

#ifndef NODO_H
#define NODO_H
#include <iostream>

using namespace std;
template <class T>
class Nodo
{
  public:
    T dato;
    Nodo *sgte;
    Nodo();
    Nodo(T);
    ~Nodo();

    void print();
    void eliminar();
};

#endif // NODO_H

Nodo.cpp

#include "Nodo.h"

//constructor por defecto
template<typename T>
Nodo<T>::Nodo()
{
  dato = NULL;
  sgte = NULL;
}

//constructor por parametro
template<typename T>
Nodo<T>::Nodo(T dato_)
{
  dato = dato_;
  sgte = NULL;
}

//imprimir un nodo
template<typename T>
void Nodo<T>::print()
{
  //cout << "Nodo-> " << "Dato: " << dato << " Direcion: " << this << " Siguiente: " << sgte << endl;
  cout << dato << "-> ";
}

//eliminar todos los nodos
template<typename T>
void Nodo<T>::eliminar()
{
  if(sgte)
    sgte->eliminar();
  delete this;
}

template<typename T>
Nodo<T>::~Nodo(){}

Lista.h

#ifndef LISTA_H
#define LISTA_H

#include <iostream>
#include "time.h"
#include <fstream>
#include <string>
#include "Nodo.h"
#include "Nodo.cpp"

using namespace std;

template <class T>
class Lista
{
  private:
    int dim,num_nodos;
    T line;
    string archivo;

  public:
    T ele;
    Nodo<T> *head;
    Lista();
    ~Lista();

    void llenar_teclado(int);
    void llenar_aleatorio(int);
    void print();
    void add_end(T);
    void add_head(T);
    void add_sort(T);
    void search(T);
    void del_dato(T);
    void del_pos(int);
    void del_all();

    void invertir();
    void sort();
    void load(string);
    void save(string);

    void concat(Lista);
    void interseccion(Lista);
};

#endif // LISTA_H

Lista.cpp

#include "Lista.h"

using namespace std;

//constructor por defecto
template<typename T>
Lista<T>::Lista()
{
  num_nodos = 0;
  head = NULL;
}

//llenar la lista por teclado
template<typename T>
void Lista<T>::llenar_teclado(int dim)
{
  for(int i=0;i<dim;i++){
    cout << "Ingresa el elemento " << i + 1 << endl;
    cin >> ele;
    add_end(ele);
  }
}

//llenar la lista aleatoriamente para enteros
template<typename T>
void Lista<T>::llenar_aleatorio(int dim)
{
  srand(time(NULL));
  for(int i=0;i<dim;i++){
    add_end(rand() % 100);
  }
}

//imprimir la lista
template<typename T>
void Lista<T>::print()
{
  Nodo<T> *temp = head;
  if(!head){
    cout << "La lista esta vacia " << endl;
  } else{
    while(temp){
      temp->print();
      if(!temp->sgte) cout << "NULL";
      temp = temp->sgte;
    }
  }
  cout << endl << endl;
}

//insertar al final
template<typename T>
void Lista<T>::add_end(T dato_)
{
  Nodo<T> *temp = head;
  Nodo<T> *nuevo = new Nodo<T> (dato_);

  if(!head){
      head = nuevo;
  } else{
    while(temp->sgte !=NULL){
      temp = temp->sgte;
    }
    temp->sgte = nuevo;
  }
  num_nodos++;
}

//insertar al inicio
template<typename T>
void Lista<T>::add_head(T dato_)
{
  Nodo<T> *temp = head;
  Nodo<T> *nuevo = new Nodo<T> (dato_);

  if(!head){
    head = nuevo;
  } else{
    nuevo->sgte = head;
    head = nuevo;
    while(temp){
      temp = temp->sgte;
    }
  }
  num_nodos++;
}

//insertar de manera ordenada
template<typename T>
void Lista<T>::add_sort(T dato_)
{
  Nodo<T> *nuevo = new Nodo<T> (dato_);
  Nodo<T> *temp = head;

  if(!head){
    head = nuevo;
  } else{
    if(head->dato > dato_){
      nuevo->sgte = head;
      head = nuevo;
    } else{
      while((temp->sgte != NULL) && (temp->sgte->dato < dato_)){
        temp = temp->sgte;
      }
      nuevo->sgte = temp->sgte;
      temp->sgte = nuevo;
    }
  }
  num_nodos++;
}

//buscar el dato de un nodo
template<typename T>
void Lista<T>::search(T dato_)
{
  Nodo<T> *temp = head;
  int cont = 1;
  int cont2=0;
  while(temp){
    if(temp->dato == dato_){
	  cout << "El dato se encuentra en la posicion: " << cont << " (Para seres humanos)" << endl;
	  cont2++;
    }
	temp = temp->sgte;
	cont++;
  }
  if(cont2 == 0){
    cout << "No existe el dato " << endl;
  }
  cout << endl << endl;
}

//eliminar por dato del nodo
template<typename T>
void Lista<T>::del_dato(T dato_)
{
  Nodo<T> *temp = head;
  Nodo<T> *temp1 = head->sgte;

  int cont=0;

  if(head->dato == dato_){
    head = temp->sgte;
  } else {
    while(temp1){
      if(temp1->dato == dato_){
	    Nodo<T> *aux = temp1;
        temp->sgte = temp1->sgte;
        delete aux;
        cont++;
        num_nodos--;
      }
	  temp = temp->sgte;
	  temp1 = temp1->sgte;
    }
  }
  if(cont == 0){
    cout << "No existe el dato " << endl;
  }
}

//eliminar por posicion del nodo
template<typename T>
void Lista<T>::del_pos(int pos)
{
  Nodo<T> *temp = head;
  Nodo<T> *temp1 = temp->sgte;

  if(pos < 1 || pos > num_nodos){
    cout << "Fuera de rango " << endl;
  } else if(pos==1){
    head = temp->sgte;
  } else{
    for(int i=2;i<=pos;i++){
      if(i==pos){
        Nodo<T> *aux = temp1;
        temp->sgte = temp1->sgte;
        delete aux;
        num_nodos--;
      }
      temp = temp->sgte;
      temp1 = temp1->sgte;
    }
  }
}

//eliminar todos los nodos
template<typename T>
void Lista<T>::del_all()
{
  head->eliminar();
  head = 0;
}

//invertir la lista
template<typename T>
void Lista<T>::invertir()
{
  Nodo<T> *temp = head;
  Nodo<T> *prev = NULL;
  Nodo<T> *next = NULL;

  while(temp){
    next = temp->sgte;
    temp->sgte = prev;
    prev = temp;
    temp = next;
  }
  head = prev;
}

//ordenar de manera ascendente
template<typename T>
void Lista<T>::sort()
{
  T aux2;
  Nodo<T> *aux = head;
  Nodo<T> *temp = aux;

  while(aux){
    temp=aux;
    while(temp->sgte){
      temp=temp->sgte;

      if(aux->dato>temp->dato){
        aux2=aux->dato;
        aux->dato=temp->dato;
        temp->dato=aux2;
      }
    }
    aux=aux->sgte;
  }
}

//cargar una lista de un archivo
template<typename T>
void Lista<T>::load(string archivo)
{
  ifstream in;
  in.open(archivo.c_str());

  if(!in.is_open()){
    cout << "No se puede abrir el archivo: " << archivo << endl << endl;
  } else{
    while(in >> line){
      add_end(line);
    }
  }
  in.close();
}

//guardar una lista en un archivo
template<typename T>
void Lista<T>::save(string archivo)
{
  Nodo<T> *temp = head;
  ofstream out;
  out.open(archivo.c_str());

  if(!out.is_open()){
    cout << "No se puede guardar el archivo " << endl;
  } else{
    while(temp){
      out << temp->dato;
      out << " ";
      temp = temp->sgte;
    }
  }
  out.close();
}

//concatenar a otra lista
template<typename T>
void Lista<T>::concat(Lista Lista2)
{
  Nodo<T> *temp2 = Lista2.head;

  while(temp2){
    add_end(temp2->dato);
    temp2 = temp2->sgte;
  }
}

//numeros que coinciden en 2 listas
template<typename T>
void Lista<T>::interseccion(Lista Lista2)
{
  Nodo<T> *temp = head;
  Nodo<T> *temp2 = Lista2.head;//cabeza de la segunda lista
  Lista lista_interseccion;//creo otra lista

  int num_nodos2 = Lista2.num_nodos;//nodos de la segunda lista
  int num_inter=0;//numero de coincidencias

  //creo 2 vectores dinamicos
  T *v1 = new T[num_nodos];
  T *v2 = new T[num_nodos2];

  //lleno los vectores v1 y v2 con los datos de la lista original y segunda lista respectivamente
  int i=0;
  while(temp){
    v1[i] = temp->dato;
    temp = temp->sgte;
    i++;
  }

  int j=0;
  while(temp2){
    v2[j] = temp2->dato;
    temp2 = temp2->sgte;
    j++;
  }

  //ordeno los vectores
  insert_sort(v1,num_nodos);
  insert_sort(v2,num_nodos2);

  int v1_i= 0;//indice del 1er vector (v1)
  int v2_i= 0;//indice del 2do vector (v2)

  //mientras no haya terminado de recorrer ambas listas
  while (v1_i < num_nodos && v2_i < num_nodos2) {
    if(v1[v1_i] == v2[v2_i]){//cuando los datos de ambas sean iguales
      lista_interseccion.add_end(v1[v1_i]);//utilizo mi metodo add_end para llenar la lista de intersecciones
      v1_i++;
      v2_i++;
      num_inter++;
    } else if(v1[v1_i] < v2[v2_i]){
      v1_i++;
    } else{
      v2_i++;
    }
  }

  //Solo si hay alguna interseccion imprimo la nueva lista creada
  if(num_inter > 0) {
    cout << "Existen " << num_inter << " intersecciones " << endl;
    lista_interseccion.print();
  } else {
    cout << "No hay interseccion en ambas listas" << endl;
  }
}

//usado por el metodo interseccion
template<typename T>
void insert_sort(T a[],int tam)
{
  T temp;
  for(int i=0;i<tam;i++){
    for(int j=i-1;j >=0 && a[j+1] < a[j];j--){
      temp = a[j+1];
      a[j+1] = a[j];
      a[j] = temp;
    }
  }
}

template<typename T>
Lista<T>::~Lista(){}

main.cpp

#include <iostream>
#include "Lista.h"
#include "Lista.cpp" //por errores de linking de tipo "undefined reference to" (estudiando)

using namespace std;
int main()
{
  Lista<int> l1;
  Lista<int> l2;

  int dim,pos;
  string archivo;

  cout << "Ingresa la dimension de la lista " << endl;
  cin >>dim;

  l1.llenar_aleatorio(dim);//llenar_teclado para otros tipos

  cout << "Lista A al inicio " << endl;
  l1.print();

  cout << "Agrega un elemento por la cabeza" << endl;
  cin >>l1.ele;
  l1.add_head(l1.ele);
  l1.print();

  cout << "Lista invertida " << endl;
  l1.invertir();
  l1.print();

  cout << "Lista ordenada " << endl;
  l1.sort();
  l1.print();

  cout << "Agrega un elemento (Sera ordenado)" << endl;
  cin >>l1.ele;
  l1.add_sort(l1.ele);
  l1.print();

  cout << "Busca un elemento" << endl;
  cin >>l1.ele;
  l1.search(l1.ele);

  cout << "Elimina un elemento por dato" << endl;
  cin >>l1.ele;
  l1.del_dato(l1.ele);
  l1.print();

  cout << "Elimina un elemento por posicion" << endl;
  cin >>pos;
  l1.del_pos(pos);
  l1.print();

  cout << "Cargar una lista desde archivo - Ingresa el nombre" << endl;
  cin >> archivo;//debe estar en el mismo directorio que este programa
  l2.load(archivo);
  cout << "Lista B" << endl;
  l2.print();

  cout << "Guardar la lista en un archivo - Ingresa el nombre" << endl;
  cin >> archivo;//ingresa un nombre cualquiera *.*
  l2.save(archivo);

  cout << "Interseccion entre las listas A y B " << endl;
  l1.interseccion(l2);

  cout << "Listas A y B concatenadas " << endl;
  l1.concat(l2);
  l1.print();

  l1.del_all();
  l1.print();

  return 0;
}

Un ejemplo de la salida del programa:

Ingresa la dimension de la lista
10
Lista A al inicio
55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL

Agrega un elemento por la cabeza
18
18-> 55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL

Lista invertida
62-> 68-> 27-> 9-> 51-> 4-> 5-> 31-> 60-> 55-> 18-> NULL

Lista ordenada
4-> 5-> 9-> 18-> 27-> 31-> 51-> 55-> 60-> 62-> 68-> NULL

Agrega un elemento (Sera ordenado)
45
4-> 5-> 9-> 18-> 27-> 31-> 45-> 51-> 55-> 60-> 62-> 68-> NULL

Busca un elemento
51
El dato se encuentra en la posicion: 8 (Para seres humanos)

Elimina un elemento por dato
60
4-> 5-> 9-> 18-> 27-> 31-> 45-> 51-> 55-> 62-> 68-> NULL

Elimina un elemento por posicion:
11
4-> 5-> 9-> 18-> 27-> 31-> 45-> 51-> 55-> 62-> NULL

Cargar una lista desde archivo - Ingresa el nombre
prueba.txt // mi archivito prueba.txt tenia estos datos
Lista B
8-> 59-> 23-> 15-> 94-> 63-> 9-> 17-> 62-> 33-> NULL

Guardar la lista en un archivo - Ingresa el nombre
otralista.txt // abre tu archivo y mira el contenido
Interseccion entre las listas A y B
Existen 2 intersecciones
9-> 62-> NULL

Listas A y B concatenadas
4-> 5-> 9-> 18-> 27-> 31-> 45-> 51-> 55-> 62-> 8-> 59-> 23-> 15-> 94-> 63-> 9->17-> 62-> 33-> NULL

La lista esta vacia.

Hasta pronto

---

Possibly related posts: (automatically generated)

• Vectores, Matrices y Punteros en c++