3.3-bob: Linked List (bog'langan ro'yxat)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 3-mavzu

1. Kirish va motivatsiya

Massiv 3.2-bob — xotirada ketma-ket joylashgan: indeks O(1) tez, lekin o'rtaga qo'shish/o'chirish O(n) sekin (qolganlarni surish kerak). Linked List (bog'langan ro'yxat) — butunlay boshqa yondashuv: elementlar xotirada tarqoq yashaydi, lekin har biri keyingisiga "ko'rsatkich" (pointer) orqali bog'langan.

Bu — birinchi ko'rsatkichli ma'lumotlar tuzilmasi va keyingi murakkab tuzilmalar (tree — 3.6, graph — 3.7) ning poydevori. Linked List'ni tushunish — ma'lumot xotirada qanday "bog'lanishi"ni tushunish demak.

O'xshatish: massiv — kinoteatr qatori (o'rindiqlar yonma-yon, raqamlangan; 5-o'rindiqni darrov topasiz, lekin o'rtaga yangi o'rindiq qo'yish uchun hammasini surish kerak). Linked List — xazina qidiruvi: har bir xat keyingi xat qayerdaligini aytadi. Xatlar uyning turli joyida, lekin zanjir bilan bog'langan. Yangi xat qo'shish oson (faqat ko'rsatkichni o'zgartir), lekin 5-xatga yetish uchun 1-dan boshlab yurish kerak.

Nega o'rganamiz?

• Ko'rsatkich (pointer) tushunchasi — tree, graph, va past darajali dasturlashning asosi.
• Bosh/ma'lum joyga qo'shish/o'chirish O(1) — massivdan tez.
• Intervyularda klassik (ag'darish, sikl topish, o'rtani topish).
• Stack/Queue 3.4-bob, va boshqa tuzilmalar uning ustiga quriladi.

2. Nazariya — chuqur tushuntirish

2.1. Linked List nima?

Linked List — node (tugun) lar zanjiri. Har node ikki narsadan iborat: qiymat (value) va keyingi node'ga ko'rsatkich (next):

  head
   │
   ▼
  ┌────┬───┐   ┌────┬───┐   ┌────┬───┐
  │ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │null│
  └────┴───┘   └────┴───┘   └────┴───┘
  node1         node2         node3 (oxiri: next=null)

• Node — { value, next } (qiymat + keyingiga havola).
• head — birinchi node (ro'yxatning "boshi"). Faqat shunga ishora saqlaymiz.
• Oxirgi node — next = null (zanjir tugadi).

2.2. Massiv vs Linked List (3.1 jadvali)

* amortized; ** tail ko'rsatkichi bo'lsa.

Asosiy savdo: Array — tez murojaat, sekin o'rta o'zgartirish. Linked List — tez bosh o'zgartirish, sekin murojaat. To'g'ri tanlov vazifaga bog'liq 3.1-bob.

Jadval ko'rsatmaydigan yana bir farq — xotira lokalligi (cache locality, 0.1). Array elementlari xotirada yonma-yon yotadi, shuning uchun protsessor ularni "kesh"ga (cache) bir blok bo'lib oldindan oladi — ketma-ket o'qishda juda tez. Linked List node'lari esa xotirada tarqoq (har biri turli joyda), har next bo'yicha sakrash yangi xotira blokini kutadi (cache miss). Natijada bir xil O(n) yurishda ham Array amalda Linked List'dan ko'p marta tez bo'ladi — Big-O bir xil, lekin doimiy koeffitsiyent (constant factor) farqli. Shuning uchun zamonaviy amaliyotda ketma-ket ishlov uchun ko'pincha Array afzal ko'riladi.

2.3. Node va Linked List class (2.10)

class Node {
  constructor(value) {
    this.value = value;   // saqlanadigan qiymat
    this.next = null;     // keyingi node'ga ko'rsatkich (boshda yo'q)
  }
}

class LinkedList {
  constructor() {
    this.head = null;     // bo'sh ro'yxat — head yo'q
    this.size = 0;
  }
}

2.4. Boshga qo'shish (prepend) — O(1)

Eng tez amal — yangi node'ni boshga ulash:

  Oldin:  head  [20]  [30]
  Qo'sh:  [10] yarat, next = head, head = [10]
  Keyin:  head  [10]  [20]  [30]

prepend(value) {
  const node = new Node(value);
  node.next = this.head;   // yangi node eski boshga ishora qiladi
  this.head = node;        // head endi yangi node
  this.size++;
}
// O(1) — surish yo'q, faqat ko'rsatkich (2.2)

2.5. Oxirga qo'shish (append) va o'rtaga qo'shish

Oxirga qo'shish — oxirgacha yurish kerak (tail ko'rsatkichisiz O(n)):

