Was ist Verkettete Liste (Linked List)?

Antwort: A. Ist das Element direkt vor der Einfügestelle bekannt, lässt sich ein neues Element allein durch Umsetzen von Zeigern einfügen, ohne andere Elemente zu verschieben; um das i-te Element zu lesen, muss die Liste aber von vorn durchlaufen werden

In einer verketteten Liste genügt es zum Einfügen und Löschen an einer bekannten Stelle, die benachbarten Zeiger umzuschreiben; das kostet O(1). Um das i-te Element zu lesen, muss man dagegen von vorn i Zeigern folgen, was O(n) dauert. Ein Array berechnet die Adresse des i-ten Elements aus der Startadresse und der Elementgröße und liest jedes Element in O(1); das Einfügen in der Mitte kostet aber O(n), weil die nachfolgenden Elemente verschoben werden müssen. Da die Elemente eines Arrays zusammenhängend liegen, wirken außerdem Cache und Prefetching gut, während die Knoten einer verketteten Liste oft im Speicher verstreut sind; selbst ein Durchlauf mit gleichem O(n) kann dann deutlich langsamer sein.