Eigene LinkedLists

[Josef Sniatecki]

Seit einiger Zeit häufen sich geradezu die Threads mit dem Titel "LinkedList in LinkedList?". Daher habe ich mal wieder meine Schreib-Tutorial-Laune bekommen :
PDF-Download (75 KB)

Korrekturen, Kommentare und Fragen bitte posten.
Gruß Josef

[STARGÅTE]

naja, für n LinkedList fehlen aber noch n ganze menge wichtiger Proceduren ...

Klar wäre nach deinem PDF n Linkedlist funktionsfähig, aber viel machen kann man damit nicht.

Beim Einfügen von Elementen, müssen mehr Situationen abgefragt werden.
Jenachdem ob man nach oder vor einem aktuellen Element einfügen will, und wo sich dann das neue element befindet.

Beim Löschen tritt das dann noch mal auf, wohin wird gesprungen usw.

Was vielleicht ein schritt tiefer ginge wäre n TUT für Bäume ... die kann man ja dann auch nur als Liste missbrauchen oder wirklich als Baum ... in dem man sich bewegen kann, Äste raushemen kann und in andere Baume einfügen kann ...

[Josef Sniatecki]

Durch die Funktionen die wir uns vorher definiert haben, besitzen wir schon genug Kenntnisse, um Befehle für das Löschen einer gesamten Liste zu programmieren. Genauso können wir uns auch Befehle programmieren, die Elemente an jede beliebige Stelle hinzufügen. Auch das gezielte Löschen von einzelnen Elementen ist leicht zu realisieren, wenn man sich die Verwaltung der Verweise genauer überdenkt. Und wenn man noch viel mehr machen möchte, so kann man sich z.B. eine Sortierfunktion definieren, die nach dem „Bubblesort“-Algorithmus arbeiten.

Auch wenn es sehr vom Vorteil ist, selbst eine solche Befehlssammlung zu erweitern, stelle ich auch meine Sammlung zu dynamisch verketteten Listen zur Verfügung:
http://sourceforge.net/projects/pb-stl/
Die Quelldatei trägt den Namen „Queue.pbi“.

Klar hast recht Stargate. Das Einfügen und Löschen von Elementen an jeder beliebigen Stelle ist natürlich sehr wichtig, nur da hat meine Schreib-Tutorial-Laune irgendwie aufgehört . Trotzdem habe ich einfach mal darauf hingewiesen, was man alles noch machen kann und habe zudem noch meinen vollständigen Quellcode mit angegeben.

Ein Tutorial für Trees wäre natürlich auch sehr vom Nutzen... aber wie gesagt, da fehlt mir ein wenig die Zeit und Laune dafür. Ich wollte einfach nur mal Grundsätzlich erklären, wie so eine Liste funktioniert und dies an einem kleinen, lauffähigen Code-Beispiel zeigen.

[STARGÅTE]

Jo klar, aber du solltest wenigstens noch ein paar Hinweise zum richtigen Löschen der erstellten Speicher geben:
LinkedList-Header, LinkedList-Elemente, Strings in Elementen, ...

Vernachlässigt man solche Sachen, weil man sich denkt, die paar Bytes schaden schon nicht, und baut solch eine eigene LinkedList wirklich in ein Spiel / Anwendung, dann bekommt man schnell probleme.

Gerade dann wenn man viel mit AllocateMemory() arbeitet, deren RückgabeWert man nicht explizit speichert, sonden nur in anderen Elementen sichert, hat man selber keine direkte kontorlle mehr, wie viele Speicher wirklich erstellt wurden.

wenn dann ein ClearList() nicht richtig funktioniert, hat man schnell n menge String- und Element-Leichen im RAM ...

Da es ja hier um ein Tut geht, sollten solche in manchen augen offensichtlichen Sachen auch mit rein!
Und zwar so früh wie möglich, eh uns morgen einer im Anfänger Forum fragt wieso sein Programm abstürzt wenn er dein TUT umgesetzt hat ...


Auch sollte sowas im Tut verbessert werden:

Code: Alles auswählen

Procedure.i NewInteger(Number.i)
Protected *Memory.Integer
  *Memory = AllocateMemory(SizeOf(Integer))
  *Memory\I = Number
  ProcedureReturn *Memory
EndProcedure

zu

Code: Alles auswählen

Procedure.i NewInteger(Number.i)
  Protected *Memory.Integer
  *Memory = AllocateMemory(SizeOf(Integer))
  If *Memory
    *Memory\I = Number
  EndIf
ProcedureReturn *Memory
EndProcedure

denn man sollte nur dann in einen Speicher schreiben wenn er auch wirklich erstellt wurde.
Auch wenn viele sagen werden, wann tritt der fall schon ein das AllocateMemory fehlschlegt!

[ts-soft]

wann tritt der fall schon ein das AllocateMemory fehlschlegt!

Laut Murphys Gesetz immer dann, wenn Du Sicher bist, es kann nicht fehlschlagen

Deswegen ist diese If auch wichtig!

[Josef Sniatecki]

@ts-soft:

@Stargate:
Danke für deine Kritik. Habe mir beim schreiben keine Gedanken über mögliche Speicherlecks gemacht, die bei Anfängern mit Lists entstehen können.

OK, wie man so gerne sagt: Aus Fehlern lernt man. Also dann, noch einen schönen Tag. Werd mal immer wieder ein bisschen was verbessern und erweitern. Vielleicht versuch ich das ganze dann sogar mit LyX zu schreiben.

Ich werde mich dazu dann mal wieder melden, sobald ich fertig bin.

Gruß Josef

[DarkDragon]

Was vielleicht ein schritt tiefer ginge wäre n TUT für Bäume ... die kann man ja dann auch nur als Liste missbrauchen oder wirklich als Baum ... in dem man sich bewegen kann, Äste raushemen kann und in andere Baume einfügen kann ...

Wieso nicht gleich für Graphen allgemein, wenn es dir eh nur um sowas geht?