append(value) {
  const node = new Node(value);
  if (!this.head) { this.head = node; this.size++; return; }
  let joriy = this.head;
  while (joriy.next) joriy = joriy.next;   // oxirigacha yur (O(n))
  joriy.next = node;
  this.size++;
}

2.6. O'chirish

Node'ni o'chirish — oldingi node'ning nextini o'chiriladigandan keyingisiga ulash:

  Oldin:  [10]  [20]  [30]
  20 ni o'chir: [10].next = [30] (20 "chetlab o'tiladi")
  Keyin:  [10]  [30]   ([20] endi hech kim ko'rmaydi  garbage collect, 0.1)

remove(value) {
  if (!this.head) return;
  if (this.head.value === value) {   // bosh o'chirilsa — O(1)
    this.head = this.head.next;
    this.size--;
    return;
  }
  let joriy = this.head;
  while (joriy.next && joriy.next.value !== value) joriy = joriy.next;
  if (joriy.next) {                   // topildi — chetlab o't
    joriy.next = joriy.next.next;
    this.size--;
  }
}

2.7. Yurish (traversal) va qidiruv — O(n)

Linked List'da indeks yo'q — har doim head'dan boshlab next orqali yuriladi:

// Yurish
print() {
  let joriy = this.head;
  const natija = [];
  while (joriy) { natija.push(joriy.value); joriy = joriy.next; }
  return natija;
}
// Qidiruv — O(n)
has(value) {
  let joriy = this.head;
  while (joriy) { if (joriy.value === value) return true; joriy = joriy.next; }
  return false;
}

2.8. Singly vs Doubly vs Circular

• Singly (bir tomonlama) — har node faqat next (yuqoridagi). Oddiy.
• Doubly (ikki tomonlama) — har node next va prev (orqaga ham yurish; oxirdan o'chirish O(1)).
• Circular (aylanma) — oxirgi node next boshga ishora qiladi (doira).

  Doubly:  null ◀─[10][20][30]─▶ null   (prev va next)
  Circular: [10][20][30]──┐
                ▲───────────┘ (oxiri boshga)

2.9. Klassik algoritmlar: ag'darish va fast/slow ko'rsatkich

Ag'darish (reverse) — ko'rsatkichlar yo'nalishini teskari qilish (intervyu klassikasi):

reverse() {
  let oldingi = null, joriy = this.head;
  while (joriy) {
    const keyingi = joriy.next;   // keyingisini saqla
    joriy.next = oldingi;          // yo'nalishni teskari qil
    oldingi = joriy;               // bir qadam oldinga
    joriy = keyingi;
  }
  this.head = oldingi;             // yangi head — eski oxir
}
// O(n) vaqt, O(1) xotira

Fast/slow ko'rsatkich — o'rtani topish, sikl aniqlash (3.2: ikki ko'rsatkich g'oyasi):

// O'rtani topish — slow 1 qadam, fast 2 qadam; fast oxirga yetganda slow o'rtada
ortani() {
  let slow = this.head, fast = this.head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow?.value;   // O(n), bir o'tishda
}

3. Sintaksis — tez ma'lumotnoma

class Node { constructor(v) { this.value = v; this.next = null; } }
class LinkedList { constructor() { this.head = null; this.size = 0; } }

// Amallar
prepend(v)   // boshga — O(1)
append(v)    // oxirga — O(n) (tail bilan O(1))
remove(v)    // o'chirish — O(n)
has(v)       // qidiruv — O(n)
reverse()    // ag'darish — O(n), O(1) xotira

// Yurish naqshi (har doim head'dan)
let joriy = this.head;
while (joriy) { /* joriy.value */ joriy = joriy.next; }

4. Batafsil kod namunalari

Misol 1 — To'liq Singly Linked List (2.3–2.7)

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

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

  prepend(value) {                    // O(1) (2.4)
    this.head = Object.assign(new Node(value), { next: this.head });
    this.size++;
  }

  append(value) {                     // O(n) (2.5)
    const node = new Node(value);
    if (!this.head) { this.head = node; }
    else {
      let cur = this.head;
      while (cur.next) cur = cur.next;
      cur.next = node;
    }
    this.size++;
  }

  remove(value) {                     // O(n) (2.6)
    if (!this.head) return;
    if (this.head.value === value) { this.head = this.head.next; this.size--; return; }
    let cur = this.head;
    while (cur.next && cur.next.value !== value) cur = cur.next;
    if (cur.next) { cur.next = cur.next.next; this.size--; }
  }

  toArray() {                          // yurish (2.7)
    const r = [];
    let cur = this.head;
    while (cur) { r.push(cur.value); cur = cur.next; }
    return r;
  }
}

const list = new LinkedList();
list.append(10); list.append(20); list.prepend(5);
console.log(list.toArray());   // [5, 10, 20]
list.remove(10);
console.log(list.toArray());   // [5, 20]

Misol 2 — Ag'darish (reverse — 2.9)

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;   // saqla
    cur.next = prev;          // teskari
    prev = cur;               // oldinga
    cur = next;
  }
  return prev;                // yangi head
}
// 102030  natija  302010  (O(n), O(1) xotira)

