einfach verkettete Liste -> Elemente vertauschen

[chrizz_h]

Hi miteinander...
habe in muehevoller Arbeit eine einfach verkettete Liste implementiert (beliebte Hausaufgabe).
Was mich jedoch schon seit Stunden wurmt, ist, wie man Listenelemente von Typ Comparable,
bzw. beliebigen Typs, miteinander vertauscht. (z.B. um einen Sortieralgorithmus zu implementieren).
Scheint in Gegensatz zu nem Array nicht ganz so leicht mit XOR zu realisieren.
Mein Ansatz ist wohl auch eher schlecht als recht, reicht aber sicherlich aus, um mich zu maßregeln...

public void swapPosition(int index1, int index2){
		Node temp;
		Node swapElem1 = head; //head ist der anfang der liste
		Node swapElem2 = head;
		for(int i= 1;i<index1-1;i++){ 
			if(index1 == 1){
				swapElem1= head; break;
			}
			swapElem1 = swapElem1.next;
		}
		for(int j = 1;j<index2-1;j++){
			if(index2 == 1){
				swapElem2 = head; break;
			}
			swapElem2 = swapElem2.next;
		}
		temp = swapElem2.next; //schaetze hier und im folgenden liegt der fehler
		swapElem2.next = temp.next;
		temp.next = swapElem1.next;
		swapElem1.next = temp;
	}

Achja, eventuelle Abruchbedingungen hab ich bislang auch außen vor gelassen!
Waere schon, wenn mir da ein geschultes Auge weiterhelfen koennte.
Habt Dank...
chrizz

 

[Anmeldeboykottierer]

Hi,
hm, sieht wirklich stark nach typ. Hausaufgaben aus. Insbesondere kommt hier das typische "Hausaufgaben werden in (fast) keinem Forum beantwortet". Das heißt natürlich nur, dass du keine geschenkte Lösung bekommst (die dir auch wirklich nichts bringen würde, z.B. wenn es eine Klausur gibt).

Damit dir jmd. helfen kann, musst du immer viel Information geben (steigert die Wahrscheinlichkeit, dass dir jmd. so hilft, dass du weiter kommst). In deinem Fall wäre es also schön, wenn du erklären kannst, wie dein Code entstanden ist. Geh mal die einzelnen Codestücke durch und erkläre etwas genauer, warum du was machst.
Nebenbei bemerkt, mich würde sogar interessieren, wie man in einem Array mit XOR vertauschen kann.

Schreib einfach erstmal die Idee deines Algorithmus in Worten (ganz ohne Java) auf. Und danach sagst du mal, was davon sich an welcher Stelle wiederfindet.
Vielleicht solltest du auch drüber nachdenken, die for-Schleifen durch eine andere Struktur zu ersetzen. Ein break ist zwar natürlich erlaubt und erfüllt seinen Zweck, aber eine while-Schleife ist da einfach leichter zu lesen (man kann bei dir das break leicht übersehen, wenn es nicht gerade blau in der Zeile steht).
Wenn du die Schleife umwandelst, kannst du dir auch leichter überlegen, wie lange du wirklich weiterlaufen musst, wirklich bis index1 den Wert 1 hat?

Gruß Der Unwissende

 

[leifg]

ich kann dir grad mal sagen wie ich vorgehe:

am besten ist, man zeichnet bevor man so einen algorithmus entwickelt eine kleine skizze (typisch: lauter kästchen die jeweils auf das nächste kästchen zeigen)

das problem bei einfach verketteten listen ist, dass keinen zugriff auf das vorherige element hat

blöderweise muss man die next referenz des vorherigen elements auf das getauschte element biegen

also erstmal nach dem vorderen element suchen und die next referenzen umbiegen

danach dann die next referenz des eigentlichen elements auf das richtige element setzen

abbruchbedingungen die man einbauen sollte sind:

- weniger als 2 elemente in liste
- angegebener index überschreitet die länge der liste

ich habe selbst auch diese tauschalgorithmus im studium durchgenommen. damals haben wir aber der tausch methode keine integer übergeben, sonder wir haben einfach mit 2 nodes gearbeitet.

hat den vorteil, dass die suchschleifen dann viel einfacher werden

tauschen(Node Node1, Node Node2)
{
 Node counter = head;
 while (counter.next != Node1)
 {
   counter = counter.next;
  }
...
}

findet das element vor Node1 (while (counter != Node1) findet Node1)

hoffe das hilft dir weiter