[Java][LinkedList]

[moka]

devo fare un esercizio in preparazione di un esame universitario, ma non riesco a uscirne fuori :cry: qualcuno saprebbe aiutarmi? :oink:
la cosa da cui proprio non riesco a cavarmi fuori è come fare a puntare ciclicamente all' elemento next, dovendo passare per head :muro: è una cosa difficile da spiegare copio l'esercizio faccio prima :D

questa è la classe:

public class ListLinked {
private Node head;

private class Node {
private String content;
private Node next;

public Node(String c, Node n) {
content = c;
next = n;
}

public Node(String c) { this(c, null); }
}

public ListLinked() {
head = null;
}

public boolean isEmpty() { return head == null; }

public void addToStart(String s) {
Node newNode = new Node(s, head);
head = newNode;
}

public static ListLinked cons(String c, ListLinked l) {
ListLinked result = new ListLinked();
result.addToStart(c);
if (l != null) result.head.next = l.head;
return result;
}

public String first() { return isEmpty() ? null : head.content; }

public ListLinked rest() {
if (isEmpty()) {
return null;
}
else {
ListLinked result = new ListLinked();
result.head = head.next;
return result;
}
}

public ListLinked concatenate(ListLinked l) {
if (isEmpty()) {
return l;
}
else {
return cons(first(), rest().concatenate(l));
}
}

public int printLength = 5;
public int setPrintLength(int pl) { return printLength = pl; }
public int getPrintLength() { return printLength; }

public String toString() {
String result;

if (isEmpty()) {
return "()";
}
else {
int i;
Node n;

result = "(" + head.content;
for (n = head.next, i = 1;
n != null || (printLength > 0 && i > printLength);
n = n.next, i++) {
result += " " + n.content;
}

if (printLength > 0 && i > printLength) result += "...";
result += ")";
return result;
}
}



public static void main(String[] args) {
ListLinked l = cons("A", cons("B", cons("C", null)));

System.out.println(l);
}
}

questi i metodi da implementare:

public ListLinked reverse(); // Inverte una lista
public ListLinked remove(String s); // Crea una nuova lista con 's' rimosso.
public ListLinked oddList(); // Crea una nuova lista con solo gli elementi in posizione dispari.
public ListLinked evenList(); // Crea una nuova lista con solo gli elementi in posizione pari.
public int length(); // Riscrivere *senza* usare cicli; potete fare un overload.

mi basta che me ne venga risolto / spiegato uno fra questi, poi dopo per gli altri ci penso io :D grazie per la pazienza :oink:

[moka]

in particolare il mio problema sta nel poter richiamare ciclicamente l'attributo next che è un oggetto della classe stessta, la quale è un attributo della altra classe.

tanto per farmi capire, a parole è difficile:
(mi scuso per la qualità delle immagini )
http://img413.imageshack.us/img413/7817/javaqx5.th.jpg (http://img413.imageshack.us/my.php?image=javaqx5.jpg)

dunque, mettiamo caso che io devo trovare il nodo che nell'attributo di tipo stringa val ha valore "ciao", e poi stampare a video il contenuto del nodo successivo(next), come posso fare?

[moka]

public ListLinked reverse(); // Inverte una lista


public ListLinked reverse(){
ListLinked k=new ListLinked();
Node n=new Node(null, head);
Vector<Node>v=new Vector<Node>(1);
if(head==null){
System.out.println("la lista è vuota!");
}else{
while(n.next!=null){
v.add(n.next);
v.setSize(v.size()+1);
n=n.next;
}
Node[]q=new Node[v.size()];
for(int i=0;i<v.size();i++){
q[i]=v.get(v.size()-i-1);
}
for(int i=0;i<v.size();i++){
q[i].next=q[i+1];
}
k.head=q[0];
}
return k;

}


mi da errore sul finale

[Oceans11]

dunque, mettiamo caso che io devo trovare il nodo che nell'attributo di tipo stringa val ha valore "ciao", e poi stampare a video il contenuto del nodo successivo(next), come posso fare?

devi scandire la lista fino a che non trovi il nodo in questione...


Node aux = head;
while(aux != null && !aux.val.equals("ciao") {
aux = aux.next;
}
if(aux != null && aux.next != null) {
System.out.println(aux.val);
}


il ciclo while dice: avanzo nella lista fino a che non sto puntando ad un elemento Node nullo oppure l'elemento attuale ha il campo val uguale a "ciao".
Terminato il while ho 2 possibilità:
1) ho scorso tutta la lista e quindi non ho trovato nessun elemento il cui campo val è "ciao" (quindi aux = null)
2) ho trovato l'elemento il cui campo val è "ciao" e quindi aux punta a quello.

in questo secondo caso allora devo controllare se l'elemento successivo ad aux è null, in caso contrario stampo il suo val.

NB: tutti i controlli rispetto a null si devono fare altrimenti viene lanciata una NullPointerExceptio a runtime.

NMB: non ci metto la mano sul fuoco....tra l'altro sono senza compilatore e non posso provare.

[moka]

devi scandire la lista fino a che non trovi il nodo in questione...


Node aux = head;
while(aux != null && !aux.val.equals("ciao") {
aux = aux.next;
}
if(aux != null && aux.next != null) {
System.out.println(aux.val);
}


il ciclo while dice: avanzo nella lista fino a che non sto puntando ad un elemento Node nullo oppure l'elemento attuale ha il campo val uguale a "ciao".
Terminato il while ho 2 possibilità:
1) ho scorso tutta la lista e quindi non ho trovato nessun elemento il cui campo val è "ciao" (quindi aux = null)
2) ho trovato l'elemento il cui campo val è "ciao" e quindi aux punta a quello.

in questo secondo caso allora devo controllare se l'elemento successivo ad aux è null, in caso contrario stampo il suo val.

NB: tutti i controlli rispetto a null si devono fare altrimenti viene lanciata una NullPointerExceptio a runtime.

NMB: non ci metto la mano sul fuoco....tra l'altro sono senza compilatore e non posso provare.

non ti preoccupare, è tutto giusto quello che dici!
MA questo esercizio l'avevo da poco capito anche io...
ho dubbi sul reverse, per esempio, ma secondo te se riesco a farlo con i Vector, funziona la cosa? è giusta?

[moka]

che mi dite di iterator?

[Oceans11]

:stordita: mi deve essere sfuggita qualche cosa allora....!:D


cmq per il reverse stavo pensando a semplici inserimenti e rimozioni. Mi spiego meglio.

Non è necessario l'utilizzo di una struttura dati ausiliaria. Si può benissimo prendere il elemento della prima lista, rimuoverlo dalla prima ed inserirlo in testa ad una seconda (etc...), che è poi quella che devi restituire, no?

[Lukas17]

Se ti serve ancora questo è il metodo Reverse funzionante:


public ListLinked reverse(){ // inverte una lista
Node curr = head;
if(curr == null) throw new NoSuchElementException();
if(curr.next == null) {return null;}
Node temp = null;
while (curr != null) {
Node next = curr.next;
curr.next = temp;
temp = curr;
curr = next;
}
head = temp;
return null;
}