Verkettete Liste - sortiert einfügen

[Castyll]

Moin,
Ich muss eine per Parameter übergebene Variable aufsteigend sortiert in eine verkettete Liste einfügen. Da ich mir bei dem Thema schwer tue und das Internet leider kaum was zu verkettete Listen hat, suche ich hier Rat.

public void insert(ObjectWithKey o)
{
   int key = o.getKey();
   Listenelement ele = head.next;
   
   while(ele != z)
   {
     if(key <= ele.data.getKey())
     {
       Listenelement newEle = new Listenelement();
       newEle.data = o;
       newEle.next = ele;
       return;
     }
     ele = ele.next;
   }

   Listenelement newEle = new Listenelement();
   newEle.data = o;
   newEle.next = z;
}

key ist ein Attribut der Klasse ObjectsWithKey wessen Objekt als Parameter übergeben wird. z ist das letzte Element
Meine Frage ist jetzt ob mein Ansatz richtig ist oder ob ich etwas vergessen habe?

 

[kaporalix]

für mich ist die Aufgabe nicht deutlich genug, kannst du da ausführlicher erklären, was gemacht werden muss.
was elemente in einer verkettete Listen hinzufügen angeht , hier ein beispiel:

public class Test    {
public static void main(String[] args) {
       
        int[] array = {1,1,0,0}; //array erstellen
   
        List<Integer> liste = new LinkedList<>();  //liste erstellen
        for(int item : array) //gehe die elemente in array durch
            liste.add(item); //und fühge sie in der Liste ein
}

 

[Castyll]

für mich ist die Aufgabe nicht deutlich genug, kannst du da ausführlicher erklären, was gemacht werden muss.
was elemente in einer verkettete Listen hinzufügen angeht , hier ein beispiel:

public class Test    {
public static void main(String[] args) {
    
        int[] array = {1,1,0,0}; //array erstellen

        List<Integer> liste = new LinkedList<>();  //liste erstellen
        for(int item : array) //gehe die elemente in array durch
            liste.add(item); //und fühge sie in der Liste ein
}

Hier nun die gesamte Klasse:

public class Liste implements DynamischeMenge {
   private class Listenelement {
     ObjectWithKey data;
     Listenelement next;

     public Listenelement(){}
     public Listenelement(ObjectWithKey o) {
       this.data = o;
     }

     public String toString() {
       return this.data.toString();
     }
   }

   Listenelement head;
   Listenelement z;

   // generiert Struktur fuer leere Liste
   public Liste() {
     head = new Listenelement();
     z = new Listenelement();
     head.data = null;
     head.next = z;
     z.data = null;
     z.next = z;
   }

   // Ausgabe aller Elemente der Liste
   public void print() {
     Listenelement ele = head.next;
     while (ele != z) {
       System.out.println(ele.data);
       ele = ele.next;
     }
   }

   public void insert(ObjectWithKey o) {
     int key = o.getKey();
     Listenelement ele = head.next;

     while(ele != z) {
       if(key < ele.data.getKey()) {
         Listenelement newEle = new Listenelement();
         newEle.data = o;
         newEle.next = ele;
         break;
       }
       ele = ele.next;
     }
   }
}

Leider kann man bei verketteten Listen nicht ganz so vorgehen wie du es beschrieben hast, da diese Klassen meist selbst geschrieben sind und man die .add methoden selbst schreiben muss.Und bei meiner war ich mir unsicher - leider darf ich auch nicht die normalen Listen nehmen, da das alles Uni Vorgaben sind

 

[Meniskusschaden]

Meine Frage ist jetzt ob mein Ansatz richtig ist oder ob ich etwas vergessen habe?

Am besten wäre es, das einfach zu testen.
Ich glaube nicht, dass es vernünftig funktioniert, denn bereits beim Erzeugen einer leeren Liste entsteht eine seltsame Struktur: Nachfolger von head ist z und Nachfolger von z ist ebenfalls z. Es gibt dann also zwei Elemente, wobei das Zweite Nachfolger des Ersten und gleichzeitig zyklisch mit sich selbst verbunden ist. Das ist doch bestimmt nicht so gewollt.

Beim Versuch, das erste Element einzufügen, müsste hier

Listenelement ele = head.next;
while (ele != z) {
    ...
}

das Problem auftreten, dass du ele auf head.next setzt (also z), so dass die Bedingung der while-Schleife niemals erfüllt wird und somit auch nichts eingefügt wird.

Bei verketteten Listen finde ich es immer hilfreich, es mal auf dem Papier mit Kästchen aufzuzeichnen und die Operationen durch "Umhängen" von Pfeilen nachzuvollziehen.

 

[Castyll]

Am besten wäre es, das einfach zu testen.
Ich glaube nicht, dass es vernünftig funktioniert, denn bereits beim Erzeugen einer leeren Liste entsteht eine seltsame Struktur: Nachfolger von head ist z und Nachfolger von z ist ebenfalls z. Es gibt dann also zwei Elemente, wobei das Zweite Nachfolger des Ersten und gleichzeitig zyklisch mit sich selbst verbunden ist. Das ist doch bestimmt nicht so gewollt.

Beim Versuch, das erste Element einzufügen, müsste hier

das Problem auftreten, dass du ele auf head.next setzt (also z), so dass die Bedingung der while-Schleife niemals erfüllt wird und somit auch nichts eingefügt wird.

Bei verketteten Listen finde ich es immer hilfreich, es mal auf dem Papier mit Kästchen aufzuzeichnen und die Operationen durch "Umhängen" von Pfeilen nachzuvollziehen.

Hallo, ja es gibt auch eine Nullpointer. Leider ist das Erzeugen der Liste so vorgegeben und darf auch nicht verändert werden. Ich habe jetzt noch folgenden Code hinzugefügt um im Falle eines leeren Heads diesen zu befüllen jedoch klappt das immer noch nicht.

if(head.data == null)
{•

Listenelement nachAnfang = new Listenelement();
head.data = o;
head.next = nachAnfang;



}

 

[neoexpert]

import java.util.*;

public class Main
{
   
    private class N{
        public N n;
        public int v;
    }
    N ll=null;
    public static void main(String[] args)
    {
        Main m=new Main();
        for(int i=0;i<20;i++)
            m.insert(new Random().nextInt(20));
       
       
       
        m.print();
    }
    public void print(){
        N l=ll;
        while(l!=null)
        {
            System.out.println(l.v);
            l = l.n;
        }
    }
    public void insert(int key)
    {
        if(ll==null)
        {
            ll=new N();
            ll.v=key;
            return;
        }
        if(key <= ll.v)
        {
            N ne = new N();
            ne.v = key;
            ne.n = ll;
            ll=ne;
           
            return;
        }
        N n=ll;

        while(true)
        {
            if(n.n==null){
                n.n=new N();
                n.n.v=key;
                break;
            }
            if(key <= n.n.v)
            {
                N ne = new N();
                ne.v = key;
                ne.n = n.n;
                n.n=ne;
                return;
            }
           
            n = n.n;
        }
       
    }
   
   
}

 

[thecain]

Soll das ein Rätsel sein oder ist deine Harddisk voll?

 

[neoexpert]

Ja meine Festplatte ist voll, ich wollte den oberen code deshalb hier speichern.