Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

LISTAS CIRCULARES DOBLEMENTE LIGADAS

No description
by

Armando Jiménez

on 26 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of LISTAS CIRCULARES DOBLEMENTE LIGADAS

En las listas circulares dobles, nunca se llega a una posición en la que ya no sea posible desplazarse.
Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento

Nodos Centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo, nodo ficticio o nodo cabeza) al principio y/o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.

Las operaciones basicas de una lista circular doble son:
Una lista doble circular es una estructura donde el último elemento tiene como referencia siguiente al primer elemento y la referencia al anterior del primer elemento de la lista también es el último.

Es una especie de lista enlazada  “doblemente enlazada”, pero que posee una característica adicional para el desplazamiento dentro de la lista, “ésta no tiene fin”  y tiene 2 apuntadores a si misma.

LISTAS CIRCULARES DOBLEMENTE LIGADAS
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 y así mantener el orden tan bien como en una lista doblemente enlazada.
Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el 1er elemento y  el puntero anterior del primer elemento apuntara hacia el ultimo elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas.

Insertar
Eliminar
Buscar
Imprimir

A través del uso de listas dobles podemos acceder a los datos recorriendo los hacia delante hasta el final o hacia atrás hasta el inicio.
Función de inserción
El primer paso es crear un nodo para el dato que vamos a insertar.
Si Lista está vacía, o el valor del primer elemento de la lista es mayor que el del nuevo, insertaremos el nuevo nodo en la primera posición de la lista.

En caso contrario, buscaremos el lugar adecuado para la inserción, tenemos un puntero "anterior". Lo inicializamos con el valor de Lista, y avanzaremos mientras anterior->siguiente no sea NULL y el dato que contiene anterior->siguiente sea menor o igual que el dato que queremos insertar.
Ahora ya tenemos anterior señalando al nodo adecuado, así que insertamos el nuevo nodo a continuación de él.

Para ésta operación podemos encontrar tres casos diferentes: Eliminar un nodo cualquiera, que no sea el apuntado por lista. Eliminar el nodo apuntado por lista, y que no sea el único nodo. Eliminar el único nodo de la lista. En el primer caso necesitamos localizar el nodo anterior al que queremos borrar. Como el principio de la lista puede ser cualquier nodo, haremos que sea precisamente lista quien apunte al nodo anterior al que queremos eliminar. Esto elimina la excepción del segundo caso, ya que lista nunca será el nodo a eliminar, salvo que sea el único nodo de la lista. Una vez localizado el nodo anterior y apuntado por lista, hacemos que lista->siguiente apunte a nodo->siguiente. Y a continuación borramos nodo.

Función "Borrar"
Localizamos el nodo de valor v
¿Existe?
SI:
¿Es el nodo apuntado por lista?
SI: Hacer que lista apunte a otro sitio.
¿Es el primer nodo de la lista?
NO: nodo->anterior->siguiente = nodo->siguiente
¿Es el último nodo de la lista?
NO: nodo->siguiente->anterior = nodo->anterior
Borrar nodo


Buscar un elemento en una lista circular:
A la hora de buscar elementos en una lista circular sólo hay que tener una precaución, es necesario almacenar el puntero del nodo en que se empezó la búsqueda, para poder detectar el caso en que no exista el valor que se busca. Por lo demás, la búsqueda es igual que en el caso de las listas abiertas, salvo que podemos empezar en cualquier punto de la lista.

Función Mostrar lista
Para mostrar la lista completa, es necesario posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego, utilizando el puntero siguiente de cada elemento, la lista es recorrida del 1er al ultimo elemento.  Mostrar la lista sin una condición para detenerse.

Full transcript