Imaginemos un mundo libre – El blog de Ronny

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Listas enlazadas – Clase Lista,Nodo en c++

with 18 comments

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->next;
        }

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 (!m_head) {
    ...
}

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.

node.h

#ifndef NODE_H
#define NODE_H

#include <iostream>

using namespace std;

template <class T>

class Node
{
    public:
        Node();
        Node(T);
        ~Node();

        Node *next;
        T data;

        void delete_all();
        void print();
};

#endif // NODE_H

node.cpp

#include "node.h"

// Constructor por defecto
template<typename T>

Node<T>::Node()
{
    data = NULL;
    next = NULL;
}

// Constructor por parámetro
template<typename T>
Node<T>::Node(T data_)
{
    data = data_;
    next = NULL;
}

// Eliminar todos los Nodos
template<typename T>
void Node<T>::delete_all()
{
    if (next)
        next->delete_all();
    delete this;
}

// Imprimir un Nodo
template<typename T>
void Node<T>::print()
{
    //cout << "Node-> " << "Dato: " << dato << " Direcion: " << this << " Siguiente: " << next << endl;
    cout << data << "-> ";
}

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

list.h

#ifndef LIST_H
#define LIST_H

#include <fstream>
#include <iostream>
#include <string>
#include <stdlib.h>

#include "node.h"
#include "node.cpp"

using namespace std;

template <class T>

class List
{
    public:
        List();
        ~List();

        void add_head(T);
        void add_end(T);
        void add_sort(T);
        void concat(List);
        void del_all();
        void del_by_data(T);
        void del_by_position(int);
        void fill_by_user(int);
        void fill_random(int);
        void intersection(List);
        void invert();
        void load_file(string);
        void print();
        void save_file(string);
        void search(T);
        void sort();

    private:
        Node<T> *m_head;
        int m_num_nodes;
};

#endif // LIST_H

list.cpp

#include "list.h"

using namespace std;

// Constructor por defecto
template<typename T>
List<T>::List()
{
    m_num_nodes = 0;
    m_head = NULL;
}

// Insertar al inicio
template<typename T>
void List<T>::add_head(T data_)
{
    Node<T> *new_node = new Node<T> (data_);
    Node<T> *temp = m_head;

    if (!m_head) {
        m_head = new_node;
    } else {
        new_node->next = m_head;
        m_head = new_node;

        while (temp) {
            temp = temp->next;
        }
    }
    m_num_nodes++;
}

// Insertar al final
template<typename T>
void List<T>::add_end(T data_)
{
    Node<T> *new_node = new Node<T> (data_);
    Node<T> *temp = m_head;

    if (!m_head) {
        m_head = new_node;
    } else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    m_num_nodes++;
}

// Insertar de manera ordenada
template<typename T>
void List<T>::add_sort(T data_)
{
    Node<T> *new_node = new Node<T> (data_);
    Node<T> *temp = m_head;

    if (!m_head) {
        m_head = new_node;
    } else {
        if (m_head->data > data_) {
            new_node->next = m_head;
            m_head = new_node;
        } else {
            while ((temp->next != NULL) && (temp->next->data < data_)) {
                temp = temp->next;
            }
            new_node->next = temp->next;
            temp->next = new_node;
        }
    }
    m_num_nodes++;
}

// Concatenar a otra List
template<typename T>
void List<T>::concat(List list)
{
    Node<T> *temp2 = list.m_head;

    while (temp2) {
        add_end(temp2->data);
        temp2 = temp2->next;
    }
}

// Eliminar todos los nodos
template<typename T>
void List<T>::del_all()
{
    m_head->delete_all();
    m_head = 0;
}

// Eliminar por data del nodo
template<typename T>
void List<T>::del_by_data(T data_)
{
    Node<T> *temp = m_head;
    Node<T> *temp1 = m_head->next;

    int cont = 0;

    if (m_head->data == data_) {
        m_head = temp->next;
    } else {
        while (temp1) {
            if (temp1->data == data_) {
                Node<T> *aux_node = temp1;
                temp->next = temp1->next;
                delete aux_node;
                cont++;
                m_num_nodes--;
            }
            temp = temp->next;
            temp1 = temp1->next;
        }
    }

    if (cont == 0) {
        cout << "No existe el dato " << endl;
    }
}

// Eliminar por posición del nodo
template<typename T>
void List<T>::del_by_position(int pos)
{
    Node<T> *temp = m_head;
    Node<T> *temp1 = temp->next;

    if (pos < 1 || pos > m_num_nodes) {
        cout << "Fuera de rango " << endl;
    } else if (pos == 1) {
        m_head = temp->next;
    } else {
        for (int i = 2; i <= pos; i++) {
            if (i == pos) {
                Node<T> *aux_node = temp1;
                temp->next = temp1->next;
                delete aux_node;
                m_num_nodes--;
            }
            temp = temp->next;
            temp1 = temp1->next;
        }
    }
}

