Listas

TDA LISTA LINEAL

Una lista lineal es un conjunto de N nodos l1, l2, … ln, con n 0, cuyas propiedades estructurales esenciales incluyen sólo las posiciones lineales (unidimensionales) relativas de los nodos; para ella se definen operaciones como las siguientes:• Tener acceso a un nodo.• Insertar y eliminar un nodo en la lista.• Combinar dos o más listas en una.• Dividir una lista en dos o más listas.• Determinar la cantidad de nodos de la lista.• Ordenar la lista de acuerdo a un criterio.• Buscar un elemento bajo una condición.

TDA LISTA LINEAL

Aclaraciones: • n = 0 denota a la lista vacía, o sea, una lista que no tiene elementos. • Si n > 0, l1 es el primer nodo.• Si 1 < k < n, lk es precedido por el nodo lk+1 y seguido por el nodo lk+1.

• Si n > 0, IN es el último nodo.

TDA LISTA LINEAL

Una misma definición de un TDA puede conllevar a implementaciones diferentes en dependencia de las necesidades, así como de las características del lenguaje en el que se va a desarrollar dicha implementación.

Por su forma de almacenamiento, la lista lineal se puede implementar en una de las siguientes disposiciones:• Secuencial• Enlazada

LISTA SECUENCIAL

Una de las formas más simples de implementación de este TDA es usando un arreglo unidimensional.

Todos los elementos de la lista se almacenan en posiciones de memoria consecutivas. Por se habla de disposición secuencial en la memoria de la computadora.

A la lista se le conoce como lista secuencial.

LISTA SECUENCIAL

. . . 1 2 3 4 5 N Índice del último Cantidad física nodo de la lista de elementos del arreglo

VENTAJAS Y DESVENTAJAS

VentajasCon esta disposición se accede a cualquier elemento de la estructura de datos en tiempo constante.

DesventajasAl asignar el arreglo en tiempo de compilación debe establecerse un límite a priori sobre el número de elementos que pueden ser almacenados en las listas.

Para inserciones y eliminaciones frecuentes hay que hacer corrimientos costosos.

LISTA ENLAZADA

En una lista enlazada se asigna memoria para el almacenar los elementos de la lista conforme se va necesitando, es decir a medida que se añaden o insertan los elementos, y se conectan los elementos de la lista con punteros.

La memoria es liberada cuando ya no se necesita más un elemento en la lista.

Esquemáticamente una lista enlazada se representa por una secuencia de nodos conectados por enlaces.

LISTA ENLAZADA

Cada nodo está conectado al siguiente por un solo enlace, a esta estructura de datos se llama lista simplemente enlazada.

primero

LISTA ENLAZADA

Un nodo de una lista simplemente enlazada contiene dos campos: datos (contiene un elemento de la lista) y siguiente (almacena un enlace al siguiente nodo de la lista).

El campo siguiente del último nodo contiene un símbolo especial que indica el final de las lista.

Se accede a la lista por medio de un apuntador al primer elemento y solo se puede recorrer la lista en un sentido, del primer nodo al último nodo.

1. Es Una Lista Enlazada De Nodos, 2. Cada Nodo Tiene Un Único Campo De Enlace. 3. Una Variable De Referencia Contiene Una Referencia Al Primer Nodo, Cada Nodo (Excepto El Último) Enlaza Con El Nodo Siguiente, 4. El Enlace Del Último Nodo Contiene Null Para Indicar El Final De La Lista. 5. La Variable De Referencia Se La Suele Llamar Top, CAB,*,+,-6. Tiene Tres Nodos, Donde Top Referencia Al Nodo A, A Conecta Con B Y B Conecta Con C Y C Es El Nodo Final:

LISTA DE ENLACE SIMPLE:

LISTA DOBLEMENTE ENLAZADA

Cada nodo contiene tres campos: un campo que almacena el elemento de la lista y los otros dos almacenan los enlaces a los nodos precedente y siguiente de la lista.

Se usan punteros nulos para marcar ambos extremos de la lista.

primero …

LISTA ENLAZADA CIRCULAR

El campo siguiente del último nodo de la lista apunta al primer nodo de la lista.

primero

LISTA DOBLEMENTE ENLAZADA CIRCULAR

El campo siguiente del último nodo apunte al primer nodo de la lista y el campo anterior del primer nodo apunte al último nodo de la lista.

primero…

VENTAJAS Y DESVENTAJASVentajas

No es preciso conocer la cantidad de elementos en tiempo de compilación.Ni las inserciones ni las eliminaciones implican realizar corrimientos de los elementos de la lista.

