Liste: Unterschied zwischen den Versionen
Hauer (Diskussion | Beiträge) |
|||
| Zeile 1: | Zeile 1: | ||
| − | Eine Liste ist eine einfache rekursive Datenstruktur. In der Objektorientierung wird eine Liste dabei meist aus zwei verschiedenen | + | Eine '''Liste''' ist eine einfache rekursive [[Datenstruktur]]. In der [[Objektorientierte Programmierung|Objektorientierung]] wird eine Liste dabei meist aus zwei verschiedenen [[Klasse]]n zusammengesetzt: Einer Art Verwaltungsklasse, die Repräsentant der Liste selbst ist, und einer Klasse für die Elemente, die von der Liste verwaltet werden sollen. |
| − | Eine Liste besteht dabei aus einem ersten Element und, falls gewünscht, einem letzten Element. Ein Element speichert dabei immer genau einen Eintrag in der Liste und eine Referenz auf das nächste Element der Liste. Durch diese Verkettung der Referenzen entsteht die Reihenfolge der Elemente in der Liste. | + | Eine '''Liste''' besteht dabei aus einem ersten '''Element''' und, falls gewünscht, einem letzten Element. Ein Element speichert dabei immer genau einen Eintrag in der Liste und eine Referenz auf das nächste Element der Liste ('''next-Referenz'''). Durch diese Verkettung der Referenzen entsteht die Reihenfolge der Elemente in der Liste. |
= Verwaltungsklasse = | = Verwaltungsklasse = | ||
| − | Die eigentlichen Listenobjekte besitzen je eine Referenz auf das erste und das letzte Element der Liste. Eine Liste ist leer, wenn die Referenzen des ersten und letzten Elementes auf | + | Die eigentlichen '''Listenobjekte''' besitzen je eine Referenz auf das erste und das letzte Element der Liste. Eine Liste ist leer, wenn die Referenzen des ersten und letzten Elementes auf den [[Nullpointer]] zeigen. |
Diese Verwaltungsklasse ist die Klasse, die ein Anwendungsprogrammierer verwenden möchte, um mit einer Liste zu arbeiten. | Diese Verwaltungsklasse ist die Klasse, die ein Anwendungsprogrammierer verwenden möchte, um mit einer Liste zu arbeiten. | ||
| Zeile 12: | Zeile 12: | ||
Auf Listen können folgende Operationen ausgeführt werden: | Auf Listen können folgende Operationen ausgeführt werden: | ||
| − | * Anfügen | + | * '''Anfügen''' eines neuen Elementes |
| − | * Einfügen eines neuen Elementes an einer bestimmten Position in der Liste | + | * '''Einfügen''' eines neuen Elementes an einer bestimmten Position in der Liste |
| − | * Auslesen eines beliebigen Elementes der Liste | + | * '''Auslesen''' eines beliebigen Elementes der Liste |
| − | * Entfernen eines beliebigen Elementes der Liste | + | * '''Entfernen''' eines beliebigen Elementes der Liste |
| − | * Abfrage, ob die Liste leer ist | + | * '''Abfrage''', ob die Liste leer ist |
| − | * Leeren der Liste | + | * '''Leeren''' der Liste |
=== Anfügen === | === Anfügen === | ||
| − | Anfügen ist, je nach Implementierung, relativ einfach: | + | '''Anfügen''' bedeutet immer, ein Element am Ende der Liste hinzuzufügen. |
| + | |||
| + | Es ist, je nach Implementierung, relativ einfach: | ||
* Wenn das letzte Element der Liste bekannt ist, so wird die Referenz des nächsten Elementes dieses letzten Elementes auf das neue Element gesetzt und die Referenz auf das letzte Element der Liste wird auf das neue Element gesetzt. | * Wenn das letzte Element der Liste bekannt ist, so wird die Referenz des nächsten Elementes dieses letzten Elementes auf das neue Element gesetzt und die Referenz auf das letzte Element der Liste wird auf das neue Element gesetzt. | ||
| − | * Wenn das letzte Element der Liste nicht vermerkt wird, so wird die gesamte Liste bis zum ersten Vorkommen einer '''null''' Referenz durchlaufen und die entsprechende Referenz wird auf das neue Element gesetzt. | + | * Wenn das letzte Element der Liste nicht vermerkt wird, so wird die gesamte Liste bis zum ersten Vorkommen einer '''null'''-Referenz durchlaufen und die entsprechende Referenz wird auf das neue Element gesetzt. |
=== Einfügen === | === Einfügen === | ||
| − | Beim Einfügen muss die Liste vom ersten Element bis zur gewünschten Position durchlaufen werden. Ist die gewünschte Position gefunden wird die '''next''' Referenz des vorherigen Elementes auf das neue Element gesetzt und die '''next''' Referenz des neuen Elementes auf die ehemalige '''next''' Referenz des vorherigen Elementes. Die Referenzen dürfen bei der Implementierung dabei natürlich auf keinen Fall verloren gehen, sonst bricht die Kette und die Liste verliert ihre Daten. | + | Beim '''Einfügen''' muss die Liste vom ersten Element bis zur gewünschten Position durchlaufen werden. Ist die gewünschte Position gefunden, wird die '''next'''-Referenz des vorherigen Elementes auf das neue Element gesetzt und die '''next'''-Referenz des neuen Elementes auf die ehemalige '''next'''-Referenz des vorherigen Elementes. Die Referenzen dürfen bei der Implementierung dabei natürlich auf keinen Fall verloren gehen, sonst bricht die Kette und die Liste verliert ihre Daten. |
=== Auslesen === | === Auslesen === | ||
| − | Beim Auslesen wird die Liste bis zum gewünschten Element durchlaufen und der Wert des gewünschten Elementes zurückgegeben. | + | Beim '''Auslesen''' wird die Liste bis zum gewünschten Element durchlaufen und der Wert des gewünschten Elementes zurückgegeben. |
=== Entfernen === | === Entfernen === | ||
| − | Beim Entfernen wird die Liste bis zum gewünschten Element durchlaufen und sich das direkt vorherige Element zwischengemerkt. Ist das Element gefunden wird die '''next''' Referenz des vorherigen Elementes auf das übernächste gesetzt. Dadurch ist das zu entfernende Element nicht mehr erreichbar und wird [[Garbage Collector | freigegeben]]. | + | '''Entfernen''' geschieht entweder per Angabe des zu entfernenden Elementes oder durch Angabe des Indizes. |
| + | |||
| + | Beim Entfernen wird die Liste bis zum gewünschten Element durchlaufen und sich das direkt vorherige Element zwischengemerkt. Ist das Element gefunden, wird die '''next''' Referenz des vorherigen Elementes auf das übernächste gesetzt. Dadurch ist das zu entfernende Element nicht mehr erreichbar und wird [[Garbage Collector | freigegeben]]. | ||
=== Leeren === | === Leeren === | ||
| Zeile 43: | Zeile 47: | ||
= Elementklasse = | = Elementklasse = | ||
| − | Ein Objekt der Elementklasse ist meistens nicht nach Außen sichtbar und für den Anwendungsentwickler, der die Liste verwendet, nicht von Interesse. Es besitzt ein Feld, um den Wert des gespeicherten Datums zu speichern und eine Referenz auf das nächste Element in der Liste | + | Ein [[Objekt]] der '''Elementklasse''' ist meistens nicht nach Außen sichtbar und für den Anwendungsentwickler, der die Liste verwendet, nicht von Interesse. Es besitzt ein Feld, um den Wert des gespeicherten Datums zu speichern und eine Referenz auf das nächste Element in der Liste. |
| − | + | ||
| − | + | ||
| − | + | Die Operationen der '''Liste''' nehmen ausschließlich Werte vom [[Datentyp|Typ]] der in der Elementklasse gespeicherten Daten, nicht jedoch vom Typ der Elementklasse selbst entgegen und geben auch nur diese zurück . | |
| − | + | ||
Version vom 24. Mai 2016, 12:00 Uhr
Eine Liste ist eine einfache rekursive Datenstruktur. In der Objektorientierung wird eine Liste dabei meist aus zwei verschiedenen Klassen zusammengesetzt: Einer Art Verwaltungsklasse, die Repräsentant der Liste selbst ist, und einer Klasse für die Elemente, die von der Liste verwaltet werden sollen.
Eine Liste besteht dabei aus einem ersten Element und, falls gewünscht, einem letzten Element. Ein Element speichert dabei immer genau einen Eintrag in der Liste und eine Referenz auf das nächste Element der Liste (next-Referenz). Durch diese Verkettung der Referenzen entsteht die Reihenfolge der Elemente in der Liste.
Inhaltsverzeichnis
Verwaltungsklasse
Die eigentlichen Listenobjekte besitzen je eine Referenz auf das erste und das letzte Element der Liste. Eine Liste ist leer, wenn die Referenzen des ersten und letzten Elementes auf den Nullpointer zeigen. Diese Verwaltungsklasse ist die Klasse, die ein Anwendungsprogrammierer verwenden möchte, um mit einer Liste zu arbeiten.
Operationen
Auf Listen können folgende Operationen ausgeführt werden:
- Anfügen eines neuen Elementes
- Einfügen eines neuen Elementes an einer bestimmten Position in der Liste
- Auslesen eines beliebigen Elementes der Liste
- Entfernen eines beliebigen Elementes der Liste
- Abfrage, ob die Liste leer ist
- Leeren der Liste
Anfügen
Anfügen bedeutet immer, ein Element am Ende der Liste hinzuzufügen.
Es ist, je nach Implementierung, relativ einfach:
- Wenn das letzte Element der Liste bekannt ist, so wird die Referenz des nächsten Elementes dieses letzten Elementes auf das neue Element gesetzt und die Referenz auf das letzte Element der Liste wird auf das neue Element gesetzt.
- Wenn das letzte Element der Liste nicht vermerkt wird, so wird die gesamte Liste bis zum ersten Vorkommen einer null-Referenz durchlaufen und die entsprechende Referenz wird auf das neue Element gesetzt.
Einfügen
Beim Einfügen muss die Liste vom ersten Element bis zur gewünschten Position durchlaufen werden. Ist die gewünschte Position gefunden, wird die next-Referenz des vorherigen Elementes auf das neue Element gesetzt und die next-Referenz des neuen Elementes auf die ehemalige next-Referenz des vorherigen Elementes. Die Referenzen dürfen bei der Implementierung dabei natürlich auf keinen Fall verloren gehen, sonst bricht die Kette und die Liste verliert ihre Daten.
Auslesen
Beim Auslesen wird die Liste bis zum gewünschten Element durchlaufen und der Wert des gewünschten Elementes zurückgegeben.
Entfernen
Entfernen geschieht entweder per Angabe des zu entfernenden Elementes oder durch Angabe des Indizes.
Beim Entfernen wird die Liste bis zum gewünschten Element durchlaufen und sich das direkt vorherige Element zwischengemerkt. Ist das Element gefunden, wird die next Referenz des vorherigen Elementes auf das übernächste gesetzt. Dadurch ist das zu entfernende Element nicht mehr erreichbar und wird freigegeben.
Leeren
Die Referenz auf das erste (und letzte) Element der Liste wird einfach auf null gesetzt. Dadurch sind alle zuvor in der Liste vorhandenen Elemente nicht mehr erreichbar und werden freigegeben.
Elementklasse
Ein Objekt der Elementklasse ist meistens nicht nach Außen sichtbar und für den Anwendungsentwickler, der die Liste verwendet, nicht von Interesse. Es besitzt ein Feld, um den Wert des gespeicherten Datums zu speichern und eine Referenz auf das nächste Element in der Liste.
Die Operationen der Liste nehmen ausschließlich Werte vom Typ der in der Elementklasse gespeicherten Daten, nicht jedoch vom Typ der Elementklasse selbst entgegen und geben auch nur diese zurück .
