Ma’lumotlar tuzilmasi (data structures) — bu ma’lumotlarni samarali o’qish va o’zgartirish imkonini beruvchi, ma’lumotlarni saqlash va boshqarishning bir formatga solingan shaklidir. Eng sodda ma’lumotlar tuzilmasiga misol qilib massiv (array)ni ko’rsatishimiz mumkin. (Manba)
Data structures primitiv va non-primitiv turga ajratiladi.
- Primitiv turga Integer, Boolean, Text, Character kiradi.
- Non-primitiv turning o’zi ikkiga bo’linadi:
– Chiziqli: Array, Linked List, Stack, Queues
– Chiziqsiz: Trees, Graphs.
Dasturchi sifatida primitiv turdagi data structures haqida bilasiz deb hisoblab, non-primitivlari bilan tanishib chiqamiz.
Array
Array bu ma’lumotlar jamlanmasi bo’lib, dasturlash tillariga ko’ra bir xil tipdagi yoki har xil tipli; o’lchami oldindan aniqlangan yoki aniqlanmagan bo’ladi. Array elementlari xotirada ketma-ket joylashgani uchun uni o’qib olish tez amalga oshadi.
Eslatma: Biz misollarni Javascript ES6 da ko’rib chiqqanimiz uchun boshqa tillar haqida qayg’urmaymiz.
Array’da bajariladigan amallar
const arr = [4,6,1,8,3,0,3,7,3,14,9]
Element o’qib olish (Get). O(1) vaqtda
Agar array indeksini bilsak, demak biz elementni darhol o’qiy olamiz. Masalan 6 sonini olish uchun arr[1] ni ishlatish kifoya.
Element qo’shish (Insert). O(n) vaqtda
Array boshiga qo’shish – unshift
Array boshiga qo’shish uchun, barcha elementlar bitta keyingi indekslarga surib chiqadi va 0 indeksga yangi elementni kiritadi.
Array ohiriga qo’shish – push
Arrayning ohirgi elementiga keladi va indeksni bittaga oshirib yangi elementni kiritadi.
Element o’chirish (Remove). O(n) vaqtda
Array boshidan o’chirish – shift
Arrayning 0 indeksini bo’shatib, keyingi indeksdagi elementlarni bitta oldingi indeksga surib chiqadi.
Array ohiridan o’chirish – pop
Arrayning ohirgi indeksini o’chiradi
Elementni o’zgartirish (Update). O(1) vaqtda
Bunda indeks ma’lum bo’lgani uchun shunchaki indeksdagi elementni yangisiga o’zgartiradi.
Elementlarni ko’rib chiqish (Traverse). O(n) vaqtda
Sikl ichida array elementlari ko’rib chiqiladi.
Linked list
Linked list — bu tugunlardan ya’ni Node’lardan iborat chiziqli tuzilma bo’lib, har bir node o’zida elementni va keyingi (ba’zan oldingi ham) node adresini ko’rsatuvchi ko’rsatkichni (pointerni) saqlaydi.
Dastlabki Node head deb ataladi. Head’dan keyingi node’lar o’zidan oldingi node’ning pointeri’ga bog’langan bo’ladi. Demak biz dastlabki node, ya’ni head’ni bilgan holda, pointerlar yordamida keyingi node’larga o’tib kerakli elementni topamiz. Array’da index nomerini bilib, darhol arr[index] bilan elementni o’qib olgan bo’lsak, Linked listda o’sha elementga borish uchun ungacha bo’lgan barcha elementlardan o’tib kelish kerak.
Hayotiy misolda, array – mehmonxona koridori. Xona nomerini bilgan holda darhol xonani topasiz. Linked List uy ichidagi mehmon kutadigan xona. U xonaga kirish uchun oldin uy ichiga kirish, ayvonga, dahlizga o’tish kerak.
Linked list’ning ikki ko’rinishi bor:
- Unidirectional – Ohirgi elementdan tashqari har bir node’da faqat keyingi node uchun pointer bo’ladi. Ya’ni bir taraflama bog’langan bo’ladi.
- Bidirectional (yoki doubly linked list) – Boshi va ohirgi elementdan tashqari har bir node’da o’zidan oldingi va o’zidan keyingi node uchun pointer bo’ladi. Ikki taraflama bog’langan bo’ladi.
Linked list ustida bajariladigan asosiy amallar
Ro’yhat boshiga element qo’shish (insertAtHead). O(1) vaqtda
Yangi node qo’shilib, uning pointeriga linked list head’i ko’rsatib qo’yiladi.
Ro’yhat oxiriga element qo’shish (insertAtEnd). O(1) vaqtda
Yangi node qo’shiladi. Uni linked list ohiriga qo’shish uchun oldin pointer = null bo’lgan ohirini topib olinadi. Keyin pointer yangi node’ga ko’rsatib qo’yiladi
Ma’lum bir elementni o’chirish (Delete). O(1) vaqtda
Buning uchun linked list ichidan element topiladi. Agar element o’rtada bo’lsa Undan oldingi elementning pointeri undan keyingi elementga ulab qo’yiladi. Ohirida bo’lsa, oldingi elementning pointeri bo’shatiladi.
Ma’lum bir elementni o’qib olish. Qidirish (Search). O(n) vaqtda
Elementni qidirish har doim linked list boshidan boshlanadi.
* * *
Struktura o’rtasiga element qo’shishda Array va Linked List farqi:
Javascriptda Linked List API
https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/linked-list/linked-list.js
Stack
Stack last in-first out prinsipida ishlaydigan chiziqli ma’lumot tuzilmasi. Bu degani Stackga qo’shiladigan ohirgi element Stackning boshiga tushadi. O’chiriladigan element ham tuzilmaning boshidan o’chiriladi.
Stackni linked listda ham, arrayda ham yasash mumkin. Element qo’shish O(1) da bo’lgani uchun linked list qulay, ma’lumotlarni o’qib olish qulayligi uchun esa array varianti yaxshiroq.
Stack ustida ikki amal bajariladi: push (qo’shish) va pop (o’chirish). Shuningdek Stack bo’shligini ham tekshirish zarurati bo’lishi mumkin.
Stackga misollar:
- Kompyuterdagi CTRL+Z funksiyasi
- Stringda berilgan matematik misolni Dijkstra’ning ikki stack algorithmi yordamida yechish.
Javascriptda Stack API
Arrayda realizatsiya: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/stack/stack-w-array.js
Linked Listda realizatsiya: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/stack/stack-w-linked-list.js
Queue
Queue esa first in-first out prinsipida ishlaydi. Bunda birinchi qo’shilgan element, birinchi bo’lib chiqadi.
Qulayligi uchun Queue’ni arrayda yasagan ma’qul.
Queue amallari ham ikkita:
- enqueue/add/put – arrayning ohiriga yangi element qo’shiladi
- dequeue/delete/get – arrayning boshidagi elementni o’chiradi. O’chirilgan elementni qaytaradi.
Shuningdek, peek – array boshidagi elementni o’chirmasdan ham qaytarish funksiyasi qo’shilishi mumkin.
Queue’ga misol – hamma yerda uchraydigan navbatlar 😉
Javascriptda Queue API
Arrayda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/queues/queue-w-array.js
Linked Listda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/queues/queue-w-linked-list.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.