|
Linked list ustida bajariladigan asosiy amallar
|
bet | 7/8 | Sana | 02.04.2023 | Hajmi | 467.22 Kb. | | #48202 |
Bog'liq Agile Kanban, 3-MAVZU TOPSHIRIQLAR-HSM-FALSAFA (1), 9 variant, 2022-05-05 175802, annostatsiya, E K-68, EK-68, Hakimov Sirojiddin, Ish yuritish tili va uslubi, Madaniyat” tushunchasi, uning mohiyati, strukturasi va funksiyal, Korrupsiyaga qarshi kurashda jamoatchilik nazoratining roli ., kichik mablagʻ evaziga tovuq fermasini tashkil etish (2), Annabayev Rustam Tezis, 3(1)
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.
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.
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 😉
|
| |