Verkettete Listen clear und size Methode

[melesch]

Hallo,

wir nehmen gerade die verketteten Listen durch und haben einige Aufgaben bekommen.

Das Löschen eines bestimmten Elementes habe ich so gelöst:


IntListNode

	IntListNode remove (int e) {
		if (elem == e) {
			return next;
		}
		IntListNode node = this;
		while (node.next != null) {
			if (node.next.elem == e) {
				node.next = node.next.next;
				return this;
			}
			node = node.next;
		}
		return this;
	}

IntList:

public void remove(int elem) {          
		if (head != null) {                
			head = head.remove(elem);
		}
	}

doch wie lösche ich eine gesamte Liste? Wie müsste hier die Schleife bzw die Rekursion aussehen?

Mein zweites Problem wäre ein Algorithmus wie ich die Länge einer solchen Liste ausgebe?

Würde mich über ein paar Denkanstöße freuen

lg

 

[faetzminator]

doch wie lösche ich eine gesamte Liste? Wie müsste hier die Schleife bzw die Rekursion aussehen?

Ich würd einfach den ersten Node rauslöschen.

Mein zweites Problem wäre ein Algorithmus wie ich die Länge einer solchen Liste ausgebe?

Entweder iterativ oder rekursiv durch alle Elemente und jeweils einen Index um eins hochzählen.

 

[TKausL]

Zum Löschen einfach erstes und letztes Element (sind ja beide hinterlegt) auf "null" setzen.

Zum zählen drüberiterieren und mitzählen ^^

 

[melesch]

Danke das löschen funktioniert

Nur wie gehe ich einfach einmal durch die Kette durch?

Habe das in der print() Methode zwar gemacht rekursiv gemacht, nur funktioniert das dann mit der Laufvariabel nicht :/

	void print() {
		System.out.println(elem);
		if (next != null) {
			next.print();
		}
	}

Kann mir hier wer einen iterativen Durchlauf zeigen? So würd ich es sicher einfacher verstehen :rtfm:

 

[Trolllllll]

Vielleicht so?!?

void print() {
   IntListNode node = this;
   while (node.next != null) {
      System.out.println(node);
      node=node.next;
   }
   System.out.println(node);
}

 

[faetzminator]

int size = 1;
IntListNode node = this;
while ((node = node.next) != null) {
    size++;
}

Oder so ähnlich ermittelst du die Grösse.

 

[melesch]

danke hat mir super geholfen!

 

[melesch]

Sry für den Doppelpost aber ich wollte hier kein Extra Thread aufmachen.

Wie kann ich auf einen bestimmten Index der Liste zugreifen?

Ich habe ja die Länge der Liste jedoch funktionieren meine Versuche so ganz und gar nicht

 

[SlaterB]

du hast eine Methode bekommen, die die Liste durchgeht, beim 1. Element eine size-Variable auf 1 erhöht, beim 5. Element 5, beim 76. Element auf 76, beim 7854874. Element auf 7854874

aber du kannst von da ausgehend keinerlei Idee entwickeln auf das 76. Element zu kommen?
echt nicht?

 

[Crian]

Das ist der Nachteil an solchen Listen, du musst dann schon n mal weiter gehen, wenn du zum Index n möchtest (und der erste den Index 0 hat).

 

[melesch]

Ok anders gefragt ^^


Das würde warscheinlich funktionieren (an der Stelle 5) :

 void get(){
		 
 IntListNode node = this;
		 for (int i = 0; i<=5; i++){
			
			 node = node.next;
			
		 }
	
	 }

Doch bräuchte ich es in der Form int get(int index)..

Bei meinen Versuchen würde ich immer node = node.next bis zu einer gewissen Zahl laufen lassen. Nur wie soll ich den return Wert bestimmen?

 

[SlaterB]

wo besteht da ein Problem?
> return node;
nach der Schleife oder was immer vom node zurückzugeben ist

natürlich besser noch alles sicherer bauen, etwa Index > Länge der Liste testen

 

[TKausL]

natürlich besser noch alles sicherer bauen, etwa Index > Länge der Liste testen

und fals Index > länge/2 dann von hinten iterieren.

 

[SlaterB]

aber nur wenn die Länge in einem Attribut irgendwo gecacht steht, was der vorherigen Methode dazu bisschen entgegensteht,
nicht wenn erst die Liste per Durchlauf bestimmt wird

 

[TKausL]

aber nur wenn die Länge in einem Attribut irgendwo gecacht steht, was der vorherigen Methode dazu bisschen entgegensteht,
nicht wenn erst die Liste per Durchlauf bestimmt wird

