Java Linked List

[KalleWirsch]

Hi,

also eigentlich will ich mit bubbleSort eine verlinkte Liste sortieren! Gut die Laufzeit ist zwar schlecht aber ich wüsste jetzt keinen Suchalgorithmus der schneller ist und Listen sortiert!!

...
Ich habe ein Problem wenn ich bei der doppelt verketteten Liste zwei Elemente vertauschen will.
Irgendwie klappt es nicht, wenn ich das Element 2 ausgehängt habe dieses dann vor das Element 1 zu hängen.
Wie ich El.1 mit El.3 verbinde weiß ich ... es funktioniert auch!!

Hier hab ich meine Methoden

public Datum GetPrevious()
	    {
	    	return previous;
	    }
	    
	    auf p
	    public void SetPrevious(Datum p)
	    {
	    	previous = p;
	    }
	        
	    
	    public Datum GetNext()
	    {
	    	return next;
	    }
	    
	   
	    public void SetNext(Datum n)
	    {
	    	next = n;
	    }

so hänge ich das Element aus:

  Datum d = GetFirst();
  Datum next = d.GetNext();
  d.SetNext(next.GetNext());
  next.GetNext().SetPrevious(d);

hiermit versuche ich dann das Element ganz vorne anzuhängen

  d.SetPrevious(next);
  next.SetNext(d);

aber wenn ich mir später die Liste in einer Schleife ausgeben lasse zeigt er mir das Element nicht mehr an!!1


weiß vielleicht jemand was ich da machen könnt???

mfG
Alpee

 

[Beni]

Merkst du dir auch, dass du einen neuen Start für die Liste hast?

 

[Leroy42]

d = GetFirst(); ==> d ist ein Element
next = d.GetNext(); ==> next ist das Folgeelement von d
d.SetNext(next.GetNext()); ==> d's Folgeelement wird auf next's Folgeelement gesetzt
next.GetNext().SetPrevious(d); ==> Das Vorgängerelement des Nachfolgers von next wird auf d gesetzt.

:autsch:


Edit: (Bis dahin scheint es ja doch in Ordnung zu sein)

Beschreib erstmal welche Elemente vertauscht werden sollen :shock:
- d und sein Nachfolger?
- d und sein Vorgänger?
- ...

Dann können wir dir helfen

 

[KalleWirsch]

es soll eiegntlich d mit seinem Nachfolger vertauscht werden!!!

Meine Idee ist:
das Nachfolgeelement von d auszuhängen
d an das übernächste Element zu hängen
und dann das ehemalige Nachfolgelement von d (dass ausgehängt wurde) vorne, vor d zu hängen!

 

[KalleWirsch]

oh sorry ... ich merk grad, vielleicht ist meien Überschrift falsch!!!
Sie sollte wohl besser doppelt verkettete Liste heißen!!

 

[Leroy42]

n = d.next

n.next.prev = d
d.prev.next = n
n.prev = d.prev
n.next = d
d.next = n.next
d.prev = n;

 

[KalleWirsch]

also in meien Methoden umgeformt, müsste das doch so aussehen:

	    	Datum n = d.GetNext();

	      	n.GetNext().SetPrevious(n);
	      	d.GetPrevious().SetNext(n);
	      	n.SetPrevious(d.GetPrevious());
	      	n.SetNext(d);
	      	d.SetNext(n.GetNext());
	      	d.SetPrevious(n);

nun bekomme ich aber eien Meldung, dass irgendwo ein NullPointer entsteht

Exception in thread "main" java.lang.NullPointerException
at five.Liste.BubbleSort_Par(Liste.java:281)
at five.Liste.main(Liste.java:19)

irgendwie versteh ichs nicht :bahnhof:

 

[KalleWirsch]

ich hab meinen Fehler jetzt doch endlich gefunden ...
ich hatte vergessend er Liste zusagen, dass sie einen neuen Anfang hat ???:L


danke für die Hilfe!!!

mfG!

 

[KalleWirsch]

Noch eine Frage:


Wenn ich also 3 Elemente habe ... El 1 - El 2 - El 3 die sind doppelt verkettet.
jetzt vertausche ich El1 mit El 2 --> El2 - El1 - El3.
Jetzt sage ich El2 das es der Anfang der Liste ist also head = El2
weshalb bekomme ich dann nicht 'null' geliefert wenn ich El2.previous abfrage??

    d.SetNext(next.GetNext()); 
    next.GetNext().SetPrevious(d); 
    d.SetPrevious(next); 
    next.SetNext(d);     
    SetFirst(next); // Hier sage ich next das es der Kopf der Liste ist
    //System.out.println("Check ob null: " + next.GetPrevious());
    d= GetFirst(); // nun wir d der Kopf also praktisch d= next
    System.out.println("Check whatz Previous: " +(j+1)+" "+ d.GetPrevious());

