uoc.ei.tads
Class LlistaEncadenada<E>

java.lang.Object
  extended by uoc.ei.tads.LlistaEncadenada<E>
All Implemented Interfaces:
java.io.Serializable, Contenidor<E>, Llista<E>
Direct Known Subclasses:
LlistaDoblementEncadenada

public class LlistaEncadenada<E>
extends java.lang.Object
implements Llista<E>

Seqüència posicional que es caracteritza per disposar d'operacions basades en la posició que ocupa un element dins del contenidor.

Since:
1.5
See Also:
Posicio, Serialized Form

Nested Class Summary
protected static class LlistaEncadenada.NodeEncadenat<E>
          Classe que implementa un node amb un encadenament a node, que uneix un node amb el següent en una estructura de dades amb encadenament simple.
protected static class LlistaEncadenada.RecorregutUnidireccionalLLista<E>
          Classe que proporciona un recorregut de les posicions.
 
Field Summary
protected  LlistaEncadenada.NodeEncadenat<E> darrer
          Posició del darrer element de la llista.
protected  int n
          Nombre d'elements que hi ha actualment al contenidor.
 
Constructor Summary
LlistaEncadenada()
          Construeix una llista buida.
 
Method Summary
 Posicio<E> afegirAbansDe(Posicio<E> node, E elem)
          Afegeix un element abans de la posició rebuda.
 Posicio<E> afegirAlFinal(E elem)
          Afegeix un element al final de la llista.
 Posicio<E> afegirAlPrincipi(E elem)
          Afegeix un element al principi de la llista.
 Posicio<E> afegirDespresDe(Posicio<E> node, E elem)
          Afegeix un element després de la posició rebuda.
protected  LlistaEncadenada.NodeEncadenat<E> anterior(LlistaEncadenada.NodeEncadenat<E> node)
          Retorna el node anterior al rebut com a paràmetre.
 Iterador<E> elements()
          Accessor de lectura dels elements que hi ha al contenidor.
 E esborrar(Posicio<E> node)
          Esborra la posició rebuda.
 E esborrarPrimer()
          Esborra la primera posició de la llista.
 E esborrarSeguent(Posicio<E> node)
          Esborra la posició següent.
 boolean estaBuit()
          Mètode per a comprovar si el contenidor està buit.
 void intercanviar(Posicio<E> node1, Posicio<E> node2)
          Intercanvia els elements continguts a les posicions rebudes.
 int nombreElems()
          Accessor de lectura del nombre d'elements que hi ha al contenidor.
protected  LlistaEncadenada.NodeEncadenat<E> novaPosicio(LlistaEncadenada.NodeEncadenat<E> node, E elem)
          Crea un node encadenat, el situa a continuació del rebut com a paràmetre i incrementa el nombre d'elements.
 Recorregut<E> posicions()
          Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.
 E reemplacar(Posicio<E> node, E elem)
          Reemplaça l'element contingut a la posició rebuda.
 java.lang.String toString()
          Mètode que sobreescriu Object.toString().
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

n

protected int n
Nombre d'elements que hi ha actualment al contenidor.


darrer

protected LlistaEncadenada.NodeEncadenat<E> darrer
Posició del darrer element de la llista. En aquesta representació circular, la posició següent és la primera.

Constructor Detail

LlistaEncadenada

public LlistaEncadenada()
Construeix una llista buida.

Method Detail

nombreElems

public int nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor.

Specified by:
nombreElems in interface Contenidor<E>
Returns:
nombre d'elements que conté actualment

estaBuit

public boolean estaBuit()
Mètode per a comprovar si el contenidor està buit.

Specified by:
estaBuit in interface Contenidor<E>
Returns:
cert o fals, segons si està buit o no ho està

afegirAlPrincipi

public Posicio<E> afegirAlPrincipi(E elem)
Afegeix un element al principi de la llista.

Specified by:
afegirAlPrincipi in interface Llista<E>
Parameters:
elem - element que es vol afegir a la llista
Returns:
nova posició que conté l'element

afegirAlFinal

public Posicio<E> afegirAlFinal(E elem)
Afegeix un element al final de la llista.

Specified by:
afegirAlFinal in interface Llista<E>
Parameters:
elem - element que es vol afegir a la llista
Returns:
nova posició que conté l'element

afegirAbansDe

public Posicio<E> afegirAbansDe(Posicio<E> node,
                                E elem)
Afegeix un element abans de la posició rebuda.

