Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Okt 2007

Java - egen länkad lista

Jag håller på att göra en egen länkad listaklass, och ja, det är en skoluppgift. Men jag vill bara ha hjälp med att förstå varför det här inte fungerar.
Det är helt enkelt så att varje objekt i listan länkar till nästa. För att ta bort ett objekt ur listan då så borde man ju helt enkelt bara göra så att objektet innan länkar ännu ett steg bort.

temp.next = temp.next.next;

Men det fungerar inte, får bara upp "Exception in thread 'main' java.lang.NullPointerException". Jag har kollat så att både temp.next och temp.next.next fungerar var för sig, och t.ex. den här raden fungerar fint.

if(temp.next.next == null){temp.next = null;}

Så det går alltså att ta bort det sista värdet i listan, och även det första. Men det vill helt enkelt inte fungera för värdena emellan.
Här är hela funktionen om ni behöver se.

public void remove(Person o){ Node temp = header; if(header.element.compareTo(o) == 0){ header = header.next; } else while(temp.element != null){ if(temp.next.element.compareTo(o) == 0){ if(temp.next.next == null){temp.next = null;} else{temp.next = temp.next.next;} } temp = temp.next; } }

Trädvy Permalänk
Medlem
Plats
Umeå
Registrerad
Feb 2004

... else while(temp.element != null){ ...

Vad du egentligen vill göra där är nog att kolla om temp.next är null.

Dessutom skiljer det sig åt vad som händer om första elementet är det sökta jämfört med om det inte är det. I första fallet tas det funna elementet (header) bort, och inget mer görs. I det andra fallet tas alla matchande objekt bort. Du borde bestämma dig för en av dem.

I övrigt kan följande kod göras simplare:

if(temp.next.next == null){temp.next = null;} else{temp.next = temp.next.next;}

Du kollar om temp.next.next är null, och sätter i så fall även temp.next till null. Annars sätter du temp.next till värdet av temp.next.next. Dessa två alternativ är dock ekvivalenta; i båda fallen sätts temp.next till det värde temp.next.next har, och de två fallen behöver därför inte skiljas åt. Det räcker alltså med:

if(temp.next.element.compareTo(o) == 0){ temp.next = temp.next.next; }

En till fråga: Tillåter din listtyp att användaren sätter in null-referenser? I så fall kan det vara en bra idé att kolla om null innan element.compareTo anropas.

Sedan kan jag ju även nämna att kodstilen inte är helt konsekvent. Mer konsekvent vore något ilknande det nedan.

public void remove(Person o) { Node temp = header; if(header.element.compareTo(o) == 0) { header = header.next; } else { while(temp.element != null) { if(temp.next.element.compareTo(o) == 0) { if(temp.next.next == null) { temp.next = null; } else { temp.next = temp.next.next; } } temp = temp.next; } } }

Edit: Ändrade mitt kodstycke om inkonsekvent kodstil lite.
Edit 2; Lade till ett stycke om olika beteenden.

Vill du ha svar? Citera mig gärna.

Trädvy Permalänk
Medlem
Registrerad
Nov 2005

Först: sen när lades "else while" till i java??

Andra: om nu temp.next.next är null, måste du då verkligen ha specialfall för att sätta temp.next?

Kolla vad som händer när du tagit bort ett objekt, där kan det hända en hel del mystiska saker... Ett tips är att läsa det här.

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Okt 2007

Tackar för all hjälpen, nu fungerar det utmärkt
Ang. else while så var det något som råkade halka in när jag ersatte en if-sats med en while-loop

Så här blev det till slut:

public void remove(Person o){ Node temp = header; //Ändra bara headern om det är det första värdet if(header.element.compareTo(o) == 0){ header = header.next; } else{ while(temp.next != null){ if(temp.next.element.compareTo(o) == 0){ temp.next = temp.next.next; //Peka om så att det oönskade värdet försvinner ur listan break; } temp = temp.next; } } }

Jag vet att objekten fortfarande ligger kvar i minnet och tar plats, men det är inget som behöver tas hänsyn till.

Trädvy Permalänk
Medlem
Plats
Umeå
Registrerad
Feb 2004
Citat:

Ursprungligen inskrivet av Apro
Jag vet att objekten fortfarande ligger kvar i minnet och tar plats, men det är inget som behöver tas hänsyn till.

Jag vet inte vad du vet, men av din formulering fick jag intrycket att du inte känner till detta; men det är faktiskt så Java fungerar. När man är klar med ett objekt tar man bara bort alla referenser till det (på ett passande sätt). Den faktiska avallokeringen sker av en garbage collector vid något senare tillfälle.

Vill du ha svar? Citera mig gärna.

Trädvy Permalänk
Medlem
Registrerad
Nov 2005
Citat:

Ursprungligen inskrivet av lajnold
Jag vet inte vad du vet, men av din formulering fick jag intrycket att du inte känner till detta; men det är faktiskt så Java fungerar. När man är klar med ett objekt tar man bara bort alla referenser till det (på ett passande sätt). Den faktiska avallokeringen sker av en garbage collector vid något senare tillfälle.

"vid något senare tillfälle" == när sista raden i remove har exekverats.

Mer generellt: garbage collector rensar upp i slutet av varje metod. Så om det då finns något objekt på stacken (där allt ligger sparat i minnet) som det inte refereras till, så tas det objektet bort.

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Mar 2008
Citat:

Ursprungligen inskrivet av kd35a
"vid något senare tillfälle" == när sista raden i remove har exekverats.

Mer generellt: garbage collector rensar upp i slutet av varje metod. Så om det då finns något objekt på stacken (där allt ligger sparat i minnet) som det inte refereras till, så tas det objektet bort.

Nej, inte nödvändigtvis. Javas GC är inte deterministisk, det går inte att veta säkert när ett objekt tas bort ur minnet. Du blandar ihop det med hur RAII fungerar i C++. Dessutom tror jag inte man kan allokera objekt på stacken alls, inte explicit iaf (VM:en kanske gör det som någon skum optimering i särskilda fall), också till skillnad från i C++.

Du kan ha rätt vad gäller lokala primitiva variabler, men med objekt så är det som sagt inte alls säkert att minnet för dem samlas upp när de går "out of scope", även om de har blivit "orphaned".

Trädvy Permalänk
Medlem
Registrerad
Nov 2005
Citat:

Ursprungligen inskrivet av badboll
Nej, inte nödvändigtvis. Javas GC är inte deterministisk, det går inte att veta säkert när ett objekt tas bort ur minnet. Du blandar ihop det med hur RAII fungerar i C++. Dessutom tror jag inte man kan allokera objekt på stacken alls, inte explicit iaf (VM:en kanske gör det som någon skum optimering i särskilda fall), också till skillnad från i C++.

Du kan ha rätt vad gäller lokala primitiva variabler, men med objekt så är det som sagt inte alls säkert att minnet för dem samlas upp när de går "out of scope", även om de har blivit "orphaned".

Ahh, ok, det var mer än vad jag visste. Har alltid förstått det som att GC rensar i slutet i metoder, men icke. Då har man lärt sig nått nytt, tack!

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Okt 2007

Okej, jag visste inte att java gjorde det automatiskt, tänkte mer att det var ett så litet program så det inte spelade någon större roll om det låg kvar eller inte. Man lär sig något varje dag