Verkettete Listen clear und size Methode

melesch

Mitglied
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

Code:
	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:
Code:
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
 

TKausL

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

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

melesch

Mitglied
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 :/

Code:
	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:
 
T

Trolllllll

Gast
Vielleicht so?!?
Java:
void print() {
   IntListNode node = this;
   while (node.next != null) {
      System.out.println(node);
      node=node.next;
   }
   System.out.println(node);
}
 

faetzminator

Gesperrter Benutzer
Java:
int size = 1;
IntListNode node = this;
while ((node = node.next) != null) {
    size++;
}
Oder so ähnlich ermittelst du die Grösse.
 

melesch

Mitglied
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 :eek:
 
S

SlaterB

Gast
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

Top Contributor
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

Mitglied
Ok anders gefragt ^^


Das würde warscheinlich funktionieren (an der Stelle 5) :
Code:
 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?
 
S

SlaterB

Gast
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
 
S

SlaterB

Gast
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

Top Contributor
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 :p)
 

melesch

Mitglied
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"

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

SlaterB

Gast
@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

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

IntListNode ist die Klasse in der die Methoden stehen..


Code:
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;
	}
...
 
S

SlaterB

Gast
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

Mitglied
ja das ist wieder bitter :lol:

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

Code:
 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;}
	 }
 

melesch

Mitglied
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?
Code:
 node = node.next;

Danke!
 
S

SlaterB

Gast
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

Mitglied
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.

Code:
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.. :p
 
S

SlaterB

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

Neue Themen


Oben