Listas Doblementes Enlazadas Yoandy Pérez Villazón (2004-11-06)
El ejemplo que muestro a continuación es una lista doblemente enlazada realizada en C++ , usando 2 clases, una clase CNodo para crear la estructura de dato y una clase CListaDE para manipular de alguna forma el trabajo con estos nodos. Es un ejemplo que incluye los métodos básicos de trabajo, es decir:
- Adicionar un elemento a la lista .-
- Eliminar un elemento de la lista .-
- Obtener un elemento a la lista .-
- Ver la lonngitud de la lista .-
- Insertar un elemento a la lista .-
De forma general esto es lo que se muestra en el codigo
template <class T>
class CNodo {
private :
T dato ;
CNodo<T> *siguiente ;
CNodo<T> *anterior ;
public :
CNodo(T adato , CNodo<T> *sig = 0,CNodo<T> *ant = 0 )
{
dato = adato ;
siguiente = sig ;
anterior = ant ;
}
void SetSiguiente(CNodo<T> *sig)
{
siguiente = sig ;
}
void SetAnterior(CNodo<T> *ant)
{
anterior = ant ;
}
T Getdato()
{
return dato;
}
CNodo<T> *GetSiguiente()
{
return siguiente ;
}
CNodo<T> *GetAnterior()
{
return anterior ;
}
};
//Clase Lista
template <class T>
class CListaDE {
private :
CNodo<T> * ptr_cabeza ;
public :
CListaDE()
{
ptr_cabeza = 0 ;
}
void Adicionar(T elem)
{
CNodo<T> *nodo = new CNodo<T>(elem, 0);
if(EstaVacia()) {
ptr_cabeza = nodo ;
}
else {
CNodo<T> *cursor = ptr_cabeza ;
while(cursor->GetSiguiente() != 0)
cursor = cursor->GetSiguiente();
nodo->SetAnterior(cursor);
cursor->SetSiguiente(nodo);
}
}
bool EstaVacia()
{
return ptr_cabeza == 0 ;
}
T Obtener(int pos)
{
if(pos>0 && pos <= Longitud())
{
CNodo<T> *cursor = ptr_cabeza ;
int pos_cursor = 0 ;
while(cursor->GetSiguiente() != 0 && pos_cursor+1 != pos)
{
cursor = cursor->GetSiguiente();
pos_cursor++;
}
return cursor->Getdato();
}
else
throw CErrorPosicionExceptions();
}
int Longitud()
{
if(EstaVacia()) return 0 ;
else {
CNodo<T> *cursor = ptr_cabeza ;
int cantidad = 0 ;
while(cursor != 0)
{
cantidad++;
cursor = cursor->GetSiguiente();
}
return cantidad ;
}
}
void Insertar(T data , int pos)
{
if(pos > 0 && pos <= Longitud())
{
if(EstaVacia()) Adicionar(data);
else
{
CNodo<T> *nodo = new CNodo<T>(data, 0 , 0);
if(pos == 1)
{
nodo->SetSiguiente(ptr_cabeza);
ptr_cabeza->GetSiguiente()->SetAnterior(nodo);
ptr_cabeza = nodo ;
}
else
{
CNodo<T> *cursor = ptr_cabeza ;
int pos_cursor = 1 ;
while(cursor->GetSiguiente() != 0 && pos_cursor + 1 != pos)
{
cursor = cursor->GetSiguiente();
pos_cursor++ ;
}
nodo->SetSiguiente(cursor->GetSiguiente());
nodo->SetAnterior(cursor);
cursor->GetSiguiente()->SetAnterior(nodo);
cursor->SetSiguiente(nodo);
}
}
}
else
throw CErrorPosicionExceptions();
}
void Eliminar(int pos)
{
if(pos>0 && pos<= Longitud())
{
if(Longitud() == 1) delete [] ptr_cabeza ;
else
if(pos == 1)
{
CNodo<T> *temp = ptr_cabeza->GetSiguiente();
delete[]ptr_cabeza ;
ptr_cabeza = temp ;
ptr_cabeza->SetAnterior(0);
}
else
{
CNodo<T> *cursor = ptr_cabeza ;
int pos_cursor = 1 ;
while(cursor->GetSiguiente()!= 0 && pos_cursor+1 != pos)
{
cursor = cursor->GetSiguiente();
pos_cursor++ ;
}
CNodo<T> *temp = cursor->GetSiguiente();
cursor->SetSiguiente(temp->GetSiguiente());
cursor->GetSiguiente()->SetAnterior(cursor);
delete []temp;
}
}
else
throw CErrorPosicionExceptions();
}
bool Buscar(T elem)
{
if(!EstaVacia())
{
CNodo<T> *cursor = ptr_cabeza ;
while(cursor->GetSiguiente() != 0)
{
if(cursor->Getdato() == elem)
{
return true ;
}
else
cursor = cursor->GetSiguiente();
}
}
}
T Buscar_Anterior(T elem)
{
if(!EstaVacia())
{
CNodo<T> *cursor = ptr_cabeza ;
while(cursor->GetSiguiente() != 0)
{
if(cursor->GetSiguiente()->Getdato() == elem)
{
return cursor->Getdato();
}
else
cursor = cursor->GetSiguiente();
}
}
}
}