verkettete liste Vorteil head/tail Implementierung

progboon9

Hallo Leute,
Ich frage mich wo genau die Vorteile der Implementierung mit head (markiert listenanfang) und tail (markiert listenende) liegen im vergleich zu der Implementierung mit einem Zeiger auf das erste Element und die markierung des Listenendes durch einen NULL-Zeiger im letzten Listenelement.

Ich glaube ein Vorteil der tail/head Implementierung liegt im anhängen einer weiteren Liste an die ursprüngliche Liste.
Aber ich verstehe nicht so ganz warum dies so ist gibt es außerdem weitere Vorteile ?

gruß progboon9

mgaeckler

Hi,

Für einen FIFO-speicher (oder auch Queue = Warteschlange) brauchst Du sowas.

mfg Martin

progboon9

aber wo genau liegt jetzt der vorteil dieser implementierung mit head und tail gegenüber der anderen?

SeppJ

Ist das denn für dich kein nennenswerter Vorteil, wenn man Operationen durchführen kann, die das Ende der Liste als Ziel haben?

volkard

progboon9 schrieb:

Hallo Leute,
Ich frage mich wo genau die Vorteile der Implementierung mit head (markiert listenanfang) und tail (markiert listenende) liegen im vergleich zu der Implementierung mit einem Zeiger auf das erste Element und die markierung des Listenendes durch einen NULL-Zeiger im letzten Listenelement.

Ich glaube ein Vorteil der tail/head Implementierung liegt im anhängen einer weiteren Liste an die ursprüngliche Liste.
Aber ich verstehe nicht so ganz warum dies so ist gibt es außerdem weitere Vorteile ?

Keine Vorteile durch Head/Tail.

In der Head/Tail-Darstellung schreibt man gerne Funktionen rekursiv

size_t count(ListImp* list){
    if(!list)
        return 0;
    else
        return 1+count(list->tail);
}

und wenn der Compiler diese Rekursionen nicht in Schleifen übersetzt, hat man schnell Probleme.

Der Anwender möchte nicht ListImp* haben, was evtl nullptr sein kann und ->count() nicht kann, sondern dann schon einen Wrapper um den Zeiger. Und dann Gips für Head/Tail gar keine Berechtigung mehr, fürchte ich.

volkard schrieb:

und wenn der Compiler diese Rekursionen nicht in Schleifen übersetzt, hat man schnell Probleme.

Gewisse Grundannahmen über Compileroptimierungen darf man haben. Sonst schreibt man paranoiden Code und ist letztendlich besser bei C aufgehoben.

hustbaer

volkard, ich glaube du hast zu viel Lisp gelutscht.
Nicht head/tail wie in head = erstes Element und tail = Rest der Liste.

Sondern head/tail wie in head = Zeiger auf das erste Element und tail = Zeiger auf das letzte Element (und dazwischen halt ganz normal mit "next" Zeigern verkettet).
Und das macht man logischerweise wenn man ne Liste braucht wo man schnell Zugriff auf das letzte Element benötigt. z.B. weil man schnell hinten anhängen ~~bzw. entfernen~~ können möchte.

volkard

hustbaer schrieb:

volkard, ich glaube du hast zu viel Lisp gelutscht.
Nicht head/tail wie in head = erstes Element und tail = Rest der Liste.
Sondern head/tail wie in head = Zeiger auf das erste Element und tail = Zeiger auf das letzte Element (und dazwischen halt ganz normal mit "next" Zeigern verkettet).

Oh, hätte tail nie mit dieser Bedeutung vermutet.

hustbaer schrieb:

Und das macht man logischerweise wenn man ne Liste braucht wo man schnell Zugriff auf das letzte Element benötigt. z.B. weil man schnell hinten anhängen bzw. entfernen können möchte.

Klar.

volkard

1970coder schrieb:

volkard schrieb:

und wenn der Compiler diese Rekursionen nicht in Schleifen übersetzt, hat man schnell Probleme.

Gewisse Grundannahmen über Compileroptimierungen darf man haben. Sonst schreibt man paranoiden Code und ist letztendlich besser bei C aufgehoben.

Die wären hier: Im Debug-Modus scheppert's.

hustbaer schrieb:

(und dazwischen halt ganz normal mit "next" Zeigern verkettet).

weil man schnell hinten anhängen bzw. entfernen können möchte.

Entfernen geht nicht, dazu bräuchte man eine doppelt verlinkte Liste.

progboon9

alles klar danke euch

also das anhängen einer weiteren liste wird vereinfacht

hustbaer

ENTF schrieb:

hustbaer schrieb:

(und dazwischen halt ganz normal mit "next" Zeigern verkettet).

weil man schnell hinten anhängen bzw. entfernen können möchte.

Entfernen geht nicht, dazu bräuchte man eine doppelt verlinkte Liste.

Upps. Habs korrigiert. Danke.