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.

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

Ventajas y desventajas Ventajas Con esta disposición se accede a cualquier elemento de la estructura de datos en tiempo constante. Desventajas Al asignar el arreglo en tiempo de compilación debe establecerse un límite a priorisobre el número de elementos que pueden ser almacenados en las listas. Para inserciones y eliminaciones frecuentes hay

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

primero

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

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.

LISTA DE ENLACE SIMPLE: 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 BYB Conecta Con C Y C Es El Nodo Final:

Lista doblemente enlazada primero

…

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.

Lista enlazada circular

primero

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

Lista doblemente enlazada circular

primero

…

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.

Ventajas y desventajas Ventajas 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. Desventajas No 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.

LISTA - OPERACIONES 1. Recorrerla . 2. Busc ar e lem entos. 3. Inse r ta r ele mentos. 4. Elim inar ele me nt os. 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. Bus car un e le ment o: - 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 En cuentra. 3. Ins er ta r elem ent o: - 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. Elimi nar un el emen to: 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 - CONSTRUCTORES - CONSTRUIRLA

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 - METODOS - CONSTRUIRLA void ad d(String it em) e void add (String it em , int ind ex) , 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.

LISTA - METODOS - CONSTRUIRLA int[] getSelectedIndexes(), da los índices de los elementos seleccionados. String getSelectedItem(), da el objeto seleccionaDO String[]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.

LISTA - METODOS - CONSTRUIRLA 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

LISTA - METODOS - CONSTRUIRLA 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:

LISTA - EJERCICIO En nuestro caso utilizaremos la tercera forma de constructor. List lista=new List(0,true);

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

ESTRUCTURAS LINEALES OPERACIONES CON LISTAS

Un a in ter fa z L ist pub lic int er face L is t { pub lic boo le an is Emp ty( ); pub lic void ad dFir st ( O bj ect o ); pub lic void ad dLas t( Object o ) ; pub lic boo le an co ntains (obj ect o) ; pub lic boo le an remo ve(Obje ct o ); pub lic ob ject remo veF ir st( ) thr ows No Suc hEl ement Excep tio n; pub lic void clear( ); pub lic int siz e( ); }

ESTRUCTURAS LINEALES LIS TAS

EST RATEGIA S D E IM PLEMEN TACIÓ N D E

• Exi st en Muc has F ormas De Imp lement ar Una L ist a. • En Imp le ment acione s Bas ad as En Arr ays c omo El Vect or D e Ja va, Inse r tar Un Eleme nt o En C ualquie r Lug ar Que No S ea el Fi nal D e La L is ta P ued e Ser C omp lej o, Ya Q ue Tod os Lo s Elem ent os Q ue Se Encuentran Entre El P unt o D e Ins er ció n y El Final D e La Lis ta D eb erán De sp laz ar se Una Pos ició n P ara Dejar Hue co Par a La N ue va Entrad a. O curr e Alg o

ESTRUCTURAS LINEALES Li st as enlaz ad as s enci llas • Las L istas Enl az ad as Son Como T renes D e Me rcancías . • Cad a Eleme nt o Q ue Q ue Se V a A P one r En L a Lis ta Est á Co nt enid o En Una Inst ancia D e Un N ue vo T ip o D e O bjet o, Ll amad o Enlace, Que Eq uiva le A U n V agón Del Tren. • En Una L is ta Enlaz ad a Sen cilla, El Enlace No Só lo Conti ene El Eleme nt o D e L a L ist a, Sino Q ue T amb ié n A punta Al Si guient e Eleme nt o D e La L is ta, A l Ig ual Q ue Un Vag ón De M er cancí as Está A co plad o A l S ig uien te. • El Últ imo Enlace De L a L ista No A punta A N ad a.

ESTRUCTURAS LINEALES List as enlaz adas s enc illas , • El O bjeto D e La L is ta, En Sí Mi smo , A punta Al Enlace Que Co ntie ne El Prime r Eleme nt o M os trad o Y S uele Incluir U na R ef erencia Adicio nal Al Últ imo Enlace De La Li sta Para Facil itar La Incor poració n D e Eleme nt os . • Se Di ce Q ue Un Enlace “Conti ene “ Ap unta A” Y Q ue La Instanci a D e L a Li st a “ Apunta” o “Conti ene U n Pu nter o” En Ja va, T odo s Ell os S on Sinónim os D e Cont ene r Una R ef erenci a. • El Enlace R ealm ent e N o Co ntie ne El Eleme nt o, Sino U na Referencia Q ue S eñala Al Eleme nt o De La Lis ta.

ESTRUCTURAS LINEALES Demo stració n d e una lis ta e nlaz ad a s encil la Li st : Int er faz De L ista SL ink ed Li st : Impl em entaci ón De Lis ta SL ink ed Li st ap p: Ap lic ació n Main( ) SL ink ed Li st vie w: GU I De L is ta MIEM BROS DE DATOS DE S LINK ED LIST • Sól o Es Nece sario F ir st ( Pr imer o) . • Las t ( Último ) Y L eng th (Lo ng it ud ) S e P ued en Encont rar A l Recorrer La Lis ta, Pero Si Se C ons er van Y Se Act ualiz an Est os M iem bros, La L lamad a A Siz e() Y A App end () Es Muc ho Más R áp id a. Priv at e Int Le ng th = 0; Priv at e S Link F ir st = Null;

ESTRUCTURAS LINEALES == y el mét od o O bject equals • Co ntains ( O bject O ) Y Remo ve( O bje ct O ) De ben Bu scar O bject O En L a L ist a. Per o, ¿ Qué Imp li ca Enco ntrarlo ? • ¿D eb e Cont ene r La L is ta Una Ref erencia Al Obje to Id ént ico (==) ? ¿O Bas ta Co n Q ue C ont eng a Una Referencia A Un Objet o Equ iv al en te Pero Po sibl em ent e Dis ti nt o? static privat e boo le an o bje ctEquals ( O bject a, O bje ct b ) { if ( a == null ) re tur n ( b == null ); e ls e re tur n a.Equals ( b );

ESTRUCTURAS LINEALES remo veFi rst( ) pub lic ob ject remo veF ir st( ) thr ows no suc he lem ent exce ptio n { if ( f ir st == nul l ) // s i la li sta es tá vacía thr ow new no Suc hElem entEx cep tio n( ); e lse { slink t = fir st ; fir st = f ir st.ne xt ; // si la l ist a t enía 1 ele ment o y aho ra es tá vacía if ( f ir st == null ) las t = nul l; le ng th--; re turn t.it em ; } }