Ligaas

Cap´ ıtulo 3 Listas
3.1 Introducci´n o

Las listas las tenemos en muchos casos en la vida real: lista de compras, lista de utiles escolares, lista de invitados, lista de pendientes, lista de tareas, lista ´ de discos, etc. Pero, ¿qu´ es una lista? Una lista es una estructura de datos e con la propiedad que se pueden agregar y suprimir datos en cualquier lugar. El tipo de datos Lista debe tenerlas siguientes propiedades: • Determinar si est´ vac´ la lista. a ıa • Limpiar la lista. • Agregar un elemento. • Encontrar un elemento. (por valor). • Actualizar un elemento. • Eliminar un elemento. Como caracter´ ısticas de las listas se tiene que de antemano se desconoce cu´ntos elementos tendr´ ´sta. Es irrelevante el orden de los elementos y el a ae manejo de ellos, es decir las insercionesy supresiones pueden ser de cualquier dato no por posici´n. o La interfaz para la clase de las listas es:

1

´ 3.2. IMPLEMENTACION

2

interface Listable { public boolean est´Vac´a(); a ı public void limpiar(); public Object primerElemento(); public void agregar(Object x); //Inserta al inicio de la lista public boolean contiene(Object x); public void eliminar(Object x); //Borra el primernodo que tenga valor x public void sustituir(Object orig, Object nuevo); public java.util.Iterator elementos(); } Propiedades que se esperan de una lista: • est´Vac´a. Devuelve true si la lista est´ vac´ y false en otro caso. a ı a ıa • limpiar. Elimina todos los elementos de la lista, es decir el tama˜o de n la lista despu´s de esta operaci´n es cero.. e o • primerElemento. Devuelve el valoralmacenado en el primer elemento de la lista. El estado de la lista no se ve alterado. • agregar. Agrega al inicio de la lista el objeto especificado como el par´metro. El tama˜o de la lista crece en una unidad. a n • contiene. Regresa true si el elemento est´ en la lista y false en otro a caso. Este m´todo no cambia el estado de la lista. e • eliminar. Si el elemento existe en la lista lo elimina, encaso contrario dispara la excepci´n NoSuchElementException. En caso de que la o operaci´n sea exitosa se reduce el tama˜o de la lista en una unidad. o n • sustituir. Si el elemento a sustituir se encuentra en la lista lo sustituye por el segundo par´metro, en caso contrario dispara la excepci´n a o NoSuchElementException. Esta operaci´n no altera el tama˜o de la o n lista.

3.2Implementaci´n o

Las listas se pueden implementar con arreglos pero para evitar el costo de recorridos durante la inserci´n o supresi´n, se puede usar el concepto de lista o o

´ 3.2. IMPLEMENTACION

3

ligada (Ver figura) la cual consta de un conjunto de nodos, no necesariamente almacenados en forma adyacente. Cada nodo contiene el elemento y una liga o enlace a su sucesor.
e1 l e2 e3 e4 e5

Figura3.1:

Implementaci´n usando dos clases: la de la lista ligada (Lista)y la de o nodos (Nodo). La clase de los nodos tinen un elemento que es el dato a guardar en la lista, y una referencia al siguiente nodo, que es la liga. Puede resultar curioso que se tenga una referencia a un objeto del tipo que est´ definiendo a pero es v´lido hacer esto. a /* * Clase para manejar los nodos de la lista */class Nodo { Object elemento; Nodo sgte; /** * Crea un nodo con elemento igual a valor y apuntando al vac´o. ı * @param valor el Objeto que es el valor de nodo */ Nodo(Object valor) { elemento = valor; sgte = null; } /** * Crea un nodo despu´s del indicado, con elemento igual a valor. e * @param valor el Objeto que es el valor de nodo * @param n el nodo anterior al reci´n creado e */ Nodo(Objectvalor, Nodo n) { elemento = valor;

´ 3.2. IMPLEMENTACION

4

sgte = n; } /* * Devuelve el valor de un nodo * @return Object el valor del nodo */ public Object daElemento () { return elemento; } /** * Devuelve la referencia del siguiente nodo * @return NOdo el siguietne nodo */ public Nodo daSgte() { return sgte;} } A continuaci´n la implementaci´n de la interfaz, creando la lista ligada o o...