Controlar tamaño de lista dinamica?

[Oren]

Necesito utilizar una lista dinamica, puesto que voy a ir borrando elementos y asi me ahorro el utilizar un array dejando celdas "vacias". El problema es que necesito saber en todo momento el tamaño que tiene la lista, es decir, el numero de nodos, para entendernos.

Como puedo hacer esto? Habia pensado en, ademas de los datos que interesan en cada nodo, y el puntero al siguiente, añadir otro campo que contuviese el tamaño total de la lista, pero estaria repitiendo este valor en todos los nodos. Hay alguna forma mas elegante de hacerlo?

Desde ya, muchas gracias.

[posman]

Puedes tener una variable. Supongo que tienes funciones para agregar o eliminar nodos. En esas funciones incrementarias o decrementarias esa variable.

Otra forma es crear una funcion que recorra toda la lista con un ciclo e ir contando los nodos (aunque esta forma es la mas tardada). Si la lista es lineal, el ciclo se detiene cuando el siguiente nodo sea nulo. Si la lista es circular, el ciclo se detendria cuando el siguiente nodo es igual al primero.


No le veo mayor complicacion

[javilillo]

Hay te dejo el codigo de la lista por si te sirve, ya que tenia la lista a mano implementada y asi te ahorras el implementarla!
Reutilizacion del codigo! jajaja


#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <conio.h>


#if !defined(_LISTA_H)
#define _LISTA_H

typedef TIPO tipodato; // TIPO= tipo del dato a guardar en la lista

class Lista{
struct nodolista{
tipodato* dato;
nodolista *suce; //enlace a siguiente nodo
};
nodolista *E_Lista; //Puntero a primer nodo.
int num_elementos; //Numero de elmentos de la lista

public:
Lista();
bool vacia();
tipodato* frente();
void borrar();
bool borrar(tipodato* x);
bool borrar(string _titulo);
void insertar(tipodato* x);
bool insorden(tipodato* x);
tipodato* buscar(string _titulo);
void mostrar();
int num_elem();
void resto (Lista &aux);
~Lista();
};



#endif



/************************************************** **********/
// Nombre y Apellidos:
// Asignatura: LP2
// Grupo: G8
// Número de Entrega: 1º
// Año:
/************************************************** **********/

#include "lista.h"

using namespace std;

Lista::Lista()
{
E_Lista=NULL;
num_elementos=0;
}

bool Lista::vacia()
{
return(E_Lista==NULL);
}

tipodato* Lista::frente()
{
return(E_Lista->dato);
}

void Lista::insertar(tipodato* x)
{
nodolista *q;
q=new nodolista;
q->dato=x;
q->suce=E_Lista;
E_Lista=q;
num_elementos++;
}

bool Lista::insorden(tipodato* x)
{
bool insertado=false;
nodolista *punt_aux,*ant,*q;

q=new nodolista;
q->dato=x;
punt_aux=E_Lista;
ant=NULL;
if(vacia())
{
q->suce=E_Lista;
E_Lista=q;
num_elementos++;
}
else
while(!insertado)
{
if(punt_aux!=NULL)
if((q->dato->get_titulo ()). compare (punt_aux->dato->get_titulo ())<0)
{
q->suce=punt_aux;
if(ant==NULL)
E_Lista=q;
else
ant->suce=q;
insertado=true;
num_elementos++;
}
else
{
ant=punt_aux;
punt_aux=punt_aux->suce;
}
else
{
q->suce=punt_aux;
if(ant==NULL)
E_Lista=q;
else
ant->suce=q;
insertado=true;
num_elementos++;
}
}
return (insertado);
}

void Lista::borrar()
{
nodolista *p;
if(!vacia())
{
p=E_Lista;
E_Lista=E_Lista->suce;
delete p;
num_elementos--;
}
}

bool Lista::borrar(tipodato* x)
{
nodolista *ant,*p;
bool enc=false;
if(!vacia())
{
p=E_Lista;
while ((enc!=1) && (p!=NULL))
{
if (p->dato==x)
enc=true;
else
{
ant=p;
p=p->suce;
}
}
if (enc)//Si existe, organizamos la lista y lo borramos
{
if (p==E_Lista)
E_Lista=E_Lista->suce; //Si es el primero
else
ant->suce=p->suce;//si esta en medio o final
delete p;
num_elementos--;
}
}
return enc;
}

bool Lista::borrar(string _titulo)
{
nodolista *ant,*p;
bool enc=false;
if(!vacia())
{
p=E_Lista;
while ((enc!=1) && (p!=NULL))
{
if ((p->dato->get_titulo()).compare (_titulo)==0)
enc=true;
else
{
ant=p;
p=p->suce;
}
}
if (enc)//Si existe, organizamos la lista y lo borramos
{
if (p==E_Lista)
E_Lista=E_Lista->suce; //Si es el primero
else
ant->suce=p->suce;//si esta en medio o final
delete p;
num_elementos--;
}
}
return enc;
}



tipodato* Lista::buscar(string _titulo)
{
nodolista *aux;
aux=E_Lista;
while(aux!=NULL)
{
if((aux->dato->get_titulo()). compare (_titulo)==0)
return (aux->dato);
else aux=aux->suce;
}
return (NULL);
}

int Lista::num_elem()
{
return(num_elementos);
}

void Lista::mostrar()
{
nodolista *aux;
aux=E_Lista;
cout<<endl;
if (aux==NULL) cout<<"Lista vacia"<<endl;
else
while (aux!=NULL)
{
cout<<aux->dato<<endl;
aux=aux->suce;
if(aux!=NULL)
{
cout<<"[Tecla para continuar]";
getch();
cout<<endl;
}
}
cout<<" -------- Fin de la lista --------"<<endl;
}

void Lista :: resto (Lista &aux){
aux.E_Lista=E_Lista->suce;

/*while (aux.vacia()){
aux.borrar();
if (!vacia())
{
nodolista* p;
p=E_Lista->suce;
while (p!=NULL){
aux.insorden (p->dato);
p=p->suce;
}
}
}*/
}

Lista::~Lista()
{
nodolista *aux;
cout<<"Destruyendo lista"<<endl;
while(!vacia())
{
aux=E_Lista;
E_Lista=E_Lista->suce;
// delete (aux->dato);
delete aux;
}
}


Espero que te sirva!

[Oren]

muchas gracias. el problema es que tengo que guardarlo todo en memoria compartida (mecanismo ipc) y no se muy bien como controlar mas de una variable (en este caso, la lista dinamica) xD

[define]

pues mete una variable dentro de la misma lista... un contador int en la lista y listo, simplemente la tendras que manejar como una variable mas, controlandola desde la estructura "padre", y siempre qeu borres uno, la variable la disminiuyes, y siempre que añades, pues la aumentas.

[javilillo]

El contador de elementos de la lista ya esta puesto como atributo dentro de la propia lista, ya no tendrias ningun problema.
un saludo