Java Listen

23.04.2015, 10:01

Batista

Java Listen

import java.util.*;

/** Verkettete Liste fuer Daten vom Typ INHALT */
public class Liste<INHALT> implements Iterable<INHALT> {
/** Kopf der Liste */
Knoten<INHALT> kopf;

/** Konstruktor fuer eine leere Liste */
public Liste() {
kopf = null; // Leer
};

/** Laenge der Liste berechnen */
public int size() {
int antwort = 0;
Knoten<INHALT> aktuell = kopf;
while(aktuell != null) {
aktuell = aktuell.naechstes;
antwort += 1;
}
return antwort;
}

/** Element am Anfang einfuegen */
public void prepend(INHALT daten) {
kopf = new Knoten<INHALT>(daten, kopf);
}

/** Element am Ende einfuegen */
public void append(INHALT daten) {
// Sonderfall: leere Liste
if (kopf == null) {
kopf = new Knoten<INHALT>(daten, kopf);
return;
}
Knoten<INHALT> ende = kopf;
// Das Ende hat kein naechstes Element:
while(ende.naechstes != null) {
ende = ende.naechstes;
}
ende.naechstes = new Knoten<INHALT>(daten, null);
}

/** Klasse, die ein Element der Liste speichert */
protected static class Knoten<INHALT> {
/** Gespeichterte Daten */
protected INHALT daten;

/** Naechstes Element */
protected Knoten<INHALT> naechstes;

/** Konstruktor fuer Knoten */
public Knoten(INHALT daten, Knoten<INHALT> naechstes) {
this.daten = daten;
this.naechstes = naechstes;
}
}

/** Einen Iterator fuer die Liste erzeugen */
public Iterator<INHALT> iterator() {
return new Iter<INHALT>(kopf);
}

/** Implementierung eines Iterators */
protected static class Iter<INHALT> implements Iterator<INHALT> {
/** Aktuelle position */
Knoten<INHALT> position;

/** Konstruktur */
public Iter(Knoten<INHALT> position) {
this.position = position;
}

/** Zum naechsten Element gehen */
public INHALT next() {
INHALT ret = position.daten;
position = position.naechstes;
return ret;
}

/** Test, ob die Liste ein naechstes Element hat */
public boolean hasNext() {
return position != null;
}

/** Entfernen nicht erlaubt. */
public void remove() {
throw new UnsupportedOperationException();
}
}

/** Methode zum Testen der Implementierung */
public static void main(String[] args) {
Liste<Integer> liste = new Liste<Integer>();
liste.prepend(2);
liste.prepend(1);
liste.append(3);
liste.append(4);
liste.prepend(0);
System.out.println("Ist die Laenge 5? "+liste.size());
System.out.println("Die naechstes Zeile sollte dies sein: '0 1 2 3 4'!");
for (Integer i : liste) {
System.out.print(i+" ");
}
System.out.println();
System.out.println("Die naechste Zeile sollte leer sein, aber keinen Fehler verursachen!");
for (Integer i : new Liste<Integer>()) {
System.out.print(i+" ");
}
System.out.println();
}
}

2-4

