Sortiertes Einfügen in doppelt verkettete Liste

[Zel2491]

Moin moin

Ich habe meine doppelt verkettete Liste und möchte dort über die Konsole Zahlen eingeben und diese DIREKT sortiert in die Liste einfügen.

Bisher sieht meine Methode so aus:

void insertSorted(DLink newDLink, int iNumber) {

    if(this.suc != null){ //1.
        this.suc.pre = newDLink;
    }

    newDLink.suc = this.suc;//2.
    newDLink.pre = this; //3.
    this.suc = newDLink; //4.
}

bisher werden die eingegebenen Zahlen einfach nur hinten angehängt^^

Jemand einen Vorschlag, wie ich das angehe?

Gruß Zel 😉

 

[Fant]

Da wirst du wohl solange deine Liste durchlaufen müssen, bis du an der passenden Stelle angekommen bist, und dann deinen neuen Knoten dort einhängen. Was ist unklar?

 

[flopalko]

Die Elemente sollten von Anfang an mit der insertSorted()-Methode eingefügt werden. Dadurch wird das Problem trivial.
Du musst einfach den Anfang deiner Liste nehmen, die Sortierbedingung prüfen, falls nötig zum nächsten Element gehen, allerdings vorher prüfen, ob vorhanden. Falls größer und Ende der Liste erreicht, fügst du es hinter dem letzten Element an, ansonsten fügst du es dann eben an der richtigen Position an.
Den Code dafür wird dir hier sicherlich niemand schreiben, wenn du aber einen Code hast, der dann nicht funktioniert kannst du den posten und dir wird sicher geholfen 😉

 

[Zel2491]

Jooo^^ Code wollt ich auch nicht haben 😛

Ich probier das gleich mal zu implementieren und dann poste ich hier nochmal Code 😛

 

[Zel2491]

Ich tu mich ehrlich gesagt gerad ziemlich schwer mit dem Durchlaufen der Liste...

Ich hab derzeit nicht so richtig den Durchblick, wie ich diese Art von Liste durchlaufe und dabei jedes einzelne Element überprüfe... -.-''

 

[flopalko]

Ich denke schon, dass du das auch selbst hinbekommen hättest, aber hier mal ein Vorschlag (auf Grund mangelnder Information der Klasse DLink habe ich raten müssen, dass suc der nachfolgende Knoten ist (besserer Name wäre next), und welchen Namen dein Attribut, das verglichen werden soll hat, hast du auch verschwiegen, also hier allgemein):

void insertSorted(DLink newDLink) {
	DLink temp = this;
	while(temp.suc != null){
		if(temp.deinZuVergleichendesAttribut > newDLink.deinZuVergleichendesAttribut){
			//füge deinen newDLink hier ein!
			return;
		}
		if(temp.suc.deinZuVergleichendesAttribut > newDLink.deinZuVergleichendesAttribut){
			//füge deinen newDLink nach temp.suc ein!
			return;
		}
		temp = temp.suc;
	}
    //falls die while-Schleife durchläuft ist das Element am Schluss einzufügen, da sonst ein return ausgeführt werden würde --> füge deinen newDLink am Schluss ein!
	return;
}

[EDIT]Den Parameter int iNumber habe ich nun auch entfernt, da der absolut nutzlos ist. Vielleicht irre ich auch, aber dann hättest du zumindest darlegen müssen, wozu der gut sein soll![/EDIT]