listas enlazadas

23
Listas Simplemente Enlazadas María Luisa Velasco Ramírez

Upload: maria-luisa-velasco

Post on 11-Jul-2015

3.254 views

Category:

Travel


1 download

TRANSCRIPT

Page 1: Listas enlazadas

Listas Simplemente Enlazadas

María Luisa Velasco Ramírez

Page 2: Listas enlazadas

Listas Enlazadas

• Una representación enlazada de un grupo de elementos de un cierto tipo es una lista enlazada de nodos, es decir, una

• secuencia de nodos situados en la memoria dinámica y conectados entre sí

• Ejemplo: lista de enteros {4, 8, 5, 3, 2}

Page 3: Listas enlazadas
Page 4: Listas enlazadas

• Como se ha visto, un nodo tiene dos atributos:

El dato, de tipo genérico (para poder guardar cualquier tipo de objeto)

• Una referencia al nodo siguiente.

Page 5: Listas enlazadas

• public class Nodo { int dato;

• Nodo siguiente;• public Nodo(int dato) {

this.dato = dato; this.siguiente = null; }

• }

Page 6: Listas enlazadas

• Una lista enlazada requiere, como mínimo, una referencia al primer nodo de la lista:

• Cuando la lista está vacía, el atributo primero apunta a null:

primero = null;

Page 7: Listas enlazadas

• public void creaListaEnlazada()• {• primero=null;• }• public boolean estaVacia()• {• return primero==null;• }

Page 8: Listas enlazadas

Operaciones básicas con listas

• Crear Lista• Recorrido de la Lista • Inserción de un Elemento • Borrado de un Elemento • Búsqueda de un Elemento

Page 9: Listas enlazadas

• Lo más eficiente es insertar al principio de la lista, pues tenemos una referencia al primer nodo

Ejemplo: Se quiere insertar el elemento “1” en la siguiente lista:

Page 10: Listas enlazadas

• public void insertarPrimero(int dato)• {• //crea un nuevo Nodo• Nodo nuevoNodo = new Nodo(dato);

• nuevoNodo.siguiente=primero;• primero=nuevoNodo;•

Page 11: Listas enlazadas

• public void desplegarLista()• {• Nodo actual=primero;• while (actual!= null)• {• System.out.println(“El dato es:”+actual.dato);• actual= actual.siguiente;• }

• }

Page 12: Listas enlazadas

Código para insertar nodos a la derecha

Page 13: Listas enlazadas

• Para insertar nodos a la derecha, es necesario declarar e inicializar otra variable , en este caso es último

Page 14: Listas enlazadas

Código ListaEnlazada

Nodo primero; Nodo ultimo;

primero=null;ultimo=null;

Declaración de las variables primero y ultimo

Inicializar primero y ultimo

Page 15: Listas enlazadas

public boolean estavacia(){return primero==null;

}public void insertarUltimo (int dato){//crea un nuevo nodo

Nodo nuevoNodo=new Nodo( dato);

if(primero==null){ nuevoNodo.siguiente=primero;

primero=nuevoNodo; ultimo=nuevoNodo;

}else{

nuevoNodo.siguiente=null; ultimo.siguiente=nuevoNodo;

ultimo=nuevoNodo;}

}

Método modificado para que los nodos se inserten a la derecha

nuevoNodo.siguiente será igual a null en vez de primeroSe le agrega

una condicion para que inserte a la derecha

Page 16: Listas enlazadas

public void desplegarLista(){Nodoactual=primero;while(actual!=null){

System.out.println(“”+actual.dato);actual=actual.siguiente;

}

}

Método para imprimir

Page 17: Listas enlazadas

do{System.out.print("Introduce el dato del nodo");System.out.flush();dato=Integer.parseInt(entrada.readLine());

lista.insertarUltimo(dato);//insertar nodo a la listaSystem.out.print("Deseas seguir insertando datos: SI=1, NO=0");System.out.flush();opc=Integer.parseInt(entrada.readLine());

}while(opc==1);lista.desplegarLista();

Invocación al método insertarUltimo

Page 18: Listas enlazadas

De manera gráfica sería:

id dato opc InsertarPrimero(id, dato)

1

2

3

4

21.5

15.8

12.4

40.2

1

1

1

0

21.5 1

15.8 2 21.5 1

12.4 3 15.8 221.5 1

40.2 4 12.4 3 15.8 221.5 1

null

null

null

null

Primero

Primero

Primero

Primero

Ultimo

Ultimo

Ultimo

y Ultimo

Page 19: Listas enlazadas

Eliminar nodo

• public NodoLista eliminarPrimero()• {• Nodo temp = primero;• primero = primero.siguiente;• return temp;• }

Page 20: Listas enlazadas

Tarea:

• Implementar en Java, un menú con las siguientes operaciones:

• A) Crear lista enlazada• B) Insertar a la cabeza de la lista• C) Insertar al final de la lista• D) Borrar el elemento inicial de la lista• E)Borrar el último elemento de la lista• F) Desplegar los elementos de la lista• Deben validar al borrar elementos de la lista que la

lista no este vacía

Page 21: Listas enlazadas

• Escribir un algoritmo que inserte un específico elemento de la lista

• Escribir un algoritmo que busque un elemento en la lista y lo visualice en pantalla, en caso de no encontrarlo, mandar el mensaje correspondiente.

• Escribir un algoritmo que borre un elemento específico de la lista. Ver ejemplo de la diapositiva siguiente.

Page 22: Listas enlazadas

Eliminar Nodos

Page 23: Listas enlazadas

Listas enlazadas vs. Arreglos