public INHALT get(int pos){
Liste<INHALT> jetzt = super.kopf;
if(pos == 0){
return jetzt.next();
} else {
while (k>0) {
jetzt = jetzt.naechtes;
k--;
}
jetzt.next();

}
2-3 habe ich keine Vorstellungen, wie ich sie lösen kann.
Wo bitte soll da "prepand" Methode sein?

23.04.2015, 13:11

Auf diesen Beitrag antworten »

as_string

Ich kann im Moment nicht den ganzen Quelltext durch schauen, deshalb nur kurz allgemein zu verketteten Listen:

Normalerweise hast Du eine Referenz auf das erste Element und dann von jedem Element wieder eine Referenz auf das nächste. Wenn Du am Ende etwas einfügen musst, musst Du zuerst auch das Ende finden. Dazu musst Du beim ersten anfangen (Du hast sonst ja erst gar keine andere Referenz) und dann von Element zu Element gehen, bis Du das letzte in der Liste gefunden hast. Dann erst kannst Du das neue Element hinten anhängen.
Am Anfang der Liste einfügen geht da viel schneller: Du kannst einfach ein neues Element generieren, dessen Referenz auf das bisherige erste Element zeigen lassen und den "Listenzeiger", also die Referenz auf das erste Element auf Dein neu generiertes zeigen lassen, weil das je jetzt das neue erste ist. Du brauchst dafür nicht über die ganze Liste zu laufen.

Verbesserung wäre, wenn Du Dir nicht nur eine Referenz auf das erste sondern auch auf das letzte Element merken würdest. Kannst Du Dir denken, wie das hilft?

Gruß
Marco

23.04.2015, 18:53

Auf diesen Beitrag antworten »

Batista

Zitat:

Original von as_string

Verbesserung wäre, wenn Du Dir nicht nur eine Referenz auf das erste sondern auch auf das letzte Element merken würdest. Kannst Du Dir denken, wie das hilft?

Gruß
Marco

/** Verkettete Liste fuer Daten vom Typ INHALT */
public class Liste<INHALT> implements Iterable<INHALT> {
/** Kopf der Liste */
Knoten<INHALT> kopf;
/** Ende der Liste */
Knoten<INHALT> ende;
** Konstruktor fuer eine leere Liste */
public Liste() {
kopf = null; // Leer
};

Jetzt muss man nicht die ganze Liste durchlaufen, sondern hat gleich die Referenz auf den Letzten Eintrag und so kann man entsprechend schneller am Ende der Liste einfügen.

Zur laufzeit:
Für einfügen am Anfang der Liste, habe ich nur ein Operation demnach 1
O(1) oder??

Beim einfügen am Ende der Liste vor der Verbesserung muss ich n Elemente der Liste durchgehen, bis das Ende erreicht ist und dann entsprechend einfügen

demnach O(n)

Nach der Verbesserung ist gilt O(1) für beide Fälle?

23.04.2015, 19:35

Auf diesen Beitrag antworten »

Batista

public Integer min() {
Knoten<Integer> jetzt= super.kopf;
Integer min = jetzt.getnext;

while(jetzt != null) {
Integer x= jetzt.getnext();
If( min.compareto(x)>0) {
min = x;
}
}
}

Weiterhin wird gefragt, wieso Integer benutzt wurde?

Weil man die Werte miteinander vergleichen wollte und Integer werte lassen sich eben vergleichen.

23.04.2015, 19:53

Auf diesen Beitrag antworten »

Batista

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

 public Integer min() {
    Knoten<Integer> jetzt= super.kopf;
Integer min = jetzt.daten;

while(jetzt != null) {
Integer x= jetzt.daten;
if( min.compareTo(x)>0) {
min = x;
}
}
return min;
}

Der Complier tut nichts nach

javac IntergerListe.java
java IntergerListe

verwirrt

23.04.2015, 20:28

Auf diesen Beitrag antworten »

Batista

Erster Code stark verbessert

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

 public INHALT get(int pos) {
       Knoten<INHALT> jetzt = super.kopf;
 INHALT x = jetzt.daten;
if(pos == 0){
return x;
} else {
while (pos>0) {
jetzt= jetzt.naechstes;
x=jetzt.daten;
pos--;
}
}
return x;

26.04.2015, 12:37

Auf diesen Beitrag antworten »

as_string

Zitat:

Original von Batista
/** Verkettete Liste fuer Daten vom Typ INHALT */
public class Liste<INHALT> implements Iterable<INHALT> {
/** Kopf der Liste */
Knoten<INHALT> kopf;
/** Ende der Liste */
Knoten<INHALT> ende;
** Konstruktor fuer eine leere Liste */
public Liste() {
kopf = null; // Leer
};

Die Quelltexte habe ich mir nicht weiter angeschaut. Erstens kann das ein Compiler viel besser und zweitens ist mir das auch zu mühsam so ganz ohne Formatierung und so! Wenn Du Quelltexte angibst achte deshalb bitte darauf, dass Du den "CODE-Einfügen" Knopf oder entsprechende Tags verwendest. Und dann eben auch die Einrückung richtig machst. Das hast Du ja bei Deinen letzten Postings auch schon teilweise gemacht.

Zitat:

Original von Batista
Jetzt muss man nicht die ganze Liste durchlaufen, sondern hat gleich die Referenz auf den Letzten Eintrag und so kann man entsprechend schneller am Ende der Liste einfügen.

Zur laufzeit:
Für einfügen am Anfang der Liste, habe ich nur ein Operation demnach 1
O(1) oder??

Beim einfügen am Ende der Liste vor der Verbesserung muss ich n Elemente der Liste durchgehen, bis das Ende erreicht ist und dann entsprechend einfügen

demnach O(n)

Nach der Verbesserung ist gilt O(1) für beide Fälle?

Ja, das ist alles so weit richtig.

Gruß
Marco

26.04.2015, 12:57

Auf diesen Beitrag antworten »

as_string

Zitat:

Original von Batista
Erster Code stark verbessert

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

 public INHALT get(int pos) {
       Knoten<INHALT> jetzt = super.kopf;
 INHALT x = jetzt.daten;
if(pos == 0){
return x;
} else {
while (pos>0) {
jetzt= jetzt.naechstes;
x=jetzt.daten;
pos--;
}
}
return x;

Bitte Code einrücken, ist ja sonst unlesbar!
Am Ende fehlt eine Klammer.
Du kannst Dir das "if(pos==0)" sparen: Wenn pos wirklich 0 ist, dann geht er ja in die while-Schleife gar nicht rein, weil die als Bedingung ja "pos>0" hat. Nach der while-Schleife machst Du dann ja auch in jedem Fall ein return x;
Also das "if" und das "else" einfach weg lassen und nur die while-Schleife.

In der while-Schleife belegst Du immer wieder x neu, brauchst es dort aber gar nicht. Das kannst Du Dir sparen und brauchst es nur einmal nach der while-Schleife zu machen, bevor Du das x zurück gibst.
Du brauchst auch das x ganz am Anfang nicht bestimmen!
Ganz am Ende fehlt noch eine schließende geschweifte Klammer.

Dann wäre Dein Code schon deutlich kürzer:

code:
1: 2: 3: 4: 5: 6: 7: 8:	public INHALT get(int pos) { Knoten<INHALT> jetzt = super.kopf; while (pos > 0) { jetzt = jetzt.naechstes; pos--; } return jetzt.daten; }

Was aber noch fehlt: Falls die Liste zu wenige Elemente enthält, um überhaupt an "pos" springen zu können, dann würde "jetzt.naechstes" in der while-Schleife irgendwann NULL werden und Du würdest eine NULL-Pointer-Exception bekommen wenn das nächste Mal auf "jetzt.naechstes" zugegriffen wird oder auf jetzt.daten ganz am Ende.
Ich würde also auf jeden Fall noch eine Überprüfung auf NULL einbauen und dann lieber eine OutOfBoundsException werfen.

Gruß
Marco

Neue Frage »

Antworten »

Java Listen

Verwandte Themen