Bog‘langan ro‘yxat va massiv: farqi va qaysi birini tanlash

Qisqa javob

Odatiy holatda massivni oling (dinamik massiv: Python da list, JavaScript da Array). U indeks bo‘yicha tez kirish, tez aylanib chiqish va ixcham xotira beradi.

Bog‘langan ro‘yxatni (linked list) faqat asosiy amal havolasi sizda allaqachon bor joyga element qo‘shish yoki o‘chirish bo‘lsa va ixtiyoriy kirish kam kerak bo‘lsa tanlang.

Xotirada qanday joylashadi

• Massiv — xotiradagi bitta uzluksiz blok. i elementi start + i * size manzilida joylashadi, manzil bir zumda hisoblanadi.
• Bog‘langan ro‘yxat — xotira bo‘ylab tarqalgan alohida tugunlar (node). Har bir tugun qiymat va keyingi tugunga ko‘rsatkichni saqlaydi (ikki tomonlama ro‘yxatda oldingisiga ham). i elementiga yetish uchun boshidan i ta ko‘rsatkich bo‘ylab yurish kerak.

Dinamik massiv zaxira sig‘imni ushlab turadi. Joy tugaganda kattaroq blok ajratadi va hamma narsani unga ko‘chiradi. Bu kamdan-kam bo‘ladi, shuning uchun oxiriga qo‘shish amortizatsiyalangan O(1).

Big O bo‘yicha taqqoslash

Asosiy nuqta: ro‘yxatdagi O(1) tugun sizda allaqachon bor deb faraz qiladi. Agar uni avval indeks yoki qiymat bo‘yicha topish kerak bo‘lsa, yurish O(n) turadi va ustunlik yo‘qoladi.

Kesh lokalligi: nega amalda massiv yutadi

Protsessor xotirani bo‘laklab — kesh qatorlari bilan yuklaydi. Massiv elementini o‘qiganingizda qo‘shnilari ham birga keladi va keyingi o‘qishlar juda tez bo‘ladi. Apparat prefetcher ham ketma-ket kirishni yaxshi taxmin qiladi.

Ro‘yxat tugunlari tarqalgan, shuning uchun har bir qadam keshdan o‘tib ketib, asosiy xotirani kutishi mumkin. Shu sababli bir xil Big O ga ega amallar, masalan barcha elementlarni aylanib chiqish, massivda ko‘pincha sezilarli tezroq ishlaydi. Kichik va o‘rta to‘plamlarda massiv elementlarini surish ko‘pincha ko‘rsatkichlar bo‘ylab yurishdan arzonroq.

Ikkalasi kodda

Python va JavaScript dagi massivlar tayyor dinamik massivlardir:

nums = [10, 20, 30]
nums.append(40)      # amortizatsiyalangan O(1)
nums.insert(0, 5)    # O(n): barcha elementlar o‘ngga suriladi
print(nums[2])       # O(1)

JavaScript da minimal bir tomonlama ro‘yxat:

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor() { this.head = null; }

  prepend(value) {            // O(1)
    this.head = new Node(value, this.head);
  }

  insertAfter(node, value) {  // tugun qo‘lda bo‘lsa O(1)
    node.next = new Node(value, node.next);
  }

  *[Symbol.iterator]() {
    for (let n = this.head; n; n = n.next) yield n.value;
  }
}

const list = new LinkedList();
list.prepend(3);
list.prepend(1);
list.insertAfter(list.head, 2);
console.log([...list]); // [1, 2, 3]

Bog‘langan ro‘yxat haqiqatan yutadigan holatlar

• LRU kesh. Xesh-jadval ikki tomonlama ro‘yxat tugunlariga ishora qiladi. Har murojaatda tugun O(1) da boshiga o‘tkaziladi, eng eskisi dumdan O(1) da o‘chiriladi.
• Ikkala uchidan tez-tez qo‘shiladigan navbat va deklar. Python dagi collections.deque aynan shu sababli bog‘langan bloklardan qurilgan. Oddiy massiv boshidan o‘chirish — O(n).
• Bo‘laklarni ko‘chirish. Butun elementlar zanjirini boshqa ro‘yxatga o‘tkazish — nusxalashsiz, bir necha ko‘rsatkichni o‘zgartirish.
• Barqaror havolalar. Tugunlar xotirada ko‘chmaydi, ularga ko‘rsatkichlar yaroqli qoladi. Dinamik massiv o‘sganda boshqa joyga ko‘chadi.
• Xotira ajratuvchilar va OT yadrolaridagi bo‘sh bloklar ro‘yxati, bu yerda tugunlar obyektlarning o‘ziga joylashtirilgan.

Ko‘p uchraydigan xatolar

• Ro‘yxatni «qo‘shish O(1)» deb tanlab, keyin indeks bo‘yicha qo‘shish — bu baribir O(n).
• Katta ma’lumotlarda array.shift() yoki list.pop(0) ni navbat sifatida ishlatish — buning uchun deque va navbatlar bor.
• Qo‘shimcha xarajatni unutish: har bir tugun ko‘rsatkichlar va ajratuvchining xizmat ma’lumotlarini olib yuradi.
• Standart kutubxonada mos tuzilma bo‘la turib, o‘z ro‘yxatingizni yozish.