Listen

[newjava^h]

Guten Abend zusammen, ich versuche mich gerade am Thema Listen und habe mal ein kleines Grundgerüst dazu aufgebaut. (Bei Bedarf sind Verbesserungen natürlich erwünscht) Hier mal mein bisheriger Code:

class Link 
{ 
    //Attribute 
    int daten; 
    Link naechster; 
 
    //Konstruktor 
    Link(int daten, Link naechster) 
    { 
        this.daten = daten; 
        this.naechster = naechster;      
    } 
} 
 
public class Liste 
{ 
   //Attribute 
   private Link anfang; 
   private Link ende; 
 
   //Konstruktor 
   public Liste() 
   { 
        anfang = new Link(-1, null); 
        ende = new Link (-1, anfang);   
        anfang.naechster = ende;  
   } 
 
   public void einfuegenElement(int neuerWert) 
   { 
       Link neuerLink = new Link(neuerWert, ende); 
       Link bisherLetzter = ende.naechster; 
       bisherLetzter.naechster = neuerLink; 
       ende.naechster = neuerLink; 
   } 
    
   // Liefert Zeiger auf erstes Nutzelement zurück 
   public Link getAnfang()  
   { 
      return anfang.naechster; 
   } 
    
   public Link getEnde()  
   { 
      return ende; 
   }  
      
}

Mein Problem hierbei ist, die Implementierung einer Klassenmethode namens "public static Liste merge (Liste liste1, Liste liste2)". Mein Ziel ist es aus zwei absteigenden Listen eine neue absteigende Liste erzeugen die alle Werte der anderen beiden Listen enthält, diese soll dann an den Aufrufer zurückgegeben werden.

Nunja wenn ich ehrlich bin weiß ich leider keinen Ansatz wie ich hier vorgehen soll. Ist den mein bisheriger Aufbau der Liste soweit korrekt? Oder gibts da Verbesserungsvorschläge? Bringt nämlich nix wenn ich mich hier an einer bisher unlösbaren Aufgabe versuche wenn schon die Basis falsch ist. Es wäre schön wenn mir jemand einen Ansatz zu meinem Problem liefern könnte, mit dem ich weiterarbeiten könnte, zur Zeit fehlt mir jegliche Idee zu einer vernünftigen Vorgehensweise -.- Würde mich über Antworten sehr freuen!

 

[Gonzo17]

Das sieht ein bisschen konfus aus. Die Klasse "Link" ist soweit in Ordnung, ich würde sie aber eher "Listeneintrag" nennen oder sowas. Die Liste selbst ist dann nicht mehr gut.

Im Konstruktor musst du dir erstmal überlegen was eine leere Liste bedeutet. Ich würde sagen, dass es bei einer Liste einen Einstiegspunkt gibt, also einen Anfang, aber das Ende ist unnötig. Du setzt also ein neues Objekt als Anfang, wobei der Parameter "naechster" natürlich null ist, da es noch keinen nächsten gibt.

Die Methode "einfuegen" könnte dann so funktionieren, dass du mit dem ersten Element beginnst und solange auf das nächste Element springst, bis es "null" ist und genau dann setzt du an diese Stelle das einzufügende Element. Natürlich brauchst du da immer linearen Aufwand und musst einmal durch die ganze Liste. Ist aber bei einfach verketteten Listen so.

Die Methoden, die dir Anfang und Ende liefern, sind auch simpel. Für den Anfang gibst du einfach das erste Element selbst zurück, für das Ende eben das letzte Element der Liste (bei diesem Element ist logischerweise "naechster" auf null).

So, jetzt das "merge". Das ist ziemlich simpel. Du hast Liste 1 und willst Liste 2 hintendran hängen. Das bedeutet schlicht und ergreifend, dass du beim letzten Element von Liste 1 als "naechster" das erste Element von Liste 2 einträgst. Damit zeigt das Ende von Liste 1 auf den Anfang von Liste 2.

 

[XHelp]

Zu der jetzigen Liste: die

einfuegenElement

-Methode sieht falsch aus. Mal dir mal so eine Liste auf und spiel mal auf dem Blatt durch was da passiert. Es geht um die Zeile 32 und 34.

Zu deinem Problem: nimm eine Liste als Ausgang. Dann musst du die von vorne durchlaufen und gucken, zwischen welchen Elementen das erste Element aus der 2. Liste passt. Anschließend es zwischen diesen beiden Elementen einfügen. Dann guckst du ob das 2. Element aus der 2. Liste passt, wenn nicht, die Liste weiter durchlaufen etc.

 

[HimBromBeere]

Naja, völlig abwägig finde ich das mit dem Ende nicht, spart das ewige Suchen nach dem Schwanz der Schlange. Wenn die Liste dann auch noch doppelt verketet werden soll, ergibt sich daraus eine rückwärts-Lesemöglichkeit, was durchaus seinen Reiz hat (OK, die gints imho auch ohne Ende-Variable...).
Das mit frm merge hab ich aber anders verstanden: es soll nicht Liste2 an 1 angehänfgt, sondern mit dieser zusammen sortiert werden. Dafür kannst du entweder alles zusammenschmeißen und die neue Liste sortieren, oder aber du suchst für jedes neue Element aus Liste 2, welches du in deine große Liste einfügst, welches Element aus Liste1 GERADE NOCH SO kleiner als dieses ist und fügst es hinten an... finde ich zwar schwieriger, dürfte aber schneller sein...

 

[Xpisto]

Also mit dem normalen verketten kann ich dir helfen, aber wie man dann sortiert weiss ich leider nicht, vllt kann da jemand helfen der mehr ahnung hat?

Verketten

public void verketten(Liste zweiteListe) 
{ 
   if (!zweiteListe.istLeer()) 
   { 
     Link zeigerAufErstesElementDerZweitenListe = zweiteListe.getAnfang().naechster; 
     Link zeigerAufVorletztesElement = ende.naechster; 
     zeigerAufVorletztesElement.naechster = zeigerAufErstesElementDerZweitenListe;
     ende = zweiteListe.getEnde();  
   } 
}

Also mich interessiert diese frage auch brennend, hoffentlich kann jemand helfen.

 

[Xpisto]

Das mit frm merge hab ich aber anders verstanden: es soll nicht Liste2 an 1 angehänfgt, sondern mit dieser zusammen sortiert werden. Dafür kannst du entweder alles zusammenschmeißen und die neue Liste sortieren, ...

Finde diesen Ansatz am besten alles erstmal verketten und dann sortieren, man muss es sich aj nicht umständlich machen. Wie würde man dass sortieren denn dann umsetzen? in meiner vorlesung steht z.b. gar nichts über das sortieren von listen.....