Actividad 4
Listas Doblemente Ligada Circular Con Registro Cabeza
Investigar que son Listas Doblemente Ligadas Circular Con Registro Cabeza y sus diferencias con las doblemente ligadas y simplemente ligadas.
Listas Circulares
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en las operaciones que se realicen sobre ellas. No
existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la
única excepción posible, la de que la lista esté vacía.
La lista circular vinculada como el tipo de lista vinculada en la que el último nodo de la lista está conectado con el primer nodo, y para reconocer dónde comienza la lista, el puntero principal está ahí que apunta al primer nodo en la lista circular vinculada.
El enlace circular se comporta exactamente como las otras dos listas vinculadas ( De manera inteligente y doble ), excepto por el comportamiento circular de las listas circulares vinculadas. Por lo tanto, podemos diseñar la lista circular vinculada utilizando estos dos tipos básicos de lista vinculada. Entonces podemos decir que una lista circular vinculada puede ser de 2 tipos –
- Lista vinculada circular.
- Lista doblemente vinculada circular.
Lista vinculada circular por separado –El comportamiento de una lista vinculada individualmente puede ser fácilmente aplicable aquí con la especialización de la naturaleza circular. Entonces, los pasos que hemos seguido para construir la lista vinculada individualmente serán los mismos. Pero solo se puede realizar una modificación en el puntero del último nodo que apunta al primer nodo.
Lista circular doblemente vinculada
La lista circular vinculada también se puede implementar con la ayuda de una lista doblemente vinculada. Al igual que en la lista vinculada circular, hemos tomado un puntero de cola que apunta a un nodo anterior a la cabeza. No es obligatorio aquí. Para la implementación, podemos modificar los punteros solo con la implementación habitual de una lista doblemente vinculada.
Tipos de Listas enlazadas circulares
Listas enlazadas simples circulares
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.
Listas enlazadas doblemente circulares
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.
Actividad en Clase