Data structure — ma’lumotni saqlash, tashkil etish va uning ustida amallarni samarali bajarish usulidir. Array, linked list, stack, queue, hash table, tree va graph turli access, update, tartib va xotira talablarini beradi. To‘g‘ri tuzilma tanlovi algoritmning vaqt hamda space complexity’siga bevosita ta’sir qiladi.
Abstract data type
Abstract data type qanday amallar mavjudligini va ularning semanticsini belgilaydi, implementatsiya esa ichki saqlashni tanlaydi. Masalan, queue enqueue va dequeueni FIFO tartibida beradi; u circular array yoki linked list bilan qurilishi mumkin.
Interface bilan representationni ajratish implementatsiyani almashtirishga imkon beradi. Biroq complexity contract ham muhim: caller O(1) deb kutgan lookup keyin O(n)ga o‘zgarsa tizim unumdorligi buziladi.
Chiziqli tuzilmalar
Array elementlarni ketma-ket xotirada saqlaydi, indeks bilan tez access va yaxshi cache locality beradi. O‘rtaga insert elementlarni siljitishi mumkin. Dynamic array capacity tugaganda kattaroq blok ajratib elementlarni ko‘chiradi.
Linked list tugunlarni pointer bilan bog‘laydi. Ma’lum tugundan insert tez, lekin indeks bo‘yicha topish chiziqli va pointer overhead katta. Stack LIFO, queue FIFO, deque esa ikki tomondan qo‘shish va olishni taqdim etadi.
Assotsiativ tuzilmalar
Hash table keyni hash orqali bucketga joylashtiradi. Yaxshi taqsimot va load factor ostida lookup expected O(1). Collision chaining yoki open addressing bilan boshqariladi. Hash collision xavfsizlikka ta’sir qilsa randomized seed yoki limit ishlatiladi.
Balanced search tree keylarni tartibli saqlab, lookup, insert va delete’ni O(log n)da beradi. U range query va sorted traversal uchun hash table’dan qulay. Heap faqat minimal yoki maksimal elementni tez olishga mo‘ljallangan priority queue implementatsiyasidir.
Graph va maxsus tuzilmalar
Graph adjacency list yoki matrix bilan saqlanadi. Trie prefiks bo‘yicha qidiruv, union-find komponentlarni birlashtirish, Bloom filter esa element ehtimol mavjudligini kam xotirada tekshirish uchun ishlatiladi. Bloom filter false positive beradi, false negative esa to‘g‘ri implementatsiyada bermaydi.
Domain-specific index — B-tree, LSM-tree, R-tree — storage yoki spatial workloadga mos quriladi. Universal “eng tez” tuzilma yo‘q; access pattern va consistency talabiga qarab tanlanadi.
Xotira modeli
Big O pointer, object header, alignment va allocator metadata constantlarini yashiradi. Millionlab mayda tugun heap fragmentation va cache miss yaratadi. Packed array yoki structure-of-arrays SIMD hamda cache uchun foydali bo‘lishi mumkin.
Persistent data structure update’da eski versiyani saqlab, strukturani bo‘lishadi. Concurrent tuzilma lock, sharding, atomic operation yoki immutable snapshotdan foydalanadi. Memory reclamation noto‘g‘ri bo‘lsa use-after-free yuz beradi.
Tanlash mezoni
Amallar nisbati, maksimal hajm, tartib talabi, duplicate key, concurrency va durability yozib olinadi. Avval sodda to‘g‘ri tuzilma tanlanadi, keyin profiler haqiqiy bottleneckni ko‘rsatganda optimallashtiriladi. Benchmark real key taqsimoti va memory limit bilan bajariladi.
Xotira va lokalitet
Nazariy murakkablik bir xil bo‘lsa ham, amaliy tezlik xotira joylashuviga bog‘liq. Ketma-ket massiv elementlari cache line ichida yaqin turadi va protsessorning oldindan yuklash mexanizmidan foyda oladi. Ko‘rsatkichlar bilan tarqalgan tugunlar esa ko‘proq cache miss keltirishi mumkin. Tuzilmaning metadata, bo‘sh sig‘im va allocation xarajati ham katta hajmda seziladi. Shu sababli tanlov faqat Big O jadvaliga emas, element soni, kirish naqshi va real benchmarkka asoslanadi. Serialization formati va parallel kirish talabi ham ichki tuzilmani belgilashi mumkin.
Bog‘liq tushunchalar
Abstract data type, Array, Hash table, Tree, Graph, Algorithm