wenn ich d.prev abfrage bekomme ich immer das Element gekliefert das vorher davor angehängt war.
Wenn man die Zeiger verschieb ... behält sich Java das dann??


mfG

 

[SlaterB]

solange du eine Referenz nicht auf null setzt oder auf was anderes,
solange wird auf das vorherige Objekt gezeigt,
kann dann auch nicht zerstört werden oder ähnliches

 

[KalleWirsch]

irgendwie steh ich MEGA aufm Schlauch ...

also ich will ja mit nem Bubblesort meine doppelt verkettete Liste sortieren

public void bubbleSort_Par()
	    {
	      	int length = length();
	      	Datum d = getFirst();
	      	Datum next = d.getNext();
	      	int j=0;
	      	next.setPrevNull();
	      	
	      		while(j < length)
	      		{                /*Hier vertausche ich alle elemente bis auf das letzte*/
			      	if (d.Par_ID() > next.Par_ID() && next.getNext() != null )
		      		{
		      		    d.setNext(next.getNext()); 
				    next.getNext().setPrevious(d); 
				    d.setprevious(next); 
				    next.setnext(d);
				    setfirst(next); /* klar hier wird dann immer das aktuelle Element als head gemacht ... aber wenn ich das nicht so mache bekomme ich die Elemente, die nach head kommen nicht mehr angezeigt*/
				    d= getFirst();
		      		}

                                                                /*hier wird das letzte Element vertausch*/
			      	else if (d.Par_ID() > next.Par_ID() && next.getNext() == null )
			      	{
			      		next.setNext(d);
			      		d.setPrevious(next);
			      		next.setPrevious(d.getPrevious());
			      		setLast(d);
			      	}

	      		//hier wird der aktuelle ptr je eins weiter geschickt
	      		d = d.getNext();
	      		if (next.getNext() != null)
	      		{
	      			next = d.getNext();
	      		}
	      		
	      		j++;

	    }// Ende while Schleife

aber irgendwie bekomm ichs nicht hin.
Einmal weiß ich nicht wie ich den Anfang der Liste setzten soll und zum andern mal klappt es nicht wenn, ich das letzte Element mit dem vorletzten vertauschen will!!!

vielleicht hat ja jemand Tips wie ich meinen Code auf die Richtige Reise bringe.
...
@SlaterB so richtig klappt das nicht die Referenzen auf null zu setzten... Ich kann sie ja nur über Methoden ansprechen und dann zeigt er mir NullPointer Exceptions an ... gibt es da irgend einen Trick???


meine zusätzlichen Methoden:

	    public Datum setLast(Datum f)
	    {
	    	return tail = f;
	    }

                    public void setPrevNull() 
	    {
	    	previous = null;
	    }
	    
	    public void setNextNull()
	    {
	    	next = null;
	    }

Mit setPrev- NextNull will ich bezwecken, dass einem Pointer einen Nullwert geben kann

	    public Datum setLast(Datum f)
	    {
	    	return tail = f;
	    }

 

[SlaterB]

> @SlaterB so richtig klappt das nicht die Referenzen auf null zu
> setzten... Ich kann sie ja nur über Methoden ansprechen und dann
> zeigt er mir NullPointer Exceptions an ... gibt es da irgend einen Trick???

auf ungenaue Beschreibungen kann man nix gescheites antworten,
sowas wie

       public void SetNextNull()
       {
          next = null;
       }

für previous wäre doch nicht schlecht,

dann würde bei

d= GetFirst(); 
d.SetPreviousNull();
System.out.println("Check whatz Previous: " +(j+1)+" "+ d.GetPrevious());

gerantiert null als previous kommen,
und wo soll da eine NullPointerException auftrefen, solange nicht d selber null ist?

ich kann also mit deiner Nachfrage gar nix anfangen

----------

wenn du dich an Java-Konventionen halten würdest, z.B. alle Operationen klein schreiben!,
dann wäre dein Code viel besser lesbar, dann würden vielleicht mehr Leute mit reinschauen,

ich erspare mir jedenfalls, die 40 Zeilen-while-Schleife durchzuarbeiten solange da alles kryptisch ist


falls du eine Überarbeitung vornimmst, dann denke doch bitte auch gleich noch an die Einrückungen,
manche sind 2 Zeichen, andere riesige Tabs, manchmal ist gar keine Einrückung..
Kommentare fliegen durch die Luft..,

benutze die Vorschau bzw. die Edit-Funktion und bedenke:
wichtig ist nicht wie es in deinem Texteditor aussieht,
sondern wie es im Forum aussieht