Verkettete Liste - sortiert einfügen

C

Castyll

Aktives Mitglied
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.
Java:
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?
 
Zuletzt bearbeitet von einem Moderator:
K

kaporalix

Mitglied
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:

Java:
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
}
 
C

Castyll

Aktives Mitglied
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:

Java:
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:

Java:
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
 
Zuletzt bearbeitet von einem Moderator:
M

Meniskusschaden

Top Contributor
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
Java:
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.
 
C

Castyll

Aktives Mitglied
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.
Code:
if(head.data == null)
{•

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



}
 
N

neoexpert

Gast
Java:
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;
        }
       
    }
   
   
}
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
A Verkettete Liste Java Basics - Anfänger-Themen 2
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
L verkettete Liste Java Basics - Anfänger-Themen 15
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
H Verkettete Liste Java Basics - Anfänger-Themen 7
N Verkettete liste rückwärts ausgeben Java Basics - Anfänger-Themen 5
K Verkettete Liste und seine Methoden Java Basics - Anfänger-Themen 1
N Verkettete Liste implementieren Java Basics - Anfänger-Themen 5
O Einfach verkettete Liste - Revert Methode Java Basics - Anfänger-Themen 1
G Verkettete Liste - Neu erzeugte Elemente werden nicht ausgegeben Java Basics - Anfänger-Themen 5
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
B Doppelt Verkettete Liste - Ist alles gut so? Java Basics - Anfänger-Themen 3
R Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel Java Basics - Anfänger-Themen 11
U Datentypen Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 13
J Methoden Doppelt verkettete Liste remove(Object) Java Basics - Anfänger-Themen 8
B OOP Über eine doppelt verkettete Liste iterieren Java Basics - Anfänger-Themen 4
hooked Verkettete Liste / linked list Java Basics - Anfänger-Themen 2
L Doppelt verkettete Liste Java Basics - Anfänger-Themen 6
J Eine Art verkettete Liste aber mit teils mehr als einem Nachfolger Java Basics - Anfänger-Themen 8
V Verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 3
R doppelt verkettete Liste aus Arrays erstellen Java Basics - Anfänger-Themen 1
K Einfach Verkettete Liste - addFirst() Java Basics - Anfänger-Themen 7
G 2 Aufgabe rund um eine verkettete Liste Java Basics - Anfänger-Themen 2
O Verkettete Liste Java Basics - Anfänger-Themen 10
E Methoden auf von Methoden erstellte Objekte zugreifen (verkettete Liste) Java Basics - Anfänger-Themen 10
X Einfach verkettete Liste, keine Fehlermeldung Programm friert ein Java Basics - Anfänger-Themen 4
S Doppelt verkettete Liste Java Basics - Anfänger-Themen 3
G Doppelt Verkettete Liste Java Basics - Anfänger-Themen 2
A Doppelt Verkettete Liste Java Basics - Anfänger-Themen 16
E doppelt verkettete liste Java Basics - Anfänger-Themen 10
V Verkettete Liste. Java Basics - Anfänger-Themen 7
X Einfach Verkettete Liste Java Basics - Anfänger-Themen 16
K Verkettete Liste - Methode entwerfen Java Basics - Anfänger-Themen 14
S Verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 12
B Insertionsort verkettete Liste Java Basics - Anfänger-Themen 4
B Stack in eine verkettete Liste pushen Java Basics - Anfänger-Themen 4
R verkettete liste ansEndeSchieben Java Basics - Anfänger-Themen 13
T Verkettete Liste Java Basics - Anfänger-Themen 14
A Klassen Innere Klassen, verkettete Liste Java Basics - Anfänger-Themen 9
B Zweifach-verkettete Liste umkehren Java Basics - Anfänger-Themen 6
X verkettete Liste Java Basics - Anfänger-Themen 13
E Datentypen Doppelt verkettete Liste Java Basics - Anfänger-Themen 10
P Einfügen in doppelt verkettete Liste Java Basics - Anfänger-Themen 7
kae verkettete Liste Java Basics - Anfänger-Themen 5
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
S Stack als verkettete liste/ toString methode Java Basics - Anfänger-Themen 3
B OOP Verkettete Liste Java Basics - Anfänger-Themen 7
R verkettete liste Java Basics - Anfänger-Themen 5
M Verkettete Liste Java Basics - Anfänger-Themen 4
M verkettete liste Java Basics - Anfänger-Themen 7
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
K Datentypen Einfach/Doppelt verkettete Liste Java Basics - Anfänger-Themen 4
N einfach verkettete liste fehler Java Basics - Anfänger-Themen 5
N einfach verkettete liste Java Basics - Anfänger-Themen 3
G verkettete Liste - invertieren Java Basics - Anfänger-Themen 2
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
B verkettete Liste Java Basics - Anfänger-Themen 8
S zyklisch verkettete Liste erstellen Java Basics - Anfänger-Themen 3
S einfach verkettete Liste Java Basics - Anfänger-Themen 19
O Stack Implementierung als verkettete Liste Java Basics - Anfänger-Themen 8
W Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 2
T Einfach verkettete Liste: Wie Elemente löschen? Java Basics - Anfänger-Themen 4
J verkettete Liste Java Basics - Anfänger-Themen 2
D Einfach verkettete Liste Java Basics - Anfänger-Themen 20
DasDogma Verkettete Liste - Element löschen Java Basics - Anfänger-Themen 2
H Verkettete Liste Java Basics - Anfänger-Themen 5
M verkettete Liste auslesen Java Basics - Anfänger-Themen 7
K eigene verkettete Liste Java Basics - Anfänger-Themen 4
G Doppelt verkettete, generische Liste Java Basics - Anfänger-Themen 11
A Eine verkettete Liste Java Basics - Anfänger-Themen 43
G verkettete lineare Liste Java Basics - Anfänger-Themen 2
L verkettete Liste - Ausgabeproblem Java Basics - Anfänger-Themen 2
G Wie kann ich eine verkettete Liste in ein JTable einfügen? Java Basics - Anfänger-Themen 7
D doppelt verkettete Liste Java Basics - Anfänger-Themen 16
S Doppelt Verkettete Liste Java Basics - Anfänger-Themen 7
R ArrayList Objekt -> verkettete Liste Java Basics - Anfänger-Themen 4
R verkettete Liste Java Basics - Anfänger-Themen 13
R verkettete Liste in und aus Datei Java Basics - Anfänger-Themen 5
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
J doppelt verkettete Liste Java Basics - Anfänger-Themen 5
L doppelt verkettete Liste Java Basics - Anfänger-Themen 6
C einfach verkettete Liste -> Elemente vertauschen Java Basics - Anfänger-Themen 2
0 Binärbaum als verkettete Liste Java Basics - Anfänger-Themen 3
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 12
G Dopplelt verkettete liste Java Basics - Anfänger-Themen 4
B Doppelt verkettete Liste Java Basics - Anfänger-Themen 16
R einfach verkettete Liste, intersect Java Basics - Anfänger-Themen 4
R Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE! Java Basics - Anfänger-Themen 12
E einfach verkettete liste, nullPointerException Java Basics - Anfänger-Themen 5
S Queue als verkettete Liste Java Basics - Anfänger-Themen 9
R doppelt verkettete Liste Java Basics - Anfänger-Themen 8
F doppelt verkettete liste! Java Basics - Anfänger-Themen 8
M Verkettete Liste (schritt für schritt durchlauf) Java Basics - Anfänger-Themen 5
R doppelt verkettete azyklische Liste Java Basics - Anfänger-Themen 2
Z Zyklisch verkettete Liste Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben