Listas dobles

Clase 25

Listas enlazadas

Colección de clases de Java
• El paquete java.util contiene implementaciones de muchas de las estructuras de datos que vamos a tratar y que implementaremos de forma más sencilla en clase. • Puede utilizar las implementaciones estándar de Java en los boletines de problemas. Están más elaboradas y son más abstractas que las implementaciones de clase. • Al aprendera implementar varias estructuras de datos, profundizará en el modo en que utiliza todas las estructuras.
2

1

Listas como un tipo de datos abstracto
Una lista es un conjunto de elementos con un orden concreto:
– Puede tener una longitud arbitraria. – Ofrece la posibilidad de insertar o eliminar un elemento en cualquier ubicación. – Ofrece la posibilidad de recorrer la lista de formaordenada, de elemento en elemento.

3

Una interfaz List
public interface List { public public public public public public boolean isEmpty(); void addFirst( Object o ); void addLast( Object o ); boolean contains(Object o); boolean remove(Object o); Object removeFirst()

throws NoSuchElementException; public void clear(); public int size(); }
4

2

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 conla eliminación. • Por ello, las listas suelen utilizar una implementación enlazada. 5

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 elelemento 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.

6

3

Diagrama de lista enlazada sencilla

Lista
primero último

Enlace 1

Enlace 2

...

Enlace n

null

Elem 1

Elem 2

Elem n

7

Listas enlazadas sencillas, 2
• El objetode 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 o “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. • Así, el enlacerealmente 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.
8

4

Demostración de una lista enlazada sencilla
List: SLinkedList: SLinkedListApp: SLinkedListView: Interfaz de lista Implementación de lista Aplicación main() GUI de lista

9

La clase interna de enlacepublic class SLinkedList implements List { private static class SLink { Object item; SLink next; SLink( Object o, SLink n ) { item = o; next = n; } SLink( Object o ) { this( o, null ); } } . . .
10

5

Listas genéricas y tipadas
• • La interfaz List que hemos especificado es general, como la clase Vector de Java: almacena y recuperar objetos. Si crea su propia clase de tipo lista y sa be, porejemplo, que sólo trabajar á concadenas, puede sustituir lo s campo s Object por cam pos String. P or ejemp lo:

private static class SLink { String item; SLink next; SLink( String o, SLink n ) { item = o; next = n; } SLink( Object o ) { this( o, null ); } } public void addFirst( String o );
11

Miembros de datos de SLinkedList
• Sólo es necesario first (primero). • last (último) y length...