Methoden Verkettete Listen Index eines Elementes ausgeben

[vaults]

Moin Leute,

ich bin grade dabei einige Methoden für eine verkettete Liste zu schreiben, zwei fehlen noch und bei diesen komme ich nicht weiter.

Ich implementiere bei meiner Klasse LinkedList das Interface List.
Die Struktur ist so, das jedes Objet aus zwei Teilen besteht, einmal das Itemfeld

private Object item;

mit dem eigentlichen Inhalt, sowie ein Zeigerfeld

private LinkedList next;

welcher auf dieses verweist. Das erste Zeigerfeld ist null.

Ich kann nun nach belieben Objekte hinzufügen, an bestimmte Positionen schreiben, löschen, hinten anhängen usw, zb. mit:

LinkedList l1 = new LinkedList();
l1.insert("FF");
l1.insert(4.7);
l1.insert(567);
l1.insert("moin");

und erhalte dann mit der toString:

--> 4.7 --> loblibuh --> FF --> jo was geht --> 15 --> moin --> 4a --> moin --> 567 --> 4.7 --> FF |--

diese Ausgabe. (hatte noch mehr drinne)

Grundsätzlich laufen alle Methode rekursiv ab, von vorne beginnend wird geprüft und ggf. mittels

return next.methode()

das ganze erneut für das folgende Element aufgerufen.

Ich soll jetzt zwei Methoden schreiben, die mir jeweils den ersten Index, sowie den letzten Index des übergebenen Elementes ermitteln.

int firstIndexOf(Object x);
int lastIndexOf(Object x);

Da die Funktionen rekursiv für jedes Element der Liste laufen, kann ich keine lokalen Variablen anlegen, globale ergeben auch keinen Sinn, da diese dann das Ergebnis bei mehrmaligem Aufruf der Funktion verfälschen würden.

Mittels length() kann ich die Länge der verbleibenden Liste abfragen, diese ändert sich dann natürlich mit jedem Aufruf, da ich jeweils ein Element weitergehe.

Mir ist nicht klar, wie ich dies realisieren soll, hier ein Ansatz der aber nichts vernünftiges liefert.

public int firstIndexOf(Object x){
		
			if (isEmpty()){
				return -1;
			}
			
			else{
				while (!(next.getItem().equals(x))){
					return next.firstIndexOf(x);			
			}
			System.out.println(length());
			return this.length();
		}
	}

Vielleicht hat sich ja jemand auf dieses Gebiet spezialisiert und kann mir helfen.

Über Tipps würde ich mich sehr freuen.

LG,
Alex

 

[SlaterB]

du kannst Parameter an den nächsten Aufruf übergeben, oder mit dem Rückgabewert arbeiten, was du halb schon versuchst

z.B. könnte bei firstIndexOf() die Methode bei Fund 1 zurückgeben, der vorherige rekursive Aufrufer schaut sich den Rückgabewert an,
wenn 0 dann bei 0 belassen, nix gefunden, wenn > 0, dann um 1 erhöhen, so kommt ganz am Anfang 5 zurück, wenn es 5 war,
mit length() zu arbeiten hilft natürlich auch irgendwann irgendwie, wie arbeitet die Methode eigentlich?

 

[faetzminator]

SlaterB, meinst du nicht eher, wenn gefunden [c]0[/c] zurück, und bei [c]-1[/c] in Ruhe lassen?

 

[vaults]

Moin,

das klingt sehr vielversprechend, werde es heute Nacht mal ausprobieren und mich dann wieder melden.

Danke schonmal und noch ein schönes WE.

LG,
Alex

 

[Fant]

Bloß keine Rekursion! (oder sollst du das so machen?)

Stell dir mal vor, was dann passiert, wenn du 100.000 Einträge in deiner Liste hast, oder mehr...

Du musst doch einfach nur linear deine Liste durchsuchen und dabei hochzählen. Wenn du dein gesuchtes Element findest, dann gibst du den aktuellen Zählerstand aus, wenn nicht, dann einfach -1.

 

[vaults]

Ich sehen keinen anderen Weg als bei einer verketteten Liste das ganze rekursiv durchzugehen und bei jeder Rekursion den Zeiger auf das Folgeelement zu legen.

Globale Variablen machen meiner Meinung nach keinen Sinn.
Ich kann diese benutzen wenn ich die Methode nur ein einziges mal aufrufe, da sonst bei erneutem Aufruf der Startwert der globalen Variable anders ist.

Auch kann ich diese in der Funktion weder vor dem Return zurück auf 0 setzen, noch zu Beginn der Methode, da sonst bei jeder Rekursion der Wert ebenfalls wieder auf 0 zurückgesetzt würde.

 

[vaults]

Moin,

so habe den Ansatz von SlaterB genommen und habe nun eine "eigentlich" funktionstüchtige Funktion, die zum Großteil den korrekten Wert ausgibt:

// Liefert ersten Index des übergebenen Elementes												//Verbleibend
	public int firstIndexOf(Object x){
		
		while (!isEmpty()){
			if (this.item == x){
				System.out.println(this.item == x);
				System.out.println(this.item.equals(x));
				break;
			}
			else {
				return 1+next.firstIndexOf(x);
			}
		}
		return 0;
	}

Der Aufruf:

System.out.println(l1.firstIndexOf("jo was geht"));

