Lineare Datenstrukturen Generell

Eine Lineare Datenstruktur ist eine Datenstruktur die Objekt (Klassen, Primitive, etc...) in reihenfolge speichern kann. Beispiele dafür sind Arrays, Listen oder Queues. Im folgenden beschäftige ich mich mit dynamischen linearen Datenstrukturen, die ihre Struktur (Speicherbelegung) dynamisch an die anzahl der Listenelemente anpassen und damit flexibel groß sein können. Ein Array zum Beispiel ist nicht dynamisch, da es einen festen Speicherplatz beim initialisieren belegt und damit eine feste Länge hat.

Stacks

Der Stack arbeitet nach dem first in last out prinzip. Das bedeutet, das man Elemente wie bei einem papierstapel drauflegen und runternehmen kann. Dabei wird immer das letzte Element zuerst runtergenommen.

Dadurch kann sich folgende Operationen überlegen:

  • Lege ein Element drauf
  • Nimm das obere Element runter.
  • Gib das obere Element aus.

Der Stack enthält das oberste Stackelement als Attribut. Ein Stackelement ist ein Objekt, was den zu speichernden Inhalt und das nächste Element als Attribut hat. Dadurch referenzieren sich die Elemente immer weiter gegenseitig.

Wenn ein neues Objekt draufgelegt wird, speichert dieses die Referenz zum vorherigen ersten Element und wird als oberstes element im Stack gespeichert. Da das erste Element bei einem leeren Stack null ist, referenziert das letzte Element immer null als nächstes. Dadurch ist es einfach zu erkennen, wann der Stack zu ende ist.

classDiagram class Stack~ContentType~ { top() : ~ContentType~ push(~ContentType~) : void pop() : void } class StackNode~ContentType~ { content: ~ContentType~ } Stack <-- StackNode : top StackNode <-- StackNode : next

Queue

Eine Queue funktioniert ahnlich wie ein Stack. Die Queue arbeitet nach dem First in - First out prinzip. Dafür wird das neueste Element und das älteste Element in der Queue referenziert. Die QueueNodes referenzieren jeweils das neuere Element, welches dementsprechend als nächstes das abzurufende wäre. Auch enthalten die Nodes wieder das Inhaltsobjekt.

classDiagram class Queue~ContentType~ { append(~ContentType~) : void first() : ~ContentType~ remove() : void } class QueueNode~ContentType~ { content : ~ContentType~ } Queue <-- QueueNode : first Queue <-- QueueNode : last QueueNode <-- QueueNode : next

Um in einer Queue ein Objekt hinzuzufügen wird es zum vorher letzten als nächstes referenziert und dann in der Queue als letztes referenziert. Genau wie beim Stack ist das nächste Element der letzten Node null

Liste

Die Liste ist wie eine dynamische Version des Arrays. Eine Liste hat einen Zeiger, der auf das aktuelle Element verweist. Dieser kann frei innerhalb der Liste bewegt werden. Ebenfalls hat die Liste einen Verweis auf das erste und das letzte Element, um die Navigation zu vereinfachen.

classDiagram class Liste~ContentType~ { toFirst() : void toLast() : void getContent() : ~ContentType~ next() : void isEmpty() : boolean remove() : void append(~ContentType~) : void concat(Liste~ContentType~) : void getPrevNode(Node~ContentType~) : Node~ContentType~ } class Node~ContentType~ { content : ~ContentType~ } Liste <-- Node : first Liste <-- Node : last Liste <-- Node : current Node <-- Node : next

Die Liste ist so strukturiert, dass jede Node die referenz zum nächsten Element speichert. Dadurch ergibt sich wie auch schon bei der Queue eine Kette. Man spricht hierbei von einer Linked-List. Würden die Nodes auch eine Referenz auf das vorherige Element, also in beide Richtungen speichern, wäre es eine Double-Linked-List.

Die Liste hat die Vorteile, wenn man Ansammlungen von verschieden großen Mengen speichern will und man nicht unnötig viel speicherplatz zuweisen will. Die standard-Java Bibliothek hat die Klasse LinkedList, die genau diese Aufgabe übernimmt.