• Author / Uploaded
• Luis Tena

Citation preview

Listas enlazadas circulares En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer un lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para "ingerir" datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros Listas enlazadas circulares simples 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.

**Què es una lista?Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo,donde el orden de los mismos seestablece mediante punteros. La idea básica es que cada componente de la listaincluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista. El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista. Las operaciones que podemos realizar sobre una lista enlazada son las siguientes: 

Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.



Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:



o

Insertar un nodo al inicio.

o

Insertar un nodo antes o después de cierto nodo.

o

Insertar un nodo al final.

Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:



o

Eliminar el primer nodo.

o

Eliminar el último nodo.

o

Eliminar un nodo con cierta información.

o

Eliminar el nodo anterior o posterior al nodo cierta con información.

Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.

Se dice que una lista enlazada es circular cuando el último nodo apunta al primero, como se muestra en la siguiente figura.

Para insertar nodos en una lista circular consideramos dos casos:



Cuando la lista está vacía. En este caso el nodo hacemos que apunte así mismo o sea nodo->siguiente = nodo, y este viene a ser el puntero de la lista (Lc=nodo).



Cuando la lista no está vacía. Hacemos que nodo->siguiente apunte a Lc->siguiente, después, y este viene a ser el puntero de la lista ( Lc=nodo);

**

4.5 Listas Circulares

Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero

La siguiente figura es una representación gráfica de una lista circular.

Enseguida se mostrarán los algoritmos más comunes en listas circulares. Al igual que en las secciones anteriores, utilizaremos el apuntador top para hacer referencia al primer nodo en la lista. Algoritmo de creación repite new(p) lee(p(dato)) si top=nil entonces top