Introduzione alle strutture dati - Dipartimento di Informaticapaolo/FP/materiale/LucidiListe.pdf ·...

Tratti da ©2002 Apogeo srlHorstmann-Concetti di informatica e fondamenti di Java 2 1

Capitolo 17 Introduzione alle strutture dati

Liste

Introduzione alle strutture dati



Una lista concatenata di stringhe



public class LList{

/** Metodi per manipolare le liste */

/** Una lista e’ un riferimento ad un oggetto dellaclasse Link */

private Link first;

/** La classe Link definisce gli elementi della lista */private class Link{

Object data;Link next;

}



/** Costruisce una lista concatenata vuota.

*/public LList(){

first = null;}

LinkedList

nullfirst



Aggiunta di un elemento in testa a una lista concatenata



/**Aggiunge un elemento in testa alla lista concatenata.@param obj l’oggetto da aggiungere

*/public void addFirst(Object obj){

Link newLink = new Link();newLink.data = obj;newLink.next = first;first = newLink;

}



Eliminazione del primo elemento di una lista concatenata



/**Toglie il primo elemento dalla lista concatenata.@return l’elemento eliminato

*/

public Object removeFirst(){

if (first == null) return null;

else {Object obj = first.data;first = first.next;return obj;

}}


Capitolo 17 Introduzione alle strutture dati/**

Restituisce il primo elemento della lista concatenata.@return il primo elemento della lista concatenata

*/

public Object getFirst()

{if (first == null)

return null;

else

return first.data;

}



��

Bob

null

temp

Aggiungere un elemento in fondo a una lista concatenata



/**Aggiunge un elemento in fondo alla lista concatenata.@param obj l’oggetto da aggiungere

*/public void add(Object obj) {

Link newLink = new Link();newLink.data = obj;newLink.next = null;

if (first == null)first = newLink;

else {Link temp = first;while(temp.next != null)

temp = temp.next;temp.next = newLink;}

}



Togliere un elemento da una lista concatenata

positionprevious



/**Toglie la prima occorrenza di un elemento dallalista concatenata@param l’oggetto da eliminare @return true se almeno un elemento è stato eliminatodalla lista concatenata.

*/

public boolean remove (Object obj)

{

boolean found = false;

Link position = first;

Link previous = null;



while ((!found) && (position != null)){

if ((position.data).equals(obj))found = true;

else{

previous = position;position = position.next;

}}

if (found) if (position == first)

first = first.next;else

previous.next = position.next;

return found;}



/**Controlla la presenza di un oggetto nellalista concatenata@param l’oggetto da controllare@return true se almeno un’occorrenza dell’elemento è trovata

*/public boolean contains(Object obj){

boolean found = false;Link l = first;while ((!found) && (l != null)

if ((l.data).equals(obj)) found = true;

elsel = l.next;

return found;}

}



Aggiungere un elemento nella parte centraledi una lista concatenata



Visione concreta di una lista concatenata


Capitolo 17 Introduzione alle strutture datiFile LListTest.java

/**Programma che illustra il funzionamento della classe LList

*/public class LListTest {

public static void main(String[] args) {LList staff = new LList();

staff.add("Dick");staff.add("Harry");staff.addFirst("Romeo");

// Romeo � Dick � Harry

staff.add("Juliet")staff.add("Nina"); // R � D � H � J � Nstaff.remove("Dick"); // R � H � J � N

staff.toPrint();



if (staff.contains("Romeo"))System.out.println("Qua Romeo c'e'");

elseSystem.out.println("Qua Romeo non c'e'");

staff.removeFirst(); // H � J � N

staff.toPrint();

if (staff.contains("Romeo"))System.out.println("Qua Romeo c'e'");

elseSystem.out.println("Qua Romeo non c'e'");

System.out.println("Il primo e' " + staff.getFirst());

staff.clear();

staff.toPrint();

System.out.println("...mentre ora e' tutto vuoto"); }

}



Riepilogo File LList.java

/**Una lista concatenata è una sequenza di elementi dotata di meccanismi di inserimento ed eliminazione.Questa classe ha un sottoinsieme dei metodi della classe standard java.util.LList

*/public class LList{

/** Costruisce una lista concatenata vuota.

*/public LList(){

first = null;}



public Object removeFirst(){

if (first == null) return null;

else {Object obj = first.data;first = first.next;return obj;

}}/**

Aggiunge un elemento in testa alla lista concatenata.@param obj l’oggetto da aggiungere

*/public void addFirst(Object obj){

Link newLink = new Link();newLink.data = obj;newLink.next = first;first = newLink;

}



/**Aggiunge un elemento in fondo alla lista concatenata.@param obj l’oggetto da aggiungere

*/public void add(Object obj) {

Link newLink = new Link();newLink.data = obj;newLink.next = null;

if (first == null)first = newLink;

else {Link l = first;while(l.next != null)

l = l.next;l.next = newLink;}

}



private Link first;

private class Link{

Object data;Link next;

}

/**Svuota la lista concatenata.

*/public void clear ( ){

first = null;}



/**Controlla la presenza di un oggetto nellalista concatenata@param l’oggetto da controllare@return true se almeno un’occorrenza dell’elemento è trovata

*/public boolean contains(Object obj){

boolean found;Link l = list;while ((!found) && (l != null)

if ((l.data).equals(obj)) found = true;

elsel = l.next;

return found;}

}

25


/**

Toglie la prima occorrenza di un oggetto dalla

lista concatenata

@param l’oggetto da eliminare

@return true se almeno un elemento è stato eliminato

dalla lista concatenata.

*/

public boolean remove(Object obj)

{

boolean found = false;

Link position = first;

Link previous = null;

©2002 Apogeo



while ((!found) && (position != null)){

if ((position.data).equals(obj))found = true;

else{

previous = position;position = position.next;

}}

if (found) if (position == first)

first = first.next;else

previous.next = position.next;

return found;}

}

Introduzione alle strutture dati - Dipartimento di Informaticapaolo/FP/materiale/LucidiListe.pdf ·...

Documents

Transcript of Introduzione alle strutture dati - Dipartimento di Informaticapaolo/FP/materiale/LucidiListe.pdf ·...