Java Listenimplementation Reverse

  • Allgemein

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von ~blaze~.

    Java Listenimplementation Reverse

    Heyhey,

    Bin gerade dabei eine eigene Implementierung einer Liste in Java zu schreiben, mangels Pointern auf diese Weise:

    Quellcode

    1. public class ListElement<T> {
    2. public T Data;
    3. public ListElement Next;
    4. public ListElement(T data, ListElement next) {
    5. this.Data = data;
    6. this.Next = next;
    7. }
    8. }

    Quellcode

    1. ​public class List<T> {
    2. public ListElement FirstElement;
    3. public List() {
    4. FirstElement = new ListElement(null, null);
    5. }
    6. public void add(T data) {
    7. if(FirstElement.Data!=null){
    8. ListElement nextElem = new ListElement(FirstElement.Data, FirstElement.Next);
    9. FirstElement.Data = data;
    10. FirstElement.Next = nextElem;
    11. }else{
    12. FirstElement.Data = data;
    13. }
    14. }
    15. public T item(int index) {
    16. int ind = 0;
    17. ListElement curr = FirstElement;
    18. while (ind < index) {
    19. curr = curr.Next;
    20. ind++;
    21. }
    22. return (T) curr.Data;
    23. }
    24. public int length() {
    25. if(FirstElement.Next==null) {return 0;}
    26. ListElement curr = FirstElement;
    27. int index = 1;
    28. while (curr.Next != null) {
    29. index++;
    30. curr = curr.Next;
    31. }
    32. return index;
    33. }
    34. }



    Bei der Reverse-Methode hänge ich, ich weiß zwar das Ich das Next Attribut auf den Vorgänger umzeigen lassen muss, allerdings wenn ich es einfach so mache, dann fängt er sich natürlich in einer Schleife.
    Jemand ne Idee wie man das geschickt lösen kann?

    8-) faxe1008 8-)

    Quellcode

    1. public void reverse(){
    2. if(FirstElement.Next == null){return;}
    3. ListElement curr = FirstElement;
    4. ListElement previous = FirstElement;
    5. while(curr.Next != null){
    6. ListElement next = curr.Next;
    7. curr.Next= previous;
    8. previous = curr;
    9. curr = next;
    10. }
    11. }


    Nach nem Ansatz von nem Prof, siehe Anhang. Ich weiß die Programmiersprache, die er verwendet (ADA) ist <X , aber dennoch der Ansatz klingt logisch.
    Bilder
    • Unbenannt.JPG

      49,47 kB, 510×411, 96 mal angesehen

    8-) faxe1008 8-)
    Also typischerweise (bei SingleLinkedList) hat eine leere Liste keine Nodes.
    Jedes Element in der Liste wird durch ein Node-Objekt dargestellt.
    Nur das nächste Node-Objekt des letzte Node-Objekts ist null.
    Hinzufügen und Entfernen von Objekten ändert nie den Inhalt eines Node-Objekts (damit ist ListElement<T>.Data gemeint), sondern fügt neue Nodes hinzu bzw. entfernt bestehende Nodes.
    Dadurch wird die Indexierung und das Zählen der Items einfacher.
    Beispiel-Implementierung

    Java-Quellcode

    1. ​public class List<T> {
    2. public ListElement<T> FirstElement = null;
    3. public void add(T item) {
    4. if (First == null) {
    5. First = new ListElement<T>(item, null);
    6. } else {
    7. /*First.Next = new ListElement<T>(item, null);*/ // Natürlich mit Schleife oder Rekursion
    8. }
    9. }
    10. public int count()
    11. {
    12. int Result = 0;
    13. var CurrentNode = First;
    14. while (CurrentNode != null)
    15. {
    16. Result += 1;
    17. CurrentNode = CurrentNode.Next;
    18. }
    19. return Result;
    20. }
    21. public T item(int Index)
    22. {
    23. if (Index < 0) throw new IndexOutOfRangeException(); // Diese beiden Fälle fehlen bei Dir übrigens
    24. int RemainingHops = Index;
    25. var CurrentNode = First;
    26. while (CurrentNode != null)
    27. {
    28. if (RemainingHops == 0) return CurrentNode.Data;
    29. RemainingHops--;
    30. CurrentNode = CurrentNode.Next;
    31. }
    32. throw new IndexOutOfRangeException(); // Diese beiden Fälle fehlen bei Dir übrigens
    33. }
    34. }


    Was genau meinst Du mit "Reverse-Methode"?
    Meinst Du eine DoubleLinkedList?
    Oder eine SingleLinkedList bei der die Items in der umgekehrten Reihenfolge gemerkt werden?
    Oder meinst Du eine methode, die die Reihenfolge der Elemente in der Liste umkehrt?

    Edit: Ich war etwas zu langsam. Also gemeint war eine methode, die die Reihenfolge der Elemente in der Liste umkehrt??
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    Die einfachste Lösung erscheint mir folgende:
    Eine neue Liste erstellen, die die Elemente rückwärts beinhalten wird.
    Rekursiv die Liste von First bis zum letzten Element durchlaufen.
    Nachdem der rekursive Aufruf zurückkehrt das Item, für das der aktuelle Aufruf gilt, zur neuen Liste hinzufügen (ganz normal mit der existierenden add-Methode).
    Die neue Liste kann dann entweder zurückgegeben werden (dann wird die aktuelle Liste nicht verändert) oder das First-Field kann überschrieben werden, um die aktuelle Liste zu verändern.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    @ErfinderDesRades Leider nicht der dreht endlos Runden in der Schleife.

    @Niko Ortner

    Quellcode

    1. ​public List reverse(){
    2. List returnlist = new List<T>();
    3. ListElement curr = FirstElement;
    4. while(curr.Next != null){
    5. returnlist.add(curr.Data);
    6. curr = curr.Next;
    7. }
    8. returnlist.add(curr.Data);
    9. return returnlist;
    10. }


    So gehts zwar aber ich würde am liebsten keine zweite Liste verwenden müssen, schon allein aus Performance Gründen.

    8-) faxe1008 8-)
    Performance

    ist meistens irrelevant ;) Erst recht, weil Du "Nach nem Ansatz von nem Prof" geschrieben hast, gehe ich davon aus, dass es eine Übung für die Schule sein soll.
    Aber ich kann verstehen, worauf Du hinaus willst.
    Ich bin jetzt auch auf eine Lösung gekommen, die die einzelnen Nodes umdreht. Hab erst Deinen Code nicht verstanden.

    Java-Quellcode

    1. public void reverse()
    2. {
    3. if (First == null) return;
    4. First = ReverseHelper(null, First);
    5. }
    6. private ListElement<T> ReverseHelper(ListElement<T> PreviousNode, ListElement<T> CurrentNode)
    7. {
    8. var NextNode = CurrentNode.Next;
    9. CurrentNode.Next = PreviousNode;
    10. if (NextNode == null) return CurrentNode;
    11. return ReverseHelper(CurrentNode, NextNode);
    12. }

    Kleine Unschönheit: Damit man am Ende an das letzte Node-Objekt kommt, gibt die ReverseHelper-Funktion dieses letzte Element zurück. Dadurch muss in der reverse-Methode nochmal separat geprüft werden, ob First null ist.
    Übrigens gehe ich wie in Post #4 gezeigt davon aus, dass eine leere Liste keine Nodes beinhaltet.
    Noch übrigenser: Was, wenn ich bei Deiner Implementierung null in die Liste einfügen will?
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    Hi,
    wäre das nicht einfach folgende Herangehensweise:
    - wähle erstes Element c der alten Liste
    Solange c != null:
    - merke c.Next in Variable n
    - setze c.Next auf Variable p (Initialwert null)
    - setze p := c
    - setze c := n

    - setze Zeiger auf erstes Element auf p

    Oder hab' ich da was übersehen?

    Edit: Du hast den Algorithmus ja eigentlich sogar umgesetzt, nur previous nicht auf null, sondern auf FirstElement gesetzt.

    Viele Grüße
    ~blaze~