DesventajasNo permite el acceso directo a un elemento arbitrario de la lista. Para acceder al i-ésimo elemento, debemos recorrer la lista, comenzando por el primer nodo, hasta llegar al elemento deseado.

1. RECORRERLA. 2. BUSCAR ELEMENTOS. 3. INSERTAR ELEMENTOS. 4. ELIMINAR ELEMENTOS. 5. VACIARLA.

LISTA - OPERACIONES

1. RECORRER: - Implementada Como Una Acción Puesto Que No Retorna Ningún Valor. - Recibe Como Argumento La Cabeza De La Lista. - Mostrará Por Pantalla Todos Los Elementos Almacenados.2. BUSCAR UN ELEMENTO: - Implementada Como Una Función. - Recibe Como Argumento Un Número Entero. - Retornar Un Puntero Al Primer Nodo Que Tenga Como Valor El Entero Recibido O NULL Si No Lo Encuentra.3. INSERTAR ELEMENTO: - Implementada Como Una Acción. - Recibe Como Argumento Un Número Entero. - Crea Un Nuevo Nodo En La Lista Para Almacenar El Dato Recibido

LISTA OPERACIONES

4. ELIMINAR UN ELEMENTO: Implementada Como Una Acción. Recibe Un Número Entero Como Argumento. Elimina El Primer Nodo De La Lista Que Tenga Asignado Dicho Valor.

5. VACIAR: Implementada Como Acción. No Recibe Argumentos. Elimina Todos Los Elementos De La Lista.

LISTA OPERACIONES

LIST() , CREAR UNA NUEVA LISTA.

LIST(INT ROWS), CREA UNA NUEVA LISTA CON ROWS LÍNEAS

LIST(INT ROWS, BOOLEAN MULTIPLEMODE), CREA UNA NUEVA LISTA CON ROWS LÍNEAS, Y SE LE DICE QUE, SEGÚN EL VALOR BOOLEANO MULTIPLEMODE, SE PODRÁN ELEGIR UNO O MÁS ELEMENTOS DE LA LISTA.

LISTA - CONSTRUCTORES - CONSTRUIRLA

VOID ADD(STRING ITEM) E VOID ADD(STRING ITEM, INT INDEX), PARA COLGAR, AL FINAL DE LA LISTA O EN CIERTA POSICIÓN, UN NUEVO COMPONENTE.

VOID ADDACTIONLISTENER(ACTIONLISTENER L), PARA ASOCIAR UN ACTIONLISTENER A LA LISTA.VOID ADDITEMLISTENER(ITEMLISTENER L), PARA ASOCIAR UN ITEMLISTENER A LA LISTA.STRING GETITEM(INT INDEX), PARA TENER EL ELEMENTO EN POSICIÓN INDICADA.INT GETITEMCOUNT() , PARA OBTENER EL NÚMERO DE LOS ELEMENTOS.

LISTA - METODOS - CONSTRUIRLA

STRING[] GETITEMS(), PARA OBTENER TODOS LOS ELEMENTOS.EVENTLISTENER[] GETLISTENERS(CLASS LISTENERTYPE) , PARA OBTENER LOS OYENTES ASOCIADOS A LA LISTA DEL TIPO QUE QUEREMOS. DIMENSION GETMINIMUMSIZE(), DA EL TAMAÑO MÍNIMO DE LA LISTA.DIMENSION GETPREFERREDSIZE(), DA EL TAMAÑO PREFERIDO PARA LA LISTA.INT GETROWS() , DICE EL NÚMERO DE LÍNEAS AL MOMENTO VISIBLES EN LA LISTA.INT GETSELECTEDINDEX(), DA EL ÍNDICE DEL ELEMENTO SELECCIONADO.


INT[] GETSELECTEDINDEXES(), DA LOS ÍNDICES DE LOS ELEMENTOS SELECCIONADOS.STRING GETSELECTEDITEM(), DA EL OBJETO SELECCIONADOSTRING[]GETSELECTEDITEMS(), DA LOS OBJETOS SELECCIONADOS.OBJECT[] GETSELECTEDOBJECTS(), DA LA LISTA DE LOS ELEMENTOS SELECCIONADOS EN UN VECTOR DE OBJETOS.BOOLEAN ISINDEXSELECTED(INT INDEX), DICE SI EL ÍNDICE ESTÁ SELECCIONADO.BOOLEAN ISMULTIPLEMODE(), DICE SI, EN LA LISTA, SE PUEDEN SELECCIONAR MÁS ELEMENTOS.


