Laufzeit bei Doppelt verkettete Listen (Vorgäner, Nachfolger bestimmen)

[Frozenlife]

Hallo,
ich habe eine kleine Frage gestellt bekommen, die ich einfach nicht kapiere.

"Warum kann das Nachfolger/Vorgänger bestimmen in einer Doppelt Verketteten Liste länger dauern als O(1)?"

Es beträgt ja immer O(1), da wir ja einen Pointer auf das nächste bzw. vorige Element sowieso gespeichert haben in unserer Liste? Oder gibt es da eine wirkliche Begründung warum es länger als O(1) dauern kann?

mfg

 

[saftmeister]

Wo steht das? Bei der einfach verketten Liste ist es aufwendig, den Vorgänger zu finden.

 

[Frozenlife]

Ja, also unser Informatik Prof hats mal erwähnt wo ich nicht dabei war. Aber wir glauben jetzt zumindest, dass er nicht das meint, was wir meinen (also das mit Nachfolger/Vorgänger) bestimmen, sonderen iwie anders, aber nur wie ?

Naja, es kann ja auch nichts damit zu tun habn das die Objekte fragmentiert im Speicher liegen und der Speicher erst sequentiell durchsucht werden muss, oder? Also das schließe ich mal sicherlich aus, aber ich weiß nicht..,?

mfg

 

[deepthroat]

Hi.

Ja, also unser Informatik Prof hats mal erwähnt wo ich nicht dabei war. Aber wir glauben jetzt zumindest, dass er nicht das meint, was wir meinen (also das mit Nachfolger/Vorgänger) bestimmen, sonderen iwie anders, aber nur wie ?

Fragt doch einfach mal nach. Evtl. weiß er ja noch wovon er da gesprochen hat...

Naja, es kann ja auch nichts damit zu tun habn das die Objekte fragmentiert im Speicher liegen und der Speicher erst sequentiell durchsucht werden muss, oder? Also das schließe ich mal sicherlich aus, aber ich weiß nicht..,?

Üblicherweise abstrahiert man bei Laufzeitbetrachtungen von Algorithmen von bestimmten Hardware- oder Betriebssystemspezifika.

Gruß

 

[FrankBooth]

Wo steht das? Bei der einfach verketten Liste ist es aufwendig, den Vorgänger zu finden.

Es ging aber ja um die doppelt verkettete Liste.

Mir ist keine Begründung bekannt, warum die Bestimmung länger als O(1) dauern sollte.