Misol 3 — Sikl (cycle) aniqlash (Floyd's algorithm — 2.9)

// Linked List'da sikl bormi? (fast/slow — "toshbaqa va quyon")
function siklBormi(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;          // 1 qadam
    fast = fast.next.next;     // 2 qadam
    if (slow === fast) return true;   // uchrashdi  sikl bor
  }
  return false;                // fast oxirga yetdi  sikl yo'q
}
// O(n) vaqt, O(1) xotira — agar sikl bo'lsa, fast slow'ni "quvib yetadi"

Misol 4 — Ikki saralangan ro'yxatni birlashtirish (2.2: ikki ko'rsatkich)

function birlashtir(l1, l2) {
  const dummy = new Node(0);   // "soxta" bosh (kodni soddalashtiradi)
  let tail = dummy;
  while (l1 && l2) {
    if (l1.value <= l2.value) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;        // qolganini ula
  return dummy.next;           // soxta boshdan keyingisi — haqiqiy head
}
// O(n+m) — ikki ko'rsatkich (3.2)

5. To'g'ri va noto'g'ri holatlar

1) headni saqlamasdan yo'qotish

//  head'ni siljitib, ro'yxat boshini yo'qotish
this.head = this.head.next;   // (agar bu noto'g'ri joyda bo'lsa, hammasi yo'qoladi)

//  yurishda vaqtinchalik o'zgaruvchi ishlat (head'ga tegma)
let cur = this.head;
while (cur) { ...; cur = cur.next; }

2) null next'ni tekshirmaslik

//  oxirda cur.next.value  null.value  xato (2.6)
while (cur.next.value !== x) cur = cur.next;

//  avval next borligini tekshir
while (cur.next && cur.next.value !== x) cur = cur.next;

3) Indeks bo'yicha tez murojaat kutish

 Linked List'da arr[5] kabi O(1) murojaat yo'q (2.2)
 Murojaat tez kerak bo'lsa — Array ishlat; bosh o'zgartirish ko'p bo'lsa — Linked List

4) Ag'darishda nextni saqlamaslik

//  next'ni saqlamasdan o'zgartirsang — zanjir uziladi (2.9)
cur.next = prev;   // endi keyingisi yo'qoldi!

//  avval saqla
const next = cur.next; cur.next = prev; ...

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Cannot read properties of null (reading 'next')

Sababi: null node'ga .next (oxirdan o'tib ketish — 2.6). Yechimi: while (cur && cur.next) bilan tekshiring.

Xato 2 — Cheksiz sikl (yurish)

Sababi: cur = cur.next unutilgan yoki circular list 2.8-bob. Yechimi: har iteratsiyada curni surishni tekshiring; circular'da to'xtash sharti.

Xato 3 — Ro'yxat boshi yo'qoldi

Sababi: headning o'zini siljitib yurish (1-holat). Yechimi: yurishda vaqtinchalik cur ishlating.

Xato 4 — Ag'darishda zanjir uzildi

Sababi: nextni saqlamasdan ko'rsatkichni o'zgartirish (2.9, 4-holat). Yechimi: const next = cur.next avval.

Xato 5 — Bo'sh ro'yxat (head = null) chegaraviy holat

Sababi: bo'sh ro'yxatda amal 0.6-bob. Yechimi: boshida if (!this.head) tekshiring.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Big-O 3.1-bob: array vs linked list tanlovi murakkablikka asoslanadi.
• Stack/Queue 3.4-bob: ko'pincha linked list ustiga quriladi (O(1) qo'shish/o'chirish).
• Tree/Graph (3.6, 3.7): node + ko'rsatkich g'oyasi — shu yerdan.
• OOP 2.10-bob: Node/LinkedList — class.
• Ikki ko'rsatkich 3.2-bob: fast/slow — sikl/o'rta topish.
• Xotira 0.1-bob: garbage collection — ko'rsatkichsiz node o'chadi.
• Real: browser history, undo/redo, music playlist (keyingi/oldingi).