VOID MAKEVISIBLE(INT INDEX), VISUALIZA EL ITEM EN LA POSICIÓN INDICADA.VOID REMOVE(INT POSITION), VOID REMOVE(STRING ITEM), ELIMINA LOS ELEMENTOS INDICADOS POR EL ÍNDICE O LA ETIQUETA. VOID REMOVEALL(), ELIMINA TODOS LOS ELEMENTOS DE LA LISTA.VOID REMOVEACTIONLISTENER(ACTIONLISTENER L) E VOID REMOVEITEMLISTENER(ITEMLISTENER L), ELIMINAN LOS OYENTES DE SUCESOS DEFINIDOS PARA LA LISTA.VOID REPLACEITEM(STRING NEWVALUE, INT INDEX), MODIFICA EL ELEMENTO ESPECIFICADO


VOID SELECT(INT INDEX), SELECCIONA EL ELEMENTO INDICADO EN LA LISTA.VOID SETMULTIPLEMODE(BOOLEAN B), DICE A LA LISTA SI ES POSIBLE SELECCIONAR SÓLO UN ELEMENTO O MÁS DE UNO.

EJERCICIO:

GESTIONA LAS RESERVAS DE VISITAS GUIADAS DE ALGUNAS LOCALIDADES Y QUE NOS OBLIGUE A ELEGIR UNA. ADEMÁS DE LAS FORM CONOCIDAS PARA EL NOMBRE, APELLIDOS, ETC.. TENDREMOS LA LISTA DE LAS LOCALIDADES. ANALICEMOS CÓMO PODEMOS IMPLEMENTARLA. PARA CONSTRUIR LA LISTA UTILIZAREMOS UNO DE LOS TRES CONSTRUCTORES:


EN NUESTRO CASO UTILIZAREMOS LA TERCERA FORMA DE CONSTRUCTOR.LIST LISTA=NEW LIST(0,TRUE);

LISTA - EJERCICIO

import java.awt.*;import java.awt.event.*;

public class listas extends Frame{

List lista=new List(0,true);Label text=new Label("Maravillas que se pueden visitar en la localidad elegida");

public listas(){super("Elegir itinerario");

LISTA - EJERCICIO

lista.add("Bienvenido");lista.add("Foiano de Val Fortore");lista.add("Baselice");lista.add("San Bartolomeo en Galdo");lista.add("San Marco de los Cavoti");lista.add("Montefalcone en Val Fortore");lista.add("Pesco Sannita");lista.add("Colle Sannita");lista.add("Castelvetere en Val Fortore");lista.add("Castelfranco en Miscano");lista.add("Ginestra de los Schiavoni");lista.add("San Giorgio la Molara");lista.add("Molinara");lista.add("Pietrelcina");lista.add("Fragneto Monforte");lista.add("Circello");lista.add("Campolattaro");

LISTA - EJERCICIO

add(lista,BorderLayout.CENTER);add(text,BorderLayout.SOUTH);

addWindowListener(new listeWindowListener());lista.addItemListener(new escuchaLista());

setSize(350,100);

setResizable(false);

show();

}

LISTA - EJERCICIO

class listeWindowListener implements WindowListener{

public void windowActivated(WindowEvent e){}

public void windowClosed(WindowEvent e){}

public void windowClosing(WindowEvent e){

LISTA - EJERCICIO

String[] s=lista.getSelectedItems();int i=0;System.out.println("Itinerario seleccionado");try{while (true){

System.out.println(s[i++]);

}

}catch (ArrayIndexOutOfBoundsException er){System.out.println("Qué lo pases bien...");}System.exit(0);}

LISTA - EJERCICIO

public void windowDeactivated(WindowEvent e){}

public void windowDeiconified(WindowEvent e){}

public void windowIconified(WindowEvent e){}

public void windowOpened(WindowEvent e){}

}

class escuchaLista implements ItemListener{

LISTA - EJERCICIO

public void itemStateChanged(ItemEvent e){

int índice=((Integer) e.getItem()).intValue();

if (índice==0) text.setText("Rocca de los Rettori, arco de Trajano, anfiteatro Romano, ciudad espectáculo");if (índice==1) text.setText("localidad San Giovanni, Campanario, via Roma, lago, fiesta S.Giovanni, fiesta del emigrante");

LISTA - EJERCICIO

if (índice==2) text.setText("óasis ds San Leonardo");if (indice==3) text.setText("casco histórico");if (índice==4) text.setText("casco histórico");if (índice==5) text.setText("casco histórico");if (índice==6) text.setText("casco histórico"); if (índice==7) text.setText("casco histórico"); if (índice==8) text.setText("casco histórico"); if (índice==9) text.setText("Bosque"); if (índice==10) text.setText("casco histórico"); if (índice==11) text.setText("Lago de San Giorgio"); if (índice==12) text.setText("casco histórico"); if (índice==13) text.setText("Piana Romana, casco histórico, casas de Padre ío"); if (índice==14) text.setText("Encuentro internacional de globos, Palacio Ducal"); if (índice==15) text.setText("casco histórico"); if (índice==16) text.setText("Dique de Campolattaro"); }

}

}

