Kako je struktura podataka Lista implementirana u memoriji i koji mehanizmi stoje u osnovi njenog rada?

U C#-u, struktura podataka List<T> implementirana je kao dinamički niz. U memoriji, ona čuva elemente u kontinuiranom bloku, što omogućava brz pristup putem indeksa.

Glavni mehanizmi rada:

• Dinamičko proširenje: kada broj elemenata premaši trenutnu kapacitet niza, kreira se novi veći niz (obično duplo veći), i svi elementi se kopiraju u njega.
• Brz pristup putem indeksa: zahvaljujući kontinuiranom skladištenju elemenata, pristup elementu putem indeksa vrši se u konstantnom vremenu O(1).
• Dodavanje elemenata: ako ima mesta, element se jednostavno dodaje na kraj; ako nema, dolazi do proširenja niza.

Primer:

List<int> numbers = new List<int>();
numbers.Add(1);
numbers.Add(2);
int first = numbers[0]; // Brz pristup

Na ovaj način, List<T> kombinuje pogodnost dinamičke veličine sa efikasnošću niza.