Das deutsche Python-Forum

Hallo,
was ist gemeint mit:

Eine verkettete Liste wird als rekursive Datenstruktur betrachtet, weil sie rekursiv definiert ist. Quelle

Was ist an einer verketten Liste denn rekursiv?
Also rekursiv ist für mich etwas, wenn es durch sich selbst definiert ist, aber in welcher weißer ist das bei dieser Art Listen der Fall?

Danke für die Antwort im voraus.
Gruß
Dr.Miles[/url]

'ne verkettete Liste definiert sich doch in sich selbst! Jedes Element enthält einen Verweis auf einen Element des selben Types.

Also eine verkette Liste sieht für mich so aus:

|---Knoten--|
|inhalt |
|verweis |
|-------------|

|---Knoten--|
|inhalt |
|verweis |
|-------------|

|---Knoten--|
|inhalt |
|verweis |
|-------------|

oder:

|---Knoten--|
|inhalt |
|verweis |
|-------------|

oder:

[None] (Also eine leere Liste)

Wenn sich diese Liste dann durch sich selbst definiert, dann hat sie doch jedesmal eine andere Definition?!

Edit: Ist mit rekursive Datenstruktur gemeint, das die Struktur die die Liste hat sich durch sich selbst (also rekursiv) definiert?
Edit2: Also dieser Satz in anderen Worten:

Eine verkettete Liste besitzt eine rekursive Datenstruktur , weil die Struktur dieser Listenart sich aus der Anzahl der vorhandenen Elemente ergibt

Ein Knoten enthält einen Verweis auf einen Knoten, also auf den gleichen Typ, von dem er selbst ist. Das ist die Rekursion.

BlackJack hat geschrieben:Ein Knoten enthält einen Verweis auf einen Knoten, also auf den gleichen Typ, von dem er selbst ist. Das ist die Rekursion.

Also ist der Knoten rekursiv definiert?
Und weil der Knoten aus einem anderen Knoten besteht ist er selbst rekursiv definiert?

Aber definiert wird der Knoten doch hier:

Code: Alles auswählen

class Knoten:
	def __init__(self, inhalt=None, naechster=None):
		self.inhalt = inhalt
		self.naechster  = naechster
	def __str__(self):
		return str(self.inhalt)

Also wird doch nur ein Verweis auf eine Instanz des Knotens in der Knoteninstanz gespeichert.

Ich glaube ich weiß was du meinst, das
Knoten= inhalt , naechsterknoten(der vom Typ Knoten ist) ist
Also zur Laufzeit der Liste kann ich da etwas erkennen was mich vom Muster her ein wenig an Rekursion erinnert, aber nur mit Gewalt.

Edit: Also ist diese Rekursion bei einem Endknoten nicht mehr gegeben? Weil dort zeigt knoten.naechster ja auf None.

PS: Ich glaub ich habs:
Die bei einer vL bestehnd aus 3 Knoten ist die Definition von Knoten 1:
.inhalt
.naechster = knoten2 (was knoten 3 mit einschließt)
Also ist die Definition von Knoten 1 = nutzdaten + alle anderen knoten (indirekt über .naechster der jeweilig folgenden Knoten)

Man sieht die Rekursivität sehr schön z.B. an der Definition in Haskell:

Code: Alles auswählen

data LinkedList a = Nil | Cons a (LinkedList a)

Die LinkedList taucht also in ihrer eigenen Typdefinition auf.

Ähnliches gilt z.B. für Bäume, wo das etwa so aussehen kann:

Code: Alles auswählen

data SomeTree a  = Leaf a | Node (SomeTree a) (SomeTree a)

@Dr.Miles: Man sieht das Python nicht so gut, weil man bei der Definition keine Typen für die Attribute angeben muss. Bei statisch typisierten Programmiersprachen wird das deutlicher, wie in dem Haskell-Beispiel von birkenfeld.

Hier so etwas in C#:

Code: Alles auswählen

class Node<T>
{
    T data;
    Node<T> next;
    
    // Methoden...
}

Innerhalb der Definition des Typs `Node<T>` wird der Typ selbst verwendet.

In Prosa: Eine Liste ist entweder leer oder es ist ein Element plus eine Liste.

Das ist offensichtlich rekursiv.

Stefan

Also ich habe mir einmal die Arbeit gemacht und den Abschnitt 17.1 neu geschrieben wie ich es formuliert hätte:

17.1 Eingeschlossene Verweise

Wir haben Beispiele gesehen, bei denen Objekte in Attributen gespeichert wurden. So etwas nennt man einen eingeschlossenen Verweis.
Eine sog. verkette Liste nutzt diese Möglichkeit.

Verkettete Listen bestehen aus Knoten, wobei jeder Knoten einen Verweis zum nächsten Knoten der Liste enthält. (Es sei denn es ist der "Endknoten")
Weiterhin enthält jeder Knoten eine bestimmte Menge Nutzdaten, die den (für den Gebrauch nützlichen) Inhalt dieses Knotens darstellen.

Eine verkettete Liste besitzt eine rekursive Datenstruktur, d.h. das sich die Struktur der verketten Liste aus der Anzahl
der vorhandenen Knoten zusammensetzt. (A)

Eine verkette Liste >ist< ein oder mehrere Knoten(*1). Ein Knoten enthält zwei Attribute, einem Attribut das die Nutzdaten enthält
und einem, welches den nächsten Knoten beinhaltet. Falls es keinen nächsten Knoten gibt (also am Ende der verketten Liste), wird dem Attribut,
welches den nächsten Knoten enthalten sollte None zugewiesen. Das None kennzeichnet das Ende der verketten Liste.

Eine verkette Liste ohne einem einzigen Element wird mit None dargestellt. (Die Bedeutung von None ist nur in diesem Kontext "leere verkette Liste"
None an sich ist ein Objekt, welches einfach gesagt nichts repräsentiert.)

Die folgende Abbildung stellt eine verkette Liste visuell dar:

Bild

*1 In anderen Worten: Der erste Knoten ist die verkette Liste, da in ihm alle anderen Knoten definiert sind, was Abb.1 deutlich zeigt.

Ist das soweit alles richtig?

Klingt gut.

Streng genommen müssen es nicht explizite Knoten sein. Wenn man (in früheren Zeiten) ein bisschen Speicherplatz sparen wollte, verschmilzt man Nutzdaten und Verweis zu einem Objekt, z.B.

Code: Alles auswählen

class Process: # pseudocode, um Typen klar zu machen
    pid = int
    name = str
    next = Process

Stefan

Das deutsche Python-Forum

Wieso ist eine verkette Liste eine rekursive Datenstruktur?

Wieso ist eine verkette Liste eine rekursive Datenstruktur?