Ma’lumot tuzilmalari (data structures), Linked List, Stack, Queue

Ma'lumotlar tuzilmasi

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

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.

Linked list ko'rinishi
Linked list strukturasi

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:

Element qo'shishda linked list afzalligi
Element qo’shishda linked list afzalligi.

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.

Stack

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 (keyingi darsda).

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

Do'stlaringiz bilan bo'lishing!