uoc.ei.tads
Class ListaEncadenada<E>

java.lang.Object
  extended by uoc.ei.tads.ListaEncadenada<E>
All Implemented Interfaces:
java.io.Serializable, Contenedor<E>, Lista<E>
Direct Known Subclasses:
ListaDoblementeEncadenada

public class ListaEncadenada<E>
extends java.lang.Object
implements Lista<E>

Secuencia posicional que se caracteriza por disponer de operaciones basadas en la posición que ocupa un elemento dentro del contenedor.

See Also:
Posicion, Serialized Form

Nested Class Summary
protected static class ListaEncadenada.NodoEncadenado<E>
          Clase que implementa un nodo con un encadenamiento a nodo, que une un nodo con el siguiente en una estructura de datos con encadenamiento simple.
protected static class ListaEncadenada.RecorridoUnidireccionalLista<E>
          Clase que proporciona un recorrido de las posiciones.
 
Field Summary
protected  int n
          Número de elementos que hay actualmente en el contenedor.
protected  ListaEncadenada.NodoEncadenado<E> ultimo
          Posición del último elemento de la lista.
 
Constructor Summary
ListaEncadenada()
          Construye una lista vacía.
 
Method Summary
protected  ListaEncadenada.NodoEncadenado<E> anterior(ListaEncadenada.NodoEncadenado<E> nodo)
          Retorna el nodo anterior al recibido como parámetro.
 E borrar(Posicion<E> nodo)
          Borra la posición recibida.
 E borrarPrimero()
          Borra la primera posición de la lista.
 E borrarSiguiente(Posicion<E> nodo)
          Borra la posición siguiente.
 Iterador<E> elementos()
          Accesor de lectura de los elementos que hay en el contenedor.
 boolean estaVacio()
          Método para comprobar si el contenedor está vacío.
 Posicion<E> insertarAlFinal(E elem)
          Añade un elemento al final de la lista.
 Posicion<E> insertarAlPrincipio(E elem)
          Añade un elemento al principio de la lista.
 Posicion<E> insertarAntesDe(Posicion<E> nodo, E elem)
          Añade un elemento antes de la posición recibida.
 Posicion<E> insertarDespuesDe(Posicion<E> nodo, E elem)
          Añade un elemento después de la posición recibida.
 void intercambiar(Posicion<E> nodo1, Posicion<E> nodo2)
          Intercambia los elementos contenidos a las posiciones recibidas.
protected  ListaEncadenada.NodoEncadenado<E> nuevaPosicion(ListaEncadenada.NodoEncadenado<E> nodo, E elem)
          Crea un nodo encadenado, le sitúa a continuación del recibido como parámetro e incrementa el número de elementos.
 int numElems()
          Accesor de lectura del número de elementos que hay en el contenedor.
 Recorrido<E> posiciones()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
 E reemplazar(Posicion<E> nodo, E elem)
          Reemplaza el elemento contenido en la posición recibida.
 java.lang.String toString()
          Método que sobrescribe Object.toString(). los elementos aparecen separados por el salto de línea de la plataforma.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

n

protected int n
Número de elementos que hay actualmente en el contenedor.


ultimo

protected ListaEncadenada.NodoEncadenado<E> ultimo
Posición del último elemento de la lista. En esta representación circular, la posición siguiente es la primera.

Constructor Detail

ListaEncadenada

public ListaEncadenada()
Construye una lista vacía.

Method Detail

numElems

public int numElems()
Accesor de lectura del número de elementos que hay en el contenedor.

Specified by:
numElems in interface Contenedor<E>
Returns:
número de elementos que contiene actualmente

estaVacio

public boolean estaVacio()
Método para comprobar si el contenedor está vacío.

Specified by:
estaVacio in interface Contenedor<E>
Returns:
cierto o falso, según si está vacío o no lo está

insertarAlPrincipio

public Posicion<E> insertarAlPrincipio(E elem)
Añade un elemento al principio de la lista.

Specified by:
insertarAlPrincipio in interface Lista<E>
Parameters:
elem - elemento que se quiere añadir a la lista
Returns:
nueva posición que contiene el elemento

insertarAlFinal

public Posicion<E> insertarAlFinal(E elem)
Añade un elemento al final de la lista.

Specified by:
insertarAlFinal in interface Lista<E>
Parameters:
elem - elemento que se quiere añadir a la lista
Returns:
nueva posición que contiene el elemento

insertarAntesDe

public Posicion<E> insertarAntesDe(Posicion<E> nodo,
                                   E elem)