Specified by:
afegirAbansDe in interface Llista<E>
Parameters:
elem - element que es vol afegir a la llista
node - posició de referència
Returns:
nova posició que conté l'element
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

afegirDespresDe

public Posicio<E> afegirDespresDe(Posicio<E> node,
                                  E elem)
Afegeix un element després de la posició rebuda.

Specified by:
afegirDespresDe in interface Llista<E>
Parameters:
elem - element que es vol afegir a la llista
node - posició de referència
Returns:
nova posició que conté l'element
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

esborrarPrimer

public E esborrarPrimer()
Esborra la primera posició de la llista.

Specified by:
esborrarPrimer in interface Llista<E>
Returns:
element que hi havia a la posició
Throws:
ExcepcioContenidorBuit - si la llista està buida

esborrar

public E esborrar(Posicio<E> node)
Esborra la posició rebuda.

Specified by:
esborrar in interface Llista<E>
Parameters:
node - posició que es vol eliminar
Returns:
element que hi havia a la posició
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

esborrarSeguent

public E esborrarSeguent(Posicio<E> node)
Esborra la posició següent.

Specified by:
esborrarSeguent in interface Llista<E>
Parameters:
node - posició anterior a la que es vol eliminar; si és null s'elimina la primera posició
Returns:
element que hi havia a la posició següent
Throws:
ExcepcioPosicioInvalida - si la posició és no vàlida

reemplacar

public E reemplacar(Posicio<E> node,
                    E elem)
Reemplaça l'element contingut a la posició rebuda.

Specified by:
reemplacar in interface Llista<E>
Parameters:
elem - nou element
node - posició de referència
Returns:
element que hi havia a la posició
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

intercanviar

public void intercanviar(Posicio<E> node1,
                         Posicio<E> node2)
Intercanvia els elements continguts a les posicions rebudes.

Specified by:
intercanviar in interface Llista<E>
Parameters:
node1 - primera de les dues posicions de referència
node2 - segona de les dues posicions de referència
Throws:
ExcepcioPosicioInvalida - si alguna posició és null o no vàlida

anterior

protected LlistaEncadenada.NodeEncadenat<E> anterior(LlistaEncadenada.NodeEncadenat<E> node)
Retorna el node anterior al rebut com a paràmetre. En aquesta llista simplement encadenada l'operació té un cost temporal lineal: O(n).

Parameters:
node - posició de referència, no null
Returns:
node anterior al rebut com a paràmetre

novaPosicio

protected LlistaEncadenada.NodeEncadenat<E> novaPosicio(LlistaEncadenada.NodeEncadenat<E> node,
                                                        E elem)
Crea un node encadenat, el situa a continuació del rebut com a paràmetre i incrementa el nombre d'elements. Es pot sobreescriure per les subclasses que necessitin treballar amb descendents de NodeEncadenat.

Parameters:
node - posició anterior a la del nou node; pot ser null
elem - element que es vol afegir a la llista
Returns:
node nou contenint l'element rebut com a paràmetre; situat entre el node rebut com a paràmetre i el seu següent

elements

public Iterador<E> elements()
Accessor de lectura dels elements que hi ha al contenidor. Retorna una enumeració. Es pot obtenir un llistat amb un parell de línies de codi:
 for ( Iterador it = tad.elements(); it.hiHaSeguent(); )
    System.out.println(it.seguent()); 
Enumerar és simplement enunciar l'una darrere l'altra (les coses d'una sèrie, les parts d'un tot). Però si el contenidor té definit algun tipus d'ordenació o de recorregut, l'enumeració ha de ser conseqüent i oferir els elements per ordre (FIFO, LIFO, inordre, etc.), sense alterar l'estat actual del contenidor. Si durant el recorregut s'altera l'estructura de posicions del contenidor, els resultats són imprevisibles.

Specified by:
elements in interface Contenidor<E>
Returns:
enumeració dels elements del contenidor
Throws:
ExcepcioPosicioInvalida - si es vol obtenir el següent element de l'enumeració i no n'hi ha cap o no n'hi ha cap més
See Also:
Iterador.hiHaSeguent(), Iterador.seguent()

posicions

public Recorregut<E> posicions()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Specified by:
posicions in interface Llista<E>
Returns:
enumeració de les posicions del contenidor

toString

public java.lang.String toString()
Mètode que sobreescriu Object.toString(). Treu els elements separats pel salt de línia de la plataforma.

Overrides:
toString in class java.lang.Object
Returns:
llistat dels elements