listas circulares en java

34
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

Upload: segundo-sanchez-idrogo

Post on 11-Feb-2016

118 views

Category:

Documents


1 download

DESCRIPTION

listas circulares en java

TRANSCRIPT

Page 1: listas circulares en java

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

Page 2: listas circulares en java

Lista circular

El campo siguiente del ultimo nodo, aquel cuyo dato es 51, apunta al nodo cabecera

dato siguiente

dato siguiente

23 51

dato siguiente

Page 3: listas circulares en java

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

Page 4: listas circulares en java

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?

Page 5: listas circulares en java

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.

Page 6: listas circulares en java

•Insertar nodo al inicio( La lista circular está vacía)

W

•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

Page 7: listas circulares en java

•Insertar nodo al inicio( La lista no está vací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

A W

Lista circular

Page 8: listas circulares en java

•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

Page 9: listas circulares en java

•Eliminar nodo al inicio(La lista circular tiene un nodo)

W

•Al campo siguiente del nodo cabecera se le asigna null

Lista circular

Page 10: listas circulares en java

•Imprimir datos

Lista circular

Page 11: listas circulares en java

•Está una lista vacía?

Cuando la lista está vacía el campo siguiente de la cabecera es null

Lista circular

Page 12: listas circulares en java

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

class Nodo{

Object dato; Nodo siguiente;

Nodo(Object o) { dato=o; siguiente=null; }

Nodo(Object o, Nodo n) { dato=o; siguiente=n; }}

Lista circular

Page 13: listas circulares en java

Crear lista circularAl crear una lista circular, se crea el nodo cabecera.El nodo cabecera tiene como dato null y como siguiente null.

class ListaC{

Nodo cabecera;

ListaC() { cabecera=new Nodo(null); }

Lista circular

Page 14: listas circulares en java

•Está una lista circular vacía?

Cuando la lista está vacía el campo siguiente de la cabecera es null

public boolean estaVacia(){

if (cabecera.siguiente==null)

{

return true;

}

else

{

return false;

}

}

Lista circular

Page 15: listas circulares en java

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

void insertar(Object o) { Nodo nuevo=new Nodo(null);

if ( estaVacia() ) { nuevo=new Nodo(o); nuevo.siguiente=cabecera; cabecera.siguiente=nuevo; }

Lista circular

Page 16: listas circulares en java

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

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; } }

Lista circular

Page 17: listas circulares en java

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

public void eliminar() { Nodo borrar=cabecera.siguiente;

if (borrar.siguiente==cabecera) cabecera.siguiente=null; else{ cabecera.siguiente=borrar.siguiente; } }

Lista circular

Page 18: listas circulares en java

LISTA DOBLEMENTE LISTA DOBLEMENTE

ENLAZADAENLAZADA

Page 19: listas circulares en java

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

Page 20: listas circulares en java

Lista doblemente enlazada

•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

izq. dato der.

5511

9999

izq. dato der. izq. dato der.

Page 21: listas circulares en java

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

Page 22: listas circulares en java

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?

Page 23: listas circulares en java

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.

Page 24: listas circulares en java

•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

99

Lista doblemente enlazada

Page 25: listas circulares en java

•Insertar nodo al inicio( La listaDE no está vacía)

•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

99

11 99

Lista doblemente enlazada

Page 26: listas circulares en java

•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 (Solo si hay más de un nodo)

11 99

99

Lista doblemente enlazada

Page 27: listas circulares en java

•Imprimir datos

Lista doblemente enlazada

Page 28: listas circulares en java

•Está una listaDE vacía?

Cuando la lista está vacía el campo derecha de la cabecera es null

Lista doblemente enlazada

Page 29: listas circulares en java

public class NodoDE{ NodoDE izquierda; Object dato; NodoDE derecha;

public NodoDE(Object o) { izquierda = null; dato = o; derecha = null; }

Lista doblemente enlazada

Page 30: listas circulares en java

Crear listaDE

•Al crear una listaDE, se crea el nodo cabecera.•El nodo cabecera tiene como dato, izquierda y derecha a null.

class ListaC{

Nodo cabecera;

ListaC() { cabecera=new Nodo(null); }

Lista doblemente enlazada

Page 31: listas circulares en java

•Está una lista circular vacía?

Cuando la lista está vacía el campo derecha de la cabecera es null

public boolean esVacia( ) { if (cabecera.derecha==null) return true; else return false; }

Lista doblemente enlazada

Page 32: listas circulares en java

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

public void insertarDE(Object o) { if (esVacia()){ NodoDE nuevo = new NodoDE(o); cabecera.derecha=nuevo; nuevo.izquierda=cabecera; nuevo.derecha=null; }

Lista doblemente enlazada

Page 33: listas circulares en java

Insertar nodo al inicio( La listaDE no está vacía)

•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

else{ NodoDE nuevo = new NodoDE(o); NodoDE primero=cabecera.derecha; nuevo.derecha=cabecera.derecha; nuevo.izquierda=cabecera; primero.izquierda=nuevo; cabecera.derecha=nuevo; } }

Lista doblemente enlazada

Page 34: listas circulares en java

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

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; }

}

Lista doblemente enlazada