liefert das korrekte Ergebnis:

 --> 4.7 --> loblibuh --> FF --> jo was geht --> 15 --> moin --> 4a --> moin --> 567 --> 4.7 --> FF |--
true
true
4

Die Werte "loblibuh", sowie 4.7 und 567 liefert komischerweise einen Fehler.
loblibuh ist vom Typ Element und kann somit nicht einfach mit "==" abgefragt werden, 4.7 ist das erste Element, vielleicht hackts da, 567 sollte er aber eingentlich machen, denn auch bei 15 liefert er das korrekte Ergebnis.

Das eigentlich komische an der Sache ist allerdings, dass wenn ich die Abfrage auf :

if (this.item.equals(x)){         // oder (this.getItem().equals(x)

umstelle, bekomme ich bei jedem Aufruf einen Fehler? Das verstehe ich nicht, vielleicht kann mir hier jemand helfen.

LG,
Alex

 

[vaults]

Die Funktion funktioniert jetzt für alle Objekte, außer für Objekte der Klasse Elemente.
Die implementiert allerdings comparable, weiß also nicht woran das liegt.

// Liefert ersten Index des übergebenen Elementes												//Verbleibend
	public int firstIndexOf(Object x){
		if (this.equals(null)){
			return next.firstIndexOf(x);
		}
		while (!isEmpty()){
			if (next.getItem().equals(x)){
				return 1;
			}
			else {
				return 1+next.firstIndexOf(x);
			}
		}
		return 0;
	}

 

[SlaterB]

equals null ist immer Quatsch, wenn dann ==,
und das eigene Objekt, this, kann nicht null sein,

wenn du eine Schleife garantiert im ersten Durchlauf beendest, dann ist es keine Schleife, schreibe if statt while

auf den Nachfolger ungeprüft 1 zu addieren berücksichtigt nicht, dass ein Objekt nicht gefunden wird/ nicht vorhanden ist,
den Fall musst du auch testen, was soll dann zurückgegeben werden?

wie gesagt wurde besser mit Index 0 als validen Index anfangen, nicht 1

----

um zu wissen was mit Elemente los ist braucht es mehr Code, z.B. die Information ob du genau ein vorhandenes Objekt suchst
oder eins mit gleichen Inhalt,
zu vermuten ist, dass equals() nicht passend überschrieben ist

 

[Fant]

Ich sehen keinen anderen Weg als bei einer verketteten Liste das ganze rekursiv durchzugehen und bei jeder Rekursion den Zeiger auf das Folgeelement zu legen.

Wie man es macht hab ich dir doch gerade schon skizziert. Hier rekursiv zu arbeiten bricht dir wirklich viel schneller das Genick, als du gucken kannst...


Schau dir doch zum Vergleich einfach mal die entsprechenden Methoden aus java.util.LinkedList an. Die sollte man mit wenig Aufwand an deine Implementierung anpassen können.

  580       // Search Operations
  581   
  582       /**
  583        * Returns the index of the first occurrence of the specified element
  584        * in this list, or -1 if this list does not contain the element.
  585        * More formally, returns the lowest index {@code i} such that
  586        * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
  587        * or -1 if there is no such index.
  588        *
  589        * @param o element to search for
  590        * @return the index of the first occurrence of the specified element in
  591        *         this list, or -1 if this list does not contain the element
  592        */
  593       public int indexOf(Object o) {
  594           int index = 0;
  595           if (o == null) {
  596               for (Node<E> x = first; x != null; x = x.next) {
  597                   if (x.item == null)
  598                       return index;
  599                   index++;
  600               }
  601           } else {
  602               for (Node<E> x = first; x != null; x = x.next) {
  603                   if (o.equals(x.item))
  604                       return index;
  605                   index++;
  606               }
  607           }
  608           return -1;
  609       }
  610   
  611       /**
  612        * Returns the index of the last occurrence of the specified element
  613        * in this list, or -1 if this list does not contain the element.
  614        * More formally, returns the highest index {@code i} such that
  615        * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
  616        * or -1 if there is no such index.
  617        *
  618        * @param o element to search for
  619        * @return the index of the last occurrence of the specified element in
  620        *         this list, or -1 if this list does not contain the element
  621        */
  622       public int lastIndexOf(Object o) {
  623           int index = size;
  624           if (o == null) {
  625               for (Node<E> x = last; x != null; x = x.prev) {
  626                   index--;
  627                   if (x.item == null)
  628                       return index;
  629               }
  630           } else {
  631               for (Node<E> x = last; x != null; x = x.prev) {
  632                   index--;
  633                   if (o.equals(x.item))
  634                       return index;
  635               }
  636           }
  637           return -1;
  638       }

 

[vaults]

Moin,

danke, die Methode wurde erstmal so angepasst, dass er prüft ob das Element vorhanden ist, auch die Abfrage ob this == null ist, wurde gelöscht, er prüft dies bereits in der "isEmpty()" Funktion.

In diesem Fall ist das erste Objekt null, es markiert den Anfang der Liste.

// Liefert ersten Index des übergebenen Elementes												//Verbleibend         FAST FERTIG
	public int firstIndexOf(Object x){
		if (!isInList(x)) return -1;
		while (!isEmpty()){
			if (next.getItem().equals(x)){
				return 1;
			}
			else {
				return 1+next.firstIndexOf(x);
			}
		}
		return 0;
	}

LG,
Alex