Einfügeoption einer linearen Liste

freakC++

Hallo zusammen,

ich möchte in Java eine lineare Liste implementieren. Dabei hat jedes Element der Liste eine Referenz auf das nachfolgende Element und einen eigenen Wert. Bis jetzt funktioniert alles auch prima, außer die Methode, die ein Element an einer bestimmten Position einfügt. Ich bekomme immer eine NullPointer - Exception, aber sehe keinen Weg, sie zu umgehen. Hier ist der Code

public boolean insertAtPosition (T key, int pos) {		
	ListItem<T> q = new ListItem<T>(key, null); //neues einzufügendes Element
	ListItem<T> p = first; //erstes Element der Liste

	if(pos == 0) { //Element wird am Anfang eingefügt
		q.next = first;
		first = q;
		length++; //Listenlänge um eins erhöhen
		return true;
	}
		if(pos > length) //false zurückgeben, wenn an ungültige Position eingefügt werden soll
		return false;

	int counter = 0;
	length++;

	while(true){ //bis zu der einzufügenden Stelle gehen
		if(counter == pos) {	//Stelle gefunden	
			q.next = p.next; //NullPointerException
			p.next = q;
			);

			return true;
		}

		counter++;
		p = p.next;
	}
}

Die Zeile "q.next = p.next" erzeugt die Exception. Ich vermute mal, dass es daher kommt, dass ich an das Ende der Liste ein Element einfügen möchte. Somit ist "p.next" null. Aber das hat schon seine Richtigkeit, weil eben kein weiteres Objekt folgt :D.

Könnt ihr mir helfen, meinen Code zum Laufen zu bringen?

Vielen Dank
LG, freakC++

freakC++

Durch ein bisschen Debugging hab ich den Fehler gefunden. In der Schleife muss die if-Bedingung natürlich "if(counter == pos-1)" heißen. Das ist aber irgendwie nicht so schön...

Angenommen ich habe die Liste 0 1 2 3 4 5 6 7 8 9 und ich möchte an die vierte Stelle 99 einfügen, dann sieht das Ergebnis so aus:

0 1 2 3 4 99 5 6 7 8 9.

Es wird also an die fünfte Stelle eingefügt. Das liegt daran, dass wir eben bei 0 anfangen zu zählen. Meine Frage ist nun, ob das immer so ist? Ich dachte, dass bei Enfügeoptionen man meist von 1 anfängt zu zählen und hier das Ergebnis also

0 1 2 3 99 4 5 6 7 8 9

lauten sollte. Wie ist der Standard?
Vielen Dank

LG, freakC++

knivil

lineare Liste

Nur so fuer mein Verstaendnis: Was ist eine nicht-lineare Liste?

freakC++

z.B. ein Baum.

Fängt man hier auch normwalerweise bei 0 an zu zählen?

Vielen Dank

freakC++

Da man auch bei ArrayList, Vector, HashMap etc. bei 0 anfängt zu zählen, gehe ich von der Richtigkeit meines Codes aus

LG, freakC++

@freakC++: Eigentlich wird es meistens andersrum gesehen, d.h. eine Liste ist ein spezieller ("linearer") Baum, nicht umgekehrt.

freakC++

ohh...ok! Das wusste ich nicht. Da habe ich es wohl andersherum gerlernt