Lectura 02 377

Lectura Nro 02
Estructuras de Datos listas enlazadas
Teoría de lista ligadas
La segunda forma de realización de listas, celdas enlazadas sencillas, utiliza apuntadores para enlazar elementos consecutivos. Esta implantación permite eludir el empleo de memoria contigua para almacenar una lista y, por tanto, también elude los desplazamientos de elementos para hacer inserciones o rellenar vacíoscreados por la eliminación de elementos. No obstante, por esto hay que pagar el precio de un espacio adicional para los apuntadores.

Listas con encabezado
Lista simplemente ligada
En esta representación, una lista está formada por celdas; cada celda contiene un elemento de la lista y un apuntador a la siguiente celda. Si la lista a1, a2, a3,...,an, la celda que contiene AI tiene un apuntador a lacelda que contiene a ai+1, para i=1,2,...,n – 1. La celda que contiene An posee un apuntador a NULL. Existe también una celda de encabezamiento que apunta a la celda que contiene a1; esta celda de encabezamiento no tiene ningún elemento. En este caso hablamos de una lista simplemente ligada con nodo de encabezamiento vacío, en la que el empleo de una celda completa para el encabezado simplifica laimplementación de las operaciones para manipular la lista, aunque también se puede utilizar el encabezado para almacenar el primer elemento y a este tipo de representación se le conoce como lista simplemente ligada con nodo de encabezamiento no vacío, en la que las inserciones y supresiones al principio de la lista se manejan de manera especial.

En el caso de una lista con encabezado vacío, elapuntador al siguiente nodo es NULL ya que no se tienen más celdas. La estructura de datos que emplearemos para representar una lista con apuntadores será un registro con dos campos, uno para guardar el elemento de la lista y otro para mantener la dirección del siguiente nodo.

A continuación se muestra la figura de una lista simplemente ligada lineal con nodo de encabezamiento vacío y longitud n.Las operaciones más comunes a las listas se muestran a continuación:
Class nodo{
tipo_elemento elemento;
nodo sig;
}

void inicializa ( Nodo Encabezado){
Encabezado =new(nodo); //Se crea el nodo de encabezado
Encabezado.sig =NULL; //Se le pone nil al campo siguiente,
//ya que la lista está vacía
}

Lista simplemente ligada circular
La implementación de una lista también puedehacerse mediante una lista simplemente ligada circular, que es muy similar a la anterior, con la diferencia de que el último nodo contiene en su campo siguiente un apuntador al encabezado en lugar de NULL.

La estructura de datos que se emplea para representar este tipo de lista es la misma que para una lista ligada lineal, y al igual que estas también el nodo de encabezado puede contenerinformación.



Una desventaja de las listas lineales es que dado un apuntador p a un nodo de la lista, no se puede tener acceso a cualquier otro nodo anterior a p. Si se recorre una lista, el apuntador al encabezado no debe ser modificado a fin de poder hacer referencia a esta lista.
Si hacemos un pequeño cambio en la estructura de tal manera que el último nodo en lugar de tener en el campo siguiente unapuntador nulo (nil) tenga la dirección al inicio de la lista, entonces desde cualquier otro punto de la lista es posible llegar a cualquier otro punto. En este caso la lista se llama lista circular.
Class nodo{
Tipo_elemento Elemento;
nodo sig;
}
void inicializa(Nodo Encabezado){ //Se crea el nodo de encabezado
encabezado = new(nodo); //Se hace que el campo siguiente del
encabezado.sig= encabezado; //encabezado se apunte así mismo

}
void inserta (tipo_elemento x, Nodo p){
/*Coloca el elemento x delante de la celda apuntada por p es exactamente igual que una lista lineal */
Nodo aux;
aux =new(nodo); /*Se reserva memoria para el nuevo nodo*/
aux.elemento =x; /*Se almacena el elemento*/
aux.sig =p.sig; /*Se enlaza con el siguiente nodo de p*/...