Verkettete Liste

[pixewakb]

Ich lese gerade eine Einführung und die Laufzeiten von Array mit verketteter Liste werden verglichen:

Lesen:
Array: O(1)
Listen: O(n)

Einfügen:
Array: O(n)
Listen: O(1)

Warum ist das Einfügen mit einer Laufzeit von O(1) möglich, ich muss doch erst einmal zum Element kommen und dort die Änderung zum Einfügen vornehmen, aber die Elemente bis zur Einfügestelle muss ich doch erst einmal durch die Liste iterieren?

Kann mir das jemand erklären?

[__blackjack__]

@pixewakb: Die werden wahrscheinlich nur die Einfügeoperation selbst meinen. Also man hat die Stelle wo man einfügen will bereits.

[Sirius3]

Welche Laufzeit wirklich vorliegt, kommt auch ganz auf das Programm an, das man drumrum schreibt.
Der üblich Anwendungsfall, gehe durch alle Elemente der Liste ist mit beiden Implementierungen ein O(n).