Ma’lumotlar tuzilmasi (data structures) — bu ma’lumotlarni samarali öqiş va özgartiriş imkonini beruvçi, ma’lumotlarni saqlaş va boşqarişning bir formatga solingan şaklidir. Eng sodda ma’lumotlar tuzilmasiga misol qilib massiv (array)ni körsatişimiz mumkin. (Manba)

Data structures primitiv va non-primitiv turga ajratiladi.

• Primitiv turga Integer, Boolean, Text, Character kiradi.
• Non-primitiv turning özi ikkiga bölinadi:
• Çiziqli: Array, Linked List, Stack, Queues
• Çiziqsiz: Trees, Graphs.

Dasturçi sifatida primitiv turdagi data structures haqida bilasiz deb hisoblab, non-primitivlari bilan tanişib çiqamiz.

Array

Array bu ma'lumotlar jamlanmasi bölib, dasturlaş tillariga köra bir xil tipdagi yoki har xil tipli; ölçami oldindan aniqlangan yoki aniqlanmagan böladi. Array elementlari xotirada ketma-ket joylaşgani uçun uni öqib oliş tez amalga oşadi.

Eslatma: Biz misollarni Javascript ES6 da körib çiqqanimiz uçun boşqa tillar haqida qayğurmaymiz.

Array'da bajariladigan amallar

const arr = [4,6,1,8,3,0,3,7,3,14,9]

Element öqib oliş (Get). O(1) vaqtda

Agar array indeksini bilsak, demak biz elementni darhol öqiy olamiz. Masalan 6 sonini oliş uçun arr[1] ni işlatiş kifoya.

Element qöşiş (Insert). O(n) vaqtda

Array boşiga qöşiş - unshift
Array boşiga qöşiş uçun, barça elementlar bitta keyingi indekslarga surib çiqadi va 0 indeksga yangi elementni kiritadi.

Array ohiriga qöşiş - push
Arrayning ohirgi elementiga keladi va indeksni bittaga oşirib yangi elementni kiritadi.

Element öçiriş (Remove). O(n) vaqtda

Array boşidan öçiriş - shift
Arrayning 0 indeksini böşatib, keyingi indeksdagi elementlarni bitta oldingi indeksga surib çiqadi.

Array ohiridan öçiriş - pop
Arrayning ohirgi indeksini öçiradi

Elementni özgartiriş (Update). O(1) vaqtda

Bunda indeks ma'lum bölgani uçun şunçaki indeksdagi elementni yangisiga özgartiradi.

Elementlarni körib çiqiş (Traverse). O(n) vaqtda

Sikl içida array elementlari körib çiqiladi.

Linked list

Linked list — bu tugunlardan ya'ni Node'lardan iborat çiziqli tuzilma bölib, har bir node özida elementni va keyingi (ba’zan oldingi ham) node adresini körsatuvçi körsatkiçni (pointerni) saqlaydi.

Linked list strukturasi

Dastlabki Node head deb ataladi. Head'dan keyingi node'lar özidan oldingi node'ning pointeri'ga boğlangan böladi. Demak biz dastlabki node, ya'ni head'ni bilgan holda, pointerlar yordamida keyingi node'larga ötib kerakli elementni topamiz. Array'da index nomerini bilib, darhol arr[index] bilan elementni öqib olgan bölsak, Linked listda öşa elementga boriş uçun ungaça bölgan barça elementlardan ötib keliş kerak.

Hayotiy misolda, array - mehmonxona koridori. Xona nomerini bilgan holda darhol xonani topasiz. Linked List uy içidagi mehmon kutadigan xona. U xonaga kiriş uçun oldin uy içiga kiriş, ayvonga, dahlizga ötiş kerak.

Linked list'ning ikki körinişi bor:

• Unidirectional - Ohirgi elementdan taşqari har bir node'da faqat keyingi node uçun pointer böladi. Ya'ni bir taraflama boğlangan böladi.
• Bidirectional (yoki doubly linked list) - Boşi va ohirgi elementdan taşqari har bir node'da özidan oldingi va özidan keyingi node uçun pointer böladi. Ikki taraflama boğlangan böladi.

Linked list ustida bajariladigan asosiy amallar

Röyhat boşiga element qöşiş (insertAtHead). O(1) vaqtda

Yangi node qöşilib, uning pointeriga linked list head'i körsatib qöyiladi.

Röyhat oxiriga element qöşiş (insertAtEnd). O(1) vaqtda

Yangi node qöşiladi. Uni linked list ohiriga qöşiş uçun oldin pointer = null bölgan ohirini topib olinadi. Keyin pointer yangi node'ga körsatib qöyiladi

Ma’lum bir elementni öçiriş (Delete). O(1) vaqtda

Buning uçun linked list içidan element topiladi. Agar element örtada bölsa Undan oldingi elementning pointeri undan keyingi elementga ulab qöyiladi. Ohirida bölsa, oldingi elementning pointeri böşatiladi.

Ma’lum bir elementni öqib oliş. Qidiriş (Search). O(n) vaqtda

Elementni qidiriş har doim linked list boşidan boşlanadi.

---

Struktura örtasiga element qöşişda Array va Linked List farqi:

Element qöşişda 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 işlaydigan çiziqli ma'lumot tuzilmasi. Bu degani Stackga qöşiladigan ohirgi element Stackning boşiga tuşadi. Öçiriladigan element ham tuzilmaning boşidan öçiriladi.

Stackni linked listda ham, arrayda ham yasaş mumkin. Element qöşiş O(1) da bölgani uçun linked list qulay, ma'lumotlarni öqib oliş qulayligi uçun esa array varianti yaxşiroq.

Stack ustida ikki amal bajariladi: push (qöşiş) va pop (öçiriş). Şuningdek Stack böşligini ham tekşiriş zarurati bölişi mumkin.

Stackga misollar:

• Kompyuterdagi CTRL+Z funksiyasi
• Stringda berilgan matematik misolni Dijkstra'ning ikki stack algorithmi yordamida yeçiş.

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 işlaydi. Bunda birinçi qöşilgan element, birinçi bölib çiqadi.

Qulayligi uçun Queue'ni arrayda yasagan ma'qul.

Queue amallari ham ikkita:

• enqueue/add/put - arrayning ohiriga yangi element qöşiladi
• dequeue/delete/get - arrayning boşidagi elementni öçiradi. Öçirilgan elementni qaytaradi.

Şuningdek, peek - array boşidagi elementni öçirmasdan ham qaytariş funksiyasi qöşilişi mumkin.

Queue'ga misol - hamma yerda uçraydigan 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 böyiça savollarni Github'dagi Webmaxor / leetcode-solutions repository'da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.