Hogyan határozzuk meg a lista index alapján történő elem lekérdezésének időbeli összetettségét?

A lista egy adott indexén történő elemlekérés időbeli komplexitása a lista típusától függ:

• Egy tömb vagy indexelést támogató lista (például a C#-ban a List<T>) esetén az index szerinti hozzáférés O(1) időkomplexitású művelet, mivel az elem közvetlenül a cím alapján elérhető.

• Egy láncolt lista (egysoros vagy kétsoros) esetén az index szerinti hozzáférés O(n) időkomplexitású, mivel az elem eléréséhez végig kell menni a listán a kezdettől (vagy a végétől) a kívánt pozícióig.

A C#-ban a List<T> osztály egy tömbön alapul, így az index szerinti hozzáférés gyors és O(1) komplexitású.