Listas Enlazadas en C++ Orientado a Objetos

Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. 
El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato autoreferenciado porque contienen un puntero o enlace a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.

En este programa se utiliza memoria dinámica y una función add(), donde  busca el lugar de la inserción, ya sea automáticamente por el inicio, a la mitad o al final de la lista, misma que se puede utilizar las veces que sean necesarias. También tiene funciones en las que permite buscar algún dato anteriormente insertado, vaciar la lista e imprimir.

#ifndef __SLLIST_
#define __SLLIST_

typedef class snode{
    public:
        bool add(int);
        void printList();
        int leer(int);
        bool search(int);
        bool erase(int);
        bool clear();
        bool empty();
        int Menu(int);
        int data;
        class snode * next;
}node;
#endif

Este es el archivo de cabecera que se guarda con la extensión ".h" donde se declara la clase

#include "sllist.h"
#include <iostream>
#include <iomanip>

using namespace std;

node *list = NULL;

bool node::add(int x){
    if(list == NULL){//lista vacia
        list = new node;
        list -> data = x;
        list -> next = NULL;
        return true;
    }
    node *p = list;//lista no vacia
    node *q;
    //buscar lugar de la insercion
    while(p != NULL && p -> data < x){
         q = p;
         p = p -> next;
    }//insercion por el final de la lista
    if(p == NULL){
        node *aux = new node;
        aux -> data = x;
        aux -> next = NULL;
        q -> next = aux;
    }//insercion
    //el nuevo dato ya existente
    else{
        if(p -> data == x)
            return false;
        if(p == list){//agregacion por el inicio
            node *aux = new node;
            aux -> data = x;
            list = aux;
            aux -> next = p;
        }
        else{//gregacion a la mitad de la lista
            node *aux = new node;
            aux -> data = x;
            q -> next = aux;
            aux ->next = p;
        }
    }
    return true;
}

int node::leer(int dato){    
    cin>>dato;
    return dato;
}

void node::printList(){
    node *p = list;
    while (p != NULL){
        cout<<setw(4)<<p -> data;
        p = p ->next;
    }
    cout<<endl;
}

bool node::search(int x){
     node *p = list;
     while(p != NULL && p -> data <= x){
         if(p -> data == x)
             return true;
         else
             p = p -> next;
     }
     return false;
}    

bool node::erase(int x){//Mal
    node *p = list;
    node *q;
    while((p != NULL) && (p -> data <= x)){
        if(p -> data == x){
            if(p == list)
                list = p -> next;                
            else{
                q -> next = p -> next;
                delete p;
                return true;
            }
        }
        else{
            q = p;
            p = p -> next;
        }   
    }
    return false;   
}

bool node::clear(){
    node *q;
    while(list != NULL){
        q = list;
        list = list -> next;
        delete q;
    }
    list = NULL;
    return true;
}

bool node::empty(){
     return list == NULL; 
}

En este archivo se hacen los métodos para la inserción, búsqueda, eliminación y vaciado de la lista.

#include "sllist.h"
#include <cstdlib>
#include <iostream>

using namespace std;

int Menu(int opcion){
     cout<<"1)agregar\n";
     cout<<"2)buscar\n";
     cout<<"3)eliminar\n";
     cout<<"4)vaciar lista\n";
     cout<<"5)verificar si la lista esta vacia\n";
     cout<<"6)Imprimir Lista\n";
     cout<<"7)Salir\n"; 
     cout<<"\n\nOpcion: ";
     cin>>opcion;
     return opcion;
}

int main(){
    node n;
    int x;
    int opcion;
    do{
        opcion = Menu(opcion);
        switch(opcion){
            case 1:
                 cout<<"Ingresa el dato: ";
                 x = n.leer(x);
                 if(n.add(x)){       
                     cout<<"El dato fue insertado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue insertado\n";
                 break;
            case 2:
                 x = n.leer(x);
                 if(n.search(x)){ 
                     cout<<"El dato fue encontrado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue encontrado\n";
                 break;
            case 3:
                 x = n.leer(x);
                 if(n.erase(x)){
                     cout<<"El dato fue eliminado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue encontrado\n";
                 break;
            case 4:
                 if(n.clear()){ 
                     cout<<"la lista esta vacia";
                     n.printList();
                 }
                 else
                     cout<<"la lista aun no esta vacia";
                 break;
            case 5:
                 if(n.empty()){ 
                     cout<<"la lista esta vacia";
                     n.printList();
                 }
                 else
                     cout<<"la lista no esta vacia";
                 break;
            case 6:
                 n.printList();
                 break;
            case 7:
                 n.clear();
                 return 0;
                 break;    
            default: 
                 cerr<<"Error";
                 break;
        }
        cin.get();
        cin.get();
        system("cls"); 
    }while(opcion != 7);    
    return EXIT_SUCCESS;
}

Al final el archivo Main donde se muestra un ejemplo del uso de esta lista.