Wenn die Länge nicht gespeichert ist ist es aber auch sinnfrei erstmal durchzuzählen nur um die länge rauszubekommen um dann nachher nochmal zu iterieren. Da kann man auch während dem durchzählen gucken ob man an Position X angekommen ist: return das element, ob man am ende der liste ist: return null, oder ob keins von beiden zutrifft, continue; (bzw. garnichts mehr, schleife geht einfach weiter )

 

[melesch]

wo besteht da ein Problem?
> return node;
nach der Schleife oder was immer vom node zurückzugeben ist

Aber genau das ist mein Problem.. Ich kann in einer int methode das node nicht zurückgeben.

Eclipse Zitat "Type missmatch. Cannot convert from int to IntListNode"

 int get(int index){
		 IntListNode node = this;
		 for (int i = 0; i<=index; i++){
			 node = node.next;
			
		 }
		 return node;
	
	 }

 

[TKausL]

Cannot convert from int to IntListNode

Das kann ich mir nicht vorstellen.
Beim return sollte eigentlich eher das hier kommen:

Cannot convert from IntListNode to int

Poste mal bitte die genaue Zeile wo der Fehler auftritt.

 

[SlaterB]

@TKausL
> Wenn die Länge nicht gespeichert ist ist es aber auch sinnfrei erstmal durchzuzählen nur um die länge rauszubekommen um dann nachher nochmal zu iterieren.

habe ich denn entsprechendes behauptet? maximal sich von der anderen Methode zu einer Idee leiten zu lassen,
das aktuelle sieht doch gut aus, Länge taucht da nicht direkt auf,

einen hohen Index für Fehler-Test zu verwenden impliziert auch nicht, dass die Methode die Länge berechnen muss,
passiert dann nebenbei wie du ja auch sagst

@melesch
was ist denn ein IntListNode?
klingt ganz danach als hätte er einen int in sich gespeichert,
also
> return node.rueckDeinenIntRaus();
?

das ist ja nun wirklich eine bedenkliche Frage...

 

[melesch]

Sry natürlich steht "Cannot convert from IntListNode to int"!

IntListNode ist die Klasse in der die Methoden stehen..

class IntListNode {

	private int elem;          // das eigentliche Listenelement
	private IntListNode next;  // naechster Knoten in der Liste
	
	IntListNode(int e, IntListNode n) {
		elem = e;
		next = n;
	}
...

 

[SlaterB]

und es kommt dir nicht in den Sinn, den int 'elem' des Nodes zurückzugeben?
ob du es als Code hinbekommst ist eine Sache, so wenig schwer es auch sein sollte,
aber allein die Überlegung 'ich muss wohl den int aus dem Node zurückgeben' ist schon fern jeder Vorstellung?

 

[melesch]

ja das ist wieder bitter :lol:

Naja wurde jetzt gelöst, aber ist sicher nicht das schönste..

 int get(int index){
		 IntListNode node = this;
		 if (index == 0) { return node.elem;}
		 else { int size = 0;
		 while ((node = node.next) != null) {
			    size++;
			    if (size == index) break;
			}
		 return node.elem;}
	 }

 

[TKausL]

Bei einer Listenlänge von 5 würde er bei get(6) einfach das letzte Element zurück geben. Ist das so gewollt?

 

[melesch]

danke hat jetzt alles funktioniert!

Habe nur mehr ein Denkproblem und zwar wie lösche ich das erste Element??

Mit diesem Code wird ja nur weitergegangen?

 node = node.next;

Danke!

 

[SlaterB]

du hast doch im ersten Posting schon eine Lösch-Methode, die anscheinend auch das erste Element löscht wenn dessen Wert der Parameter ist,
wieder mal die Standardfrage: überhaupt keine Ideen, irgendwas davon ausgehend selber zu machen außer eine Forum-Frage zu stellen?

so böse das klingt, aber wenn du nichts dabei lernst:
langsam kannst du dir wohl auch sparen, die Aufgaben zu bearbeiten, welchen Zweck sollte das haben?
ich selber spare mir schon die Arbeit bzw. allein das 'Verbrechen', deine Aufgabensteller zu betrügen

 

[melesch]

Na gut aber hier wird das auf eine andere Weise geändert.. das funktioniert hier leider nicht da ich hier nicht auf das erste Element komme.

void removeAll(int elem){
		  IntListNode node = this;
		
		  while (node.next != null) {
				if (node.next.elem == elem) {
					node.next = node.next.next;
				}
				node = node.next;
			}
	  }

natürlich habe ich Ideen nur ist mir gestern und heut nichts passendes eingefallen.. kommen leider immer nur Fehler. Außerdem war das die dritte Frage bei 14 Beispielen..

 

[SlaterB]

ein Objekt kann sich offensichtlich nicht selber entfernen,
das geht nur von außen, mit head, ganz wie im ersten Posting