Añade un elemento antes de la posición recibida.

Specified by:
insertarAntesDe in interface Lista<E>
Parameters:
elem - elemento que se quiere añadir a la lista
nodo - posición de referencia
Returns:
nueva posición que contiene el elemento
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

insertarDespuesDe

public Posicion<E> insertarDespuesDe(Posicion<E> nodo,
                                     E elem)
Añade un elemento después de la posición recibida.

Specified by:
insertarDespuesDe in interface Lista<E>
Parameters:
elem - elemento que se quiere añadir a la lista
nodo - posición de referencia
Returns:
nueva posición que contiene el elemento
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

borrarPrimero

public E borrarPrimero()
Borra la primera posición de la lista.

Specified by:
borrarPrimero in interface Lista<E>
Returns:
elemento que había en la posición
Throws:
ExcepcionContenedorVacio - si la lista está vacía

borrar

public E borrar(Posicion<E> nodo)
Borra la posición recibida.

Specified by:
borrar in interface Lista<E>
Parameters:
nodo - posición que se quiere eliminar
Returns:
elemento que había en la posición
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

borrarSiguiente

public E borrarSiguiente(Posicion<E> nodo)
Borra la posición siguiente.

Specified by:
borrarSiguiente in interface Lista<E>
Parameters:
nodo - posición anterior a la que se quiere eliminar; si es null se elimina la primera posición
Returns:
elemento que había en la posición siguiente
Throws:
ExcepcionPosicionInvalida - si la posición es no válida

reemplazar

public E reemplazar(Posicion<E> nodo,
                    E elem)
Reemplaza el elemento contenido en la posición recibida.

Specified by:
reemplazar in interface Lista<E>
Parameters:
elem - nuevo elemento
nodo - posición de referencia
Returns:
elemento que había en la posición
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

intercambiar

public void intercambiar(Posicion<E> nodo1,
                         Posicion<E> nodo2)
Intercambia los elementos contenidos a las posiciones recibidas.

Specified by:
intercambiar in interface Lista<E>
Parameters:
nodo1 - primera de las dos posiciones de referencia
nodo2 - segunda de las dos posiciones de referencia
Throws:
ExcepcionPosicionInvalida - si alguna posición es null o no válida

anterior

protected ListaEncadenada.NodoEncadenado<E> anterior(ListaEncadenada.NodoEncadenado<E> nodo)
Retorna el nodo anterior al recibido como parámetro. En esta lista simplemente encadenada la operación tiene un coste temporal lineal: O(n).

Parameters:
nodo - posición de referencia, no null
Returns:
nodo anterior al recibido como parámetro

nuevaPosicion

protected ListaEncadenada.NodoEncadenado<E> nuevaPosicion(ListaEncadenada.NodoEncadenado<E> nodo,
                                                          E elem)
Crea un nodo encadenado, le sitúa a continuación del recibido como parámetro e incrementa el número de elementos. Se puede sobrescribir por las subclases que necesiten trabajar con descendientes de NodoEncadenado.

Parameters:
nodo - posición anterior a la del nuevo nodo; puede ser null
elem - elemento que se quiere añadir a la lista
Returns:
nodo nuevo conteniendo el elemento recibido como parámetro; situado entre el nodo recibido como parámetro y su siguiente

elementos

public Iterador<E> elementos()
Accesor de lectura de los elementos que hay en el contenedor. Retorna una enumeración. Enumerar es simplemente enunciar la una detrás la otra (las cosas de una serie, las partes de un todo). Pero si el contenedor tiene definido algún tipo de ordenación o de recorrido, la enumeración debe ser consecuente y ofrecer los elementos por orden (FIFO, LIFO, inordre, etc.), sin alterar el estado actual del contenedor. Si durante el recorrido se altera la estructura de posiciones del contenedor, los resultados son imprevisibles.

Specified by:
elementos in interface Contenedor<E>
Returns:
enumeración de los elementos del contenedor
Throws:
ExcepcionPosicionInvalida - si se quiere obtener el siguiente elemento de la enumeración y éste no existe.
See Also:
Iterador.haySiguiente(), Iterador.siguiente()

posiciones

public Recorrido<E> posiciones()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Specified by:
posiciones in interface Lista<E>
Returns:
enumeración de las posiciones del contenedor

toString

public java.lang.String toString()
Método que sobrescribe Object.toString(). los elementos aparecen separados por el salto de línea de la plataforma.

Overrides:
toString in class java.lang.Object