Algoritmlаr, ulаrning хоssаlаri

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.

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 😉