Verständnisfragen bezüglich Liste

[Mr.Käse]

Moin,

Wir haben in der Schule letztens die Datenstruktur einfach verkettete Liste programmiert und ich habe da noch einige Fragen, die mir mein Lehrer nicht so richtig beantworten konnte, dass ich es nachvollziehen konnte.

So haben wir für die Daten der Knoten ein Interface programmiert, an das wir die eigentliche Klasse mit den zu verwaltenden Daten angehängt haben. Meine Frage wäre jetzt, warum nimmt man ein Interface? Was hat das für Vorteile? Und warum verwendet man bei der eigentlichen Klasse, die die Daten verwaltet 'implements' und nicht 'extends', um vom Inteface "zu erben"? Ist das einfach so in Java festgelegt worden oder besteht die Möglichkeit beide Schlüsselwörter zu verwenden?

Meine nächste Frage bezieht sich auf den Fakt, der uns vorgegeben wurde, dass die Liste eine rekursive Datenstruktur ist. Meine Frage ist jetzt, was allgemein kennzeichnend für eine rekursive Datenstruktur ist bzw. was das bedeutet, wenn eine Datenstruktur rekursiv ist. Rekursion an sich verstehe ich, aber ich sehe noch keine allgemeine Regel, an der man erkennt, dass eine Datenstruktur rekursiv ist. Wenn ihr mir das vllt. erklären könntet, wäre ich euch sehr dankbar.

Das war's erstmal. Ich hoffe ich habe nichts vergessen und freue mich auf Antworten

 

[Gast2]

So haben wir für die Daten der Knoten ein Interface programmiert, an das wir die eigentliche Klasse mit den zu verwaltenden Daten angehängt haben. Meine Frage wäre jetzt, warum nimmt man ein Interface? Was hat das für Vorteile? Und warum verwendet man bei der eigentlichen Klasse, die die Daten verwaltet 'implements' und nicht 'extends', um vom Inteface "zu erben"? Ist das einfach so in Java festgelegt worden oder besteht die Möglichkeit beide Schlüsselwörter zu verwenden?

Man erbt nicht von Interfaces, man implementiert sie, daher das Stichwort

implements

. Bei Vererbung verwendet man

extends

.
Warum Interfaces? Das hat den Vorteil dass du irgendwann mal die Implementierung austauschen kannst ohne was am restlichen Programm ändern zu müssen. Dein Programm hat nur die Sicht auf das Interface, wie genau das implementiert ist, ist deinem Programm egal.

Meine nächste Frage bezieht sich auf den Fakt, der uns vorgegeben wurde, dass die Liste eine rekursive Datenstruktur ist. Meine Frage ist jetzt, was allgemein kennzeichnend für eine rekursive Datenstruktur ist bzw. was das bedeutet, wenn eine Datenstruktur rekursiv ist. Rekursion an sich verstehe ich, aber ich sehe noch keine allgemeine Regel, an der man erkennt, dass eine Datenstruktur rekursiv ist. Wenn ihr mir das vllt. erklären könntet, wäre ich euch sehr dankbar.

Rekursive Datenstrukturen

 

[Marco13]

Der Link enthält Beispiele, aber keine Definition im Sinne eines Unterscheidungskriteriums.
Die würde mich aber auch mal interessieren.
Das "Bauchgefühl" ist klar:
- Ein Knoten ist eine Liste
- "Ein Knoten vor einer Liste" ist eine Liste
oder
- Ein Knoten ist ein Baum
- "Ein Knoten and dem n Bäume hängen" ist ein Baum
Aber ein "Bauchgefühl" ist in einer Prüfung (manchmal Gold, aber meistens) einen Sch-dreck wert.

Analog dazu, dass man jede Rekursion in eine Iteration verwandeln kann, und es auch "triviale" und "unsinninge" Rekursionen gibt, kann man das ja kaum für eine echte Klassifikation verwenden... :bahnhof:

 

[Mr.Käse]

Danke für die Antwort auf die erste Frage, aber die zwiete wurde meiner Meinung nach immer noch nicht richtig beantwortet. Ich weiß, dass Bäume, Graphen, Listen, Schlangen, Stapel rekursive Datenstrukturen sind, möchte aber wissen, was sie als solche klassifiziert. Sind alle Datenstrukturen, die ein Referenz-Attribut auf ein Objekt der gleichen Klasse besitzen eine rekursive Datenstruktur?