// Llenar la Lista por teclado
template<typename T>
void List<T>::fill_by_user(int dim)
{
    T ele;
    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 List<T>::fill_random(int dim)
{
    srand(time(NULL));
    for (int i = 0; i < dim; i++) {
        add_end(rand() % 100);
    }
}

// Usado por el método intersección
template<typename T>
void insert_sort(T a[], int size)
{
    T temp;
    for (int i = 0; i < size; 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;
        }
    }
}

// Números que coinciden en 2 Lists
template<typename T>
void List<T>::intersection(List list_2)
{
    Node<T> *temp = m_head;
    Node<T> *temp2 = list_2.m_head;

    // Creo otra Lista
    List intersection_list;

    int num_nodes_2 = list_2.m_num_nodes;
    int num_inter = 0;

    // Creo 2 vectores dinámicos
    T *v1 = new T[m_num_nodes];
    T *v2 = new T[num_nodes_2];

    // Lleno los vectores v1 y v2 con los datas de la lista original y segunda lista respectivamente
    int i = 0;

    while (temp) {
        v1[i] = temp->data;
        temp = temp->next;
        i++;
    }

    int j = 0;

    while (temp2) {
        v2[j] = temp2->data;
        temp2 = temp2->next;
        j++;
    }

    // Ordeno los vectores
    insert_sort(v1, m_num_nodes);
    insert_sort(v2, num_nodes_2);

    // Índice del 1er vector (v1)
    int v1_i = 0;

    // Índice del 2do vector (v2)
    int v2_i = 0;

  // Mientras no haya terminado de recorrer ambas Lists
  while (v1_i < m_num_nodes && v2_i < num_nodes_2) {
      if (v1[v1_i] == v2[v2_i]) {
          intersection_list.add_end(v1[v1_i]);
          v1_i++;
          v2_i++;
          num_inter++;
      } else if (v1[v1_i] < v2[v2_i]) {
          v1_i++;
      } else {
          v2_i++;
      }
  }

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

// Invertir la lista
template<typename T>
void List<T>::invert()
{
    Node<T> *prev = NULL;
    Node<T> *next = NULL;
    Node<T> *temp = m_head;

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

// Cargar una lista desde un archivo
template<typename T>
void List<T>::load_file(string file)
{
    T line;
    ifstream in;
    in.open(file.c_str());

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

// Imprimir la Lista
template<typename T>
void List<T>::print()
{
    Node<T> *temp = m_head;
    if (!m_head) {
        cout << "La Lista está vacía " << endl;
    } else {
        while (temp) {
            temp->print();
            if (!temp->next) cout << "NULL";
                temp = temp->next;
        }
  }
  cout << endl << endl;
}

// Buscar el dato de un nodo
template<typename T>
void List<T>::search(T data_)
{
    Node<T> *temp = m_head;
    int cont = 1;
    int cont2 = 0;

    while (temp) {
        if (temp->data == data_) {
            cout << "El dato se encuentra en la posición: " << cont << endl;
            cont2++;
        }
        temp = temp->next;
        cont++;
    }

    if (cont2 == 0) {
        cout << "No existe el dato " << endl;
    }
    cout << endl << endl;
}

// Ordenar de manera ascendente
template<typename T>
void List<T>::sort()
{
    T temp_data;
    Node<T> *aux_node = m_head;
    Node<T> *temp = aux_node;

    while (aux_node) {
        temp = aux_node;

        while (temp->next) {
            temp = temp->next;

            if (aux_node->data > temp->data) {
                temp_data = aux_node->data;
                aux_node->data = temp->data;
                temp->data = temp_data;
            }
        }

        aux_node = aux_node->next;
    }
}

// Guardar una lista en un archivo
template<typename T>
void List<T>::save_file(string file)
{
    Node<T> *temp = m_head;
    ofstream out;
    out.open(file.c_str());

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

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

main.cpp

#include <iostream>

#include "list.h"
#include "list.cpp"

using namespace std;

int main()
{
    List<int> list_1;
    List<int> list_2;
    int ele;

    int dim;
    int pos;
    string file_with_list;

    cout << "Ingresa la dimensión de la lista: " << endl;
    cin >> dim;

    list_1.fill_random(dim);

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

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

    cout << "Lista invertida: " << endl;
    list_1.invert();
    list_1.print();

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

    cout << "Agrega un elemento. Será insertado ordenadamente: " << endl;
    cin >> ele;
    list_1.add_sort(ele);
    list_1.print();

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

    cout << "Elimina un elemento por dato: " << endl;
    cin >> ele;
    list_1.del_by_data(ele);
    list_1.print();

    cout << "Elimina un elemento por posición: " << endl;
    cin >> pos;
    list_1.del_by_position(pos);
    list_1.print();

    cout << "Cargar una lista desde archivo - Ingresa el nombre(Ex: list.txt): " << endl;
    // El archivo debe estar en el mismo directorio que este programa
    cin >> file_with_list;
    list_2.load_file(file_with_list);
    cout << "Lista B: " << endl;
    list_2.print();

    cout << "Guardar la lista en un archivo - Ingresa el nombre(Ex: list2.txt): " << endl;
    cin >> file_with_list;
    list_2.save_file(file_with_list);

    cout << "Interseccion entre las listas A y B: " << endl;
    list_1.intersection(list_2);

    cout << "Listas A y B concatenadas: " << endl;
    list_1.concat(list_2);
    list_1.print();

    list_1.del_all();
    list_1.print();

    return 0;
}

El código fuente de este y otros ejercicios de C++ está disponible en Github:

https://github.com/ronnyml/C—Tutorial

Gracias por tu visita al blog.  Puedes seguirme en Twitter haciendo click en el siguiente enlace:

About these ads

Written by Ronny Yabar Aizcorbe

julio 4, 2009 at 5:36 pm

Publicado en C++

Tagged with , , ,

18 comentarios

Subscribe to comments with RSS.

  1. te queria pedir ayuda haber si puedes hacer algo por mi tengo que entregar un proyecto y necesito leer lineas con datos de un archivo y almacenarlas en una lista dinamica..
    no se como hacerlo..
    ojala puedas ayudarme.saludos..gracias

    jandi manuel

    julio 8, 2009 at 6:43 pm

  2. Un preguntilla, el puntero **matr1 no debería estar declarado como private para mantener la encapsulación?

    Por lo demás, es un blog magnífico, estoy aprendiendo mucho.

    saludos!!

    Javier

    agosto 5, 2009 at 12:36 pm

    • @jandi en este ejemplo te fijaste en los métodos
      void Lista::load(string archivo)
      void Lista::save(string archivo)

      creo que eso es lo que necesitas, sino puedes especificar un poco más el problema que necesitas resolver.

      Ronny Yabar Aizcorbe

      septiembre 2, 2009 at 2:38 pm

    • @Javier muchas gracias por el apunte, tienes toda la razón. **matr1 ahora es private.

      Ronny Yabar Aizcorbe

      septiembre 16, 2009 at 4:43 am

  3. que quiere decir esto:
    if(!head){ // esoo ?? EN C.
    head = nuevo;

    y …
    Nodo *nuevo = new Nodo (dato_); // como podria escribirlo en C.
    // (dato_); esooooo no entiendo

    porfavor!!!
    gracias =)

    natalia

    septiembre 3, 2009 at 6:45 am

  4. haa ok , pero esto quiere decir ..
    if(!head) // preguntar si cabeza es distinto de que .. ??

    natalia

    septiembre 3, 2009 at 6:53 am

    • @natalia la sentencia: if(!head) es una manera de preguntar si la variable es nula o no contiene nada.

      Ronny Yabar Aizcorbe

      septiembre 16, 2009 at 4:28 am

  5. El error de link que te daba cuando ponias
    //#include “Lista.cpp” // ( “undefined reference to”)

    es porque tenes que agregar en Lista.cpp

    template class Lista;

    y crear un metodo static bool test(); en la clase Lista
    para poner todo lo que tenias en el Main
    /*
    template
    bool Lista :: test()
    {
    Lista l1;
    Lista l2;

    int dim,pos;
    string archivo;

    cout << "Ingresa la dimension de la lista " <>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" <>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)" <>l1.ele;
    l1.add_sort(l1.ele);
    l1.print();

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

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

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

    cout << "Cargar una lista desde archivo – Ingresa el nombre" <> 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" <> 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 true;

    */

    Y en el main
    /*
    int main()
    {
    if(Lista::test())
    cout<<"Lista – OK\n"<<endl;
    else
    cout<<"Lista – Error\n"<<endl;

    system("PAUSE");
    return EXIT_SUCCESS;

    }
    */

    Saludos!! lo demas andaba joya!

    GP

    septiembre 23, 2009 at 12:05 am

  6. muchas muchas gracias en serio bacano su codigo y mucho mas que lo comparta :) estamos en contacto por twitter.

    Daniel

    octubre 25, 2009 at 11:29 pm

  7. ooooh!!! tío eres muy muy grande!!!! Me has ayudado muchisimo, muchisimo y muchisimo con esta entrada!! Ánimo!!!

    Dave

    febrero 19, 2010 at 9:24 am

  8. template

    Lista : : ~ Lista ( ) { }

    Dani

    marzo 30, 2010 at 3:23 am

  9. Luce muy bien, pero como no se de templates pues no entendi mucho :/

    Angelverde

    octubre 25, 2010 at 10:43 pm

  10. [...] /* 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/ [...]

  11. excelente Guru!!!!

    edwin

    octubre 21, 2011 at 3:58 pm

  12. excelente tu código me ayudas un montón… pero una pregunta tengo que poner los tres cuadros en el programa de c++ para que me haga el ejemplo de salida que has mostrado

    isabel

    diciembre 28, 2011 at 1:05 am

  13. Hola muy intersante, bueno quisiera sabe q’ editor es el q’ etas usando parece bueno… gracias

    habns

    julio 28, 2012 at 1:13 am

  14. pero igualmente gracias

    PIERO ANDRATE TE CAH

    julio 7, 2014 at 7:38 pm


Deja un comentario

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

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: