Listas doblemente enlazadas

Solo disponible en BuenasTareas
  • Páginas : 3 (743 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de mayo de 2011
Leer documento completo
Vista previa del texto
. INTRODUCCIÓN.
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. Entales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.

Otra ventaja de las listasdoblemente enlazadas es que podemos usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente,también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera. El único precio que pagamos por estas características es la presencia de un punteroadicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas. Si usamos punteros (mejor que cursores) podemos declarar celdas que consisten enun elemento y dos punteros a través de:
typedef struct celda{
tipoelemento elemento;
struct celda *siguiente,*anterior;
}tipocelda;

typedef tipocelda *posicion;

Un procedimiento paraborrar un elemento en la posición p en una lista doblemente enlazada es:
void borrar (posicion p)
{
if (p->anterior != NULL)
p->anterior->siguiente = p->siguiente;
if (p->siguiente !=NULL)
p->siguiente->anterior = p->anterior;
free(p);
}

El procedimiento anterior se expresa de forma gráfica en como muestra la figura:

Donde los trazos contínuos denotan la situacióninicial y los punteados la final. El ejemplo visto se ajusta a la supresión de un elemento o celda de una lista situada en medio de la misma. Para obviar los problemas derivados de los elementos extremos(primero y último) es práctica común hacer que la cabecera de la lista doblemente enlazada sea una celda que efectivamente complete el círculo, es decir, el anterior a la celda de cabecera sea la...
tracking img