8. Eng yaxshi amaliyotlar (best practices)

• Yurishda vaqtinchalik cur ishlating, headga tegmang (1-holat).
• null tekshiruvi — while (cur && cur.next) 2.6-bob.
• Dummy (soxta) node — bosh bilan ishlashni soddalashtiradi (Misol 4).
• Fast/slow ko'rsatkich — o'rta/sikl uchun (2.9, 3.2).
• To'g'ri tanlov: tez murojaat Array; tez bosh o'zgartirish Linked List 2.2-bob.
• Bo'sh ro'yxat chegaraviy holatini boshida tekshiring 0.6-bob.
• Doubly list — orqaga yurish/oxirdan o'chirish kerak bo'lsa 2.8-bob.
• JS'da kunlik ish uchun Array yetadi — Linked List ko'proq tushuncha/intervyu uchun.

9. Amaliy loyiha: "Linked List Kutubxonasi va Algoritmlar"

Linked List'ni to'liq qurib, klassik algoritmlarni qo'llash.

Maqsad

Node/ko'rsatkich tushunchasini, traversal va klassik linked list algoritmlarini (ag'darish, sikl, o'rta) amalda mustahkamlash.

Talablar (requirements)

1. Singly Linked List class: prepend, append, remove, has, toArray, size (Misol 1).
2. reverse() — ko'rsatkichlarni teskari (Misol 2, 2.9).
3. getMiddle() — fast/slow bilan o'rtani topish 2.9-bob.
4. hasCycle() — Floyd algoritmi (Misol 3) (sikl yaratib sinab ko'ring).
5. removeNth(n) — oxirdan n-chi elementni o'chirish (ikki ko'rsatkich — 3.2).
6. merge(otherList) — ikki saralangan ro'yxatni birlashtirish (Misol 4).
7. Chegaraviy holatlar: bo'sh ro'yxat, bitta element, bosh/oxir o'chirish 0.6-bob.
8. Har amal uchun Big-O ni yozing 3.1-bob.
9. (Bonus) Doubly Linked List (prev bilan) yoki toArray ni tsiklsiz rekursiya bilan 3.11-bob.

Maslahatlar (hint)

• Yurishda let cur = this.head; while (cur) { ...; cur = cur.next; }.
• Reverse: prev, cur, next uch o'zgaruvchi (Misol 2).
• O'rta/sikl: slow 1, fast 2 qadam 2.9-bob.
• removeNth: fast'ni n qadam oldinga, keyin ikkalasini birga (oxirga yetganda slow joyida).
• Dummy node bilan bosh holatini soddalashtiring (Misol 4).
• null tekshiruvi har joyda (6-bo'lim).

"Tayyor" mezonlari (acceptance criteria)

• Linked List CRUD amallar ishlaydi.
• reverse to'g'ri (O(1) xotira).
• getMiddle fast/slow bilan.
• hasCycle sikl bor/yo'qni to'g'ri aniqlaydi.
• removeNth oxirdan to'g'ri o'chiradi.
• merge saralangan birlashtiradi.
• Bo'sh/bitta/bosh/oxir chegaraviy holatlar qulamaydi.
• Har amal Big-O bilan izohlangan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda birinchi ko'rsatkichli tuzilmani — Linked Listni o'rgandik:

• Linked List — { value, next } node'lar zanjiri; headdan boshlanadi, oxiri next = null.
• Massivdan farq 3.1-bob: murojaat O(n) (sekin), bosh qo'shish/o'chirish O(1) (tez).
• Amallar: prepend (O(1)), append (O(n)), remove, traversal/qidiruv (O(n)).
• Turlari: singly, doubly (prev), circular.
• Klassik: reverse (ko'rsatkichni teskari), fast/slow (o'rta/sikl — Floyd).
• Best: vaqtinchalik cur, null tekshiruvi, dummy node.

Keyingi bob — 3.4-bob: Stack va Queue. Linked List'ni bildik; endi uning ustiga quriladigan ikki muhim tuzilmani o'rganamiz: Stack (LIFO — oxirgi kirgan birinchi chiqadi; call stack — 2.4, undo) va Queue (FIFO — birinchi kirgan birinchi chiqadi; navbat, task queue — 5.22). Bular cheklangan, lekin nihoyatda foydali tuzilmalar.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — Linked List operatsiyalari murakkabligi
• Universal CS — linked list, Floyd's cycle detection, pointer manipulation
• MDN Web Docs — class, obyekt havolalari (2.8, 2.10)