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(); } } } }