Ako je dátová štruktúra Zoznam implementovaná v pamäti a aké mechanizmy stoja na jejom základe?

V C# je štruktúra dát List<T> implementovaná ako dynamické pole. V pamäti uchováva prvky v súvislom bloku, čo zabezpečuje rýchly prístup podľa indexu.

Hlavné mechanizmy fungovania:

• Dynamické rozšírenie: keď počet prvkov presiahne aktuálnu kapacitu poľa, vytvorí sa nové väčšie pole (zvyčajne dvojnásobné) a všetky prvky sa do neho skopírujú.
• Rýchly prístup podľa indexu: vďaka súvislému uloženiu prvkov je prístup k prvku podľa indexu v konštantnom čase O(1).
• Pridávanie prvkov: ak je miesto, prvok sa jednoducho pridá na koniec; ak nie, dôjde k rozšíreniu poľa.

Príklad:

List<int> numbers = new List<int>();
numbers.Add(1);
numbers.Add(2);
int first = numbers[0]; // Rýchly prístup

Takto List<T> kombinuje pohodlie dynamickej veľkosti s efektívnosťou poľa.