Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Lista circular
Definición
Una lista circular es una colección de elementos llamados
nodos, organizados de tal manera que el siguiente del
ultimo nodo apunta al nodo cabecera
Lista circular
23
dato
siguiente
dato
51
siguiente
dato
siguiente
El campo siguiente del ultimo nodo, aquel cuyo dato es 51,
apunta al nodo cabecera
Lista circular
Definición
Una lista circular es una estructura de datos dinámica
que permite almacenar cualquier cantidad de nodos.
Tiene la ventaja de que procesos de búsqueda o de
manipulación de los datos que requieran recorrer la lista
completa más de una vez se realizan eficientemente
Lista circular
Definición
Las operaciones sobre una lista enlazada son:
•Crear lista circular
•Insertar nodo al inicio
•Eliminar nodo al inicio
•Imprimir datos
•Es una lista circular vacía?
Lista circular
•Crear lista circular
Al crear una lista circular, se crea el nodo cabecera.
El nodo cabecera tiene como dato null y como siguiente
null.
Lista circular
•Insertar nodo al inicio( La lista circular está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y con
siguiente al nodo cabecera
•El campo siguiente del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
W
Lista circular
•Insertar nodo al inicio( La lista no está vacía)
W
A
W
•Se crea un nuevo nodo con el dato que se desee colocar y en su campo
siguiente se establece el siguiente del nodo cabecera
•Al nodo cabecera se le asigna como siguiente el nodo que estamos
insertando
Lista circular
•Eliminar nodo al inicio(La lista circular tiene mas de un nodo)
A
W
W
•Al nodo cabecera se le asigna como siguiente, el siguiente del primer nodo
Lista circular
•Eliminar nodo al inicio(La lista circular tiene un nodo)
W
•Al campo siguiente del nodo cabecera se le asigna null
Lista circular
•Imprimir datos
Lista circular
•Está una lista vacía?
Cuando la lista está vacía el campo siguiente de la
cabecera es null
Lista circular
class Nodo{
Object dato;
Nodo siguiente;
Nodo(Object o)
{
dato=o;
siguiente=null;
}
Nodo(Object o, Nodo n)
{
dato=o;
siguiente=n;
}
}
Cada nodo se
representa por medio
de dos campos:
Campo dato: contiene
el valor del nodo
Campo siguiente:
indica cuál es el nodo
con el que se enlaza
Lista circular
Crear lista circular
class ListaC{
Nodo cabecera;
ListaC()
{
cabecera=new Nodo(null);
}
Al crear una lista
circular, se crea el nodo
cabecera.
El nodo cabecera tiene
como dato null y como
siguiente null.
Lista circular
public boolean estaVacia(){
if (cabecera.siguiente==null)
•Está una lista
circular vacía?
{
return true;
}
else
{
return false;
}
}
Cuando la lista está
vacía el campo
siguiente de la
cabecera es null
Lista circular
void insertar(Object o)
{
Nodo nuevo=new Nodo(null);
if ( estaVacia() )
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera;
cabecera.siguiente=nuevo;
}
Insertar nodo al inicio
( La lista circular está
vacía)
•Se crea un nuevo nodo con
el dato que se desee colocar y
con siguiente al nodo
cabecera
•El campo siguiente del nodo
cabecera pasa de ser null a
ser el nodo que estamos
insertado
Lista circular
void insertar(Object o)
{
Nodo nuevo=new Nodo(null);
if ( estaVacia() )
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera;
cabecera.siguiente=nuevo;
}
else
{
nuevo=new Nodo(o);
nuevo.siguiente=cabecera.siguiente;
cabecera.siguiente=nuevo;
}
}
Insertar nodo al inicio
( La lista circular no está vacía)
•Se crea un nuevo nodo con el
dato que se desee colocar y en
su campo siguiente se
establece el siguiente del nodo
cabecera
•Al nodo cabecera se le asigna
como siguiente el nodo que
estamos insertando
Lista circular
public void eliminar()
{
Nodo borrar=cabecera.siguiente;
if (borrar.siguiente==cabecera)
cabecera.siguiente=null;
else{
cabecera.siguiente=borrar.siguiente;
}
}
Eliminar nodo al inicio
•Al campo siguiente del nodo cabecera
se le asigna null, si solo hay un nodo
•Al nodo cabecera se le asigna como
siguiente, el siguiente del primer
nodo, si la lista circular tiene más de
un nodo
LISTA DOBLEMENTE
ENLAZADA
Lista doblemente enlazada
Definición
Una lista doblemente enlazada es una colección de
elementos llamados nodosDE
Un nodoDE tiene tres campos: un campo izquierda, un
campo dato y un campo derecha. Los campos izquierda y
derecha son apuntadores a los nodos ubicados en el lado
izquierdo y el derecho de cada nodo
Lista doblemente enlazada
izq. dato der.
51
99
izq. dato der.
izq. dato der.
•Se mantiene un nodoDE cabecera, cuyo campo izquierda apunta a
null, no tiene valor y cuyo campo derecha apunta al nodoDE que
tiene el primer dato
•El campo derecha del ultimo nodoDE apunta a null
Lista doblemente enlazada
Definición
Una lista doblemente enlazada es una estructura de datos
dinámica que permite almacenar cualquier cantidad de
nodos.
Tiene la ventaja de que estando en cualquier nodo se
puede acceder al nodo que está tanto a la izquierda como
a la derecha
Lista doblemente enlazada
Definición
Las operaciones sobre una lista doblemente enlazada son:
•Crear listaDE
•Insertar nodo al inicio
•Eliminar nodo al inicio
•Imprimir datos
•Es una listaDE vacía?
Lista doblemente enlazada
•Crear lista doblemente enlazada
Al crear una listaDE, se crea el nodo cabecera.
El nodo cabecera tiene como dato, izquierda y derecha
a null.
Lista doblemente enlazada
•Insertar nodo al inicio( La listaDE está vacía)
9
•Se crea un nuevo nodoDE con
el dato que se desee colocar,
campo izquierda apuntado al
nodo cabecera y campo derecha
apuntando a null
•El campo derecha del nodo
cabecera pasa de ser null a ser el
nodo que estamos insertado
Lista doblemente enlazada
•Insertar nodo al inicio( La listaDE no está vacía)
9
1
9
•Se crea un nuevo nodo con el dato que se desee colocar, campo izquierda
apuntando al nodo cabecera y campo derecha apuntado al nodo que
apunta el campo derecha del nodo cabecera
•Al campo izquierda del nodo apuntado por derecha del nodo cabecera se
le asigna el nodo que estamos insertando
•Al nodo cabecera se le asigna como derecha al nodo que estamos
insertando
Lista doblemente enlazada
•Eliminar nodo al inicio
1
9
9
•Al nodo cabecera se le asigna como derecha, la derecha del primer nodo
•Al campo izquierda del segundo nodo se le asigna como izquierda el
nodo cabecera (Solo si hay más de un nodo)
Lista doblemente enlazada
•Imprimir datos
Lista doblemente enlazada
•Está una listaDE vacía?
Cuando la lista está vacía el campo derecha de la
cabecera es null
Lista doblemente enlazada
public class NodoDE
{
NodoDE izquierda;
Object dato;
NodoDE derecha;
public NodoDE(Object o)
{
izquierda = null;
dato = o;
derecha = null;
}
Lista doblemente enlazada
Crear listaDE
class ListaC{
Nodo cabecera;
•Al crear una listaDE,
ListaC()
{
cabecera=new Nodo(null);
}
•El nodo cabecera tiene
se crea el nodo
cabecera.
como dato, izquierda y
derecha a null.
Lista doblemente enlazada
public boolean esVacia( )
{
if (cabecera.derecha==null)
return true;
else
return false;
}
•Está una lista
circular vacía?
Cuando la lista está
vacía el campo
derecha de la
cabecera es null
Lista doblemente enlazada
public void insertarDE(Object o)
{
if (esVacia()){
NodoDE nuevo = new NodoDE(o);
cabecera.derecha=nuevo;
nuevo.izquierda=cabecera;
nuevo.derecha=null;
}
Insertar nodo al inicio
( La listaDE está vacía)
•Se crea un nuevo nodoDE
con el dato que se desee
colocar, campo izquierda
apuntado al nodo cabecera y
campo derecha apuntando a
null
•El campo derecha del nodo
cabecera pasa de ser null a
ser el nodo que estamos
insertado
Lista doblemente enlazada
else{
NodoDE nuevo = new NodoDE(o);
NodoDE primero=cabecera.derecha;
Insertar nodo al inicio
( La listaDE no está vacía)
•Se crea un nuevo nodo con el dato
nuevo.derecha=cabecera.derecha;
nuevo.izquierda=cabecera;
primero.izquierda=nuevo;
cabecera.derecha=nuevo;
}
que se desee colocar, campo
izquierda apuntando al nodo
cabecera y campo derecha apuntado
al nodo que apunta el campo derecha
del nodo cabecera
}
•Al campo izquierda del nodo
apuntado por derecha del nodo
cabecera se le asigna el nodo que
estamos insertando
•Al nodo cabecera se le asigna como
derecha al nodo que estamos
insertando
Lista doblemente enlazada
public void eliminarDE()
{
NodoDE eliminar=cabecera.derecha;
NodoDE derechaEliminar=eliminar.derecha;
if(esVacia())
System.out.println("LA LISTADE ESTA VACIA");
else{
cabecera.derecha=eliminar.derecha;
derechaEliminar.izquierda=cabecera;
}
}
Eliminar nodo al inicio
•Al nodo cabecera se le
asigna como derecha, la
derecha del primer nodo
•Al campo izquierda del
segundo nodo se le asigna
como izquierda el nodo
cabecera
Descargar

La lista circular está vacía