UNA INTERFAZ LISTpublic interface List {public boolean isEmpty();public void addFirst( Object o );public void addLast( Object o );public boolean contains(object o);public boolean remove(Object o);public object removeFirst()throws NoSuchElementException;public void clear();public int size();}

ESTRUCTURAS LINEALESOPERACIONES CON LISTAS

ESTRATEGIAS DE IMPLEMENTACIÓN DE LISTAS

• Existen Muchas Formas De Implementar Una Lista.• En Implementaciones Basadas En Arrays como El Vector De Java, Insertar Un Elemento En Cualquier Lugar Que No Sea el Final De La Lista Puede Ser Complejo, Ya Que Todos Los Elementos Que Se Encuentran Entre El Punto De Inserción y El Final De La Lista Deberán Desplazarse Una Posición Para Dejar Hueco Para La Nueva Entrada. Ocurre Algo Similar Con La Eliminación.• Las Listas Suelen Utilizar Una Implementación Enlazada. 5

ESTRUCTURAS LINEALES

LISTAS ENLAZADAS SENCILLAS• Las Listas Enlazadas Son Como Trenes De Mercancías.• Cada Elemento Que Que Se Va A Poner En La Lista Está Contenido En Una Instancia De Un Nuevo Tipo De Objeto, Llamado Enlace, Que Equivale A Un Vagón Del Tren.• En Una Lista Enlazada Sencilla, El Enlace No Sólo Contiene El Elemento De La Lista, Sino Que También Apunta Al Siguiente Elemento De La Lista, Al Igual Que Un Vagón De Mercancías Está Acoplado Al Siguiente.• El Último Enlace De La Lista No Apunta A Nada.


LISTAS ENLAZADAS SENCILLAS, • El Objeto De La Lista, En Sí Mismo, Apunta Al Enlace Que Contiene El Primer Elemento Mostrado Y Suele Incluir Una Referencia Adicional Al Último Enlace De La Lista Para Facilitar La Incorporación De Elementos.• Se Dice Que Un Enlace “Contiene “Apunta A” Y Que La Instancia De La Lista “Apunta” o “Contiene Un Puntero” En Java, Todos Ellos Son Sinónimos De Contener Una Referencia.• El Enlace Realmente No Contiene El Elemento, Sino Una Referencia Que Señala Al Elemento De La Lista.• El Último Enlace Contiene Una Referencia Null En El Campo Que Apunta Al Siguiente Elemento.


DEMOSTRACIÓN DE UNA LISTA ENLAZADA SENCILLAList: Interfaz De ListaSLinkedList: Implementación De ListaSLinkedListapp: Aplicación Main()SLinkedListview: GUI De ListaMIEMBROS DE DATOS DE SLINKEDLIST• Sólo Es Necesario First (Primero).• Last (Último) Y Length (Longitud) Se Pueden Encontrar Al Recorrer La Lista, Pero Si Se Conservan Y Se Actualizan Estos Miembros, La Llamada A Size() Y A Append() Es Mucho Más Rápida. Private Int Length = 0;

Private SLink First = Null;Private SLink Last = Null;

12


== Y EL MÉTODO OBJECT EQUALS• Contains( Object O ) Y Remove( Object O ) Deben Buscar Object O En La Lista. Pero, ¿Qué ImplicaEncontrarlo?• ¿Debe Contener La Lista Una Referencia Al Objeto Idéntico(==)? ¿O Basta Con Que Contenga Una Referencia A Un Objeto Equivalente Pero Posiblemente Distinto?static private boolean objectEquals( Object a, Object b ) { if ( a == null ) return ( b == null ); else return a.Equals( b ); }


removeFirst()public object removeFirst()throws nosuchelementexception{

if ( first == null ) // si la lista está vacía throw new noSuchElementException(); else {

slink t = first;first = first.next;// si la lista tenía 1 elemento y ahora

está vacía if ( first == null ) last = null;

length--;return t.item;

}}


Listas

Documents

Transcript of Listas