Massivlər və dinamik massivlər
Massiv (array) — eyni tipli elementlərin yaddaşda ardıcıl (contiguous) yerləşdiyi struktur. Bu bir cümlə massivin bütün xassələrini izah edir.
Elementlər bitişik olduğu üçün i-ci elementin ünvanı düsturla hesablanır: base + i × elementSize. Heç bir axtarış yoxdur — buna görə indekslə oxumaq və yazmaq O(1)-dir, n nə qədər böyük olsa da.
Ardıcıllığın ikinci, az danışılan üstünlüyü cache lokallığıdır: prosessor yaddaşdan bütöv bir blok (cache line) oxuyur, deməli massivi ardıcıl gəzmək eyni sayda əməliyyatı pointer-lərlə tullanmaqdan xeyli sürətli edir. Real ölçmələrdə fərq 5-10 dəfəyə çata bilər — halbuki hər ikisi O(n)-dir.
| Əməliyyat | Mürəkkəblik | Niyə |
|---|---|---|
| İndekslə oxu/yaz `arr[i]` | O(1) | Ünvan düsturla hesablanır |
| Sona əlavə (`push`) | amortized O(1) | Adətən boş yerə yazır; tutum dolanda böyütmə O(n) |
| Sondan silmə (`pop`) | O(1) | Yalnız uzunluq azalır, sürüşdürmə yoxdur |
| Əvvələ əlavə (`unshift`) | O(n) | Bütün elementlər bir addım sağa sürüşür |
| Ortadan silmə (`splice`) | O(n) | Boşluq qalmasın deyə sağdakılar sola sürüşür |
| Sıralanmamışda axtarış | O(n) | Ən pis halda hər elementə baxmaq lazımdır |
| Sıralanmışda binary search | O(log n) | Hər addımda diapazon yarıya bölünür |
| Sıralama (`sort`) | O(n log n) | Müqayisəyə əsaslanan sıralamanın nəzəri həddi |
Dinamik massiv nə üçün lazımdır. Klassik massivin ölçüsü yaradılan anda təsbit olunur, çünki yaddaşda ardıcıl blok ayrılır və qonşu ünvanlar başqasının ola bilər. JS Array, Kotlin ArrayList, Dart List — hamısı dinamik massivdir: içəridə sabit ölçülü buffer və ondan ayrı length sayğacı saxlayır.
Böyümə mexanizmi:
length == capacityolanda yeni, adətən iki dəfə böyük buffer ayrılır- Bütün elementlər yeni bufferə köçürülür — bu,
O(n) - Köhnə buffer GC üçün sərbəst qalır
Tutum həndəsi silsilə ilə (1, 2, 4, 8, 16...) artdığı üçün n əlavənin ümumi dəyəri O(n), əməliyyat başına isə amortized O(1) olur. Əgər tutum sabit addımla (məsələn, hər dəfə +10) artsaydı, ümumi dəyər O(n²) olardı — müsahibədə bu müqayisəni demək güclü siqnaldır.
Element sayı əvvəlcədən məlumdursa, tutumu qabaqcadan ayırmaq köçürmələri tamamilə aradan qaldırır (new Array(n), ArrayList(n), List.filled(n, 0)).
Massiv nə vaxt səhv seçimdir:
- Əvvəldən və ya ortadan tez-tez əlavə/silmə — hər əməliyyat
O(n)sürüşdürmədir. Növbə davranışı lazımdırsaArrayDeque/circular buffer, ortadan çox silmə varsa linked list düşün. - Açara görə axtarış —
arr.find(u => u.id === id)O(n)-dir. Dövr içində çağırılırsaO(n²)alırsan. Həlli:Map/HashMapiləO(1). - Üzvlük yoxlaması —
arr.includes(x)O(n);SetiləO(1). - Çox seyrək (sparse) data — 1 milyon xanadan 100-ü doludursa, massiv yaddaşı boş yerə tutur;
Mapdaha uyğundur.
Əksinə, massiv demək olar həmişə düzgün seçimdir: ardıcıl gəzinti, indekslə çıxış, sabit ölçülü data, kiçik kolleksiyalar.
İnterview məsləhəti. Ən çox verilən sual: "Massiv ilə linked list arasındakı fərq nədir?" Cavabı ardıcıl yaddaş vs pointer-lər fərqindən başlat, sonra nəticələri sadala: massiv — O(1) indeks, pis daxiletmə; linked list — O(1) daxiletmə (node əlindədirsə), indeks yoxdur. Cache lokallığını qeyd etmək səni əksəriyyətdən ayırır.
İkinci klassik sual: "`push` niyə O(1)-dir, axı massiv böyüyür?" — amortized təhlili ilə cavab ver (iki dəfə böyütmə, həndəsi silsilə).
Ən çox rast gəlinən səhvlər: dövrün içində includes/indexOf/find çağırıb O(n²) yaratmaq və bunu görməmək; splice-ı O(1) sanmaq; dövrün içində massivi dəyişdirib (splice edib) indeksləri sürüşdürmək — bu, klassik "hər ikinci elementi atlayan" buq-dur.
📚 Mənbələr və sənədlər
- Arrayrəsmideveloper.mozilla.org