Linked list: tuzilishi va asosiy amallar (head, tail, prepend, append)

Qisqacha: Linked list (bog'langan ro'yxat) — har biri qiymat va keyingi tugunga havola saqlaydigan tugunlar zanjiri. Massivdan farqli, elementlar xotirada yonma-yon turmaydi. Shuning uchun boshiga qo'shish va olib tashlash O(1) — hech narsa surilmaydi. Lekin i-elementga borish uchun boshidan sanab yurish kerak — O(n). tail havolasi oxiriga qo'shishni ham O(1) qiladi.

Bu darsda

• Tugun (ListNode) va ro'yxat (LinkedList) klasslarini o'zingiz yoza olasiz.
• head, tail va next havolalari amallar paytida qanday o'zgarishini chizib bera olasiz.
• Boshiga va oxiriga qo'shish, o'chirish, aylanib chiqish amallarining murakkabligini tushuntira olasiz.
• Linked list va massivni o'lchov bilan solishtirib, qachon qaysi biri yaxshi ekanini aniqlaysiz.

Oldin bilishingiz kerak: Massiv xotirada va joyida amallar, JS o'rnatilgan amallarining narxi, Hash map bilan hisoblash naqshlari, class sintaksisi, Generator funksiyalar.

1. Nega bu kerak?

Sardor oshxona ekrani uchun buyurtmalar navbatini massivda saqladi. Oddiy buyurtma oxiriga qo'shiladi (push). Shoshilinch buyurtma esa boshiga (unshift). Kichik kunlarda hammasi joyida edi. Bayram kuni buyurtmalar o'n minglab bo'ldi va ekran qota boshladi.

Sababni JS o'rnatilgan amallarining narxi darsida ko'rgan edik: unshift hamma elementni bir o'ringa suradi — O(n). Massiv xotirada uzluksiz turadi (Massiv xotirada): boshida bo'sh joy ochish uchun hammani surishdan boshqa yo'l yo'q.

Agar elementlar yonma-yon turmasa-chi? Har buyurtma "mendan keyin falonchi" deb yozib qo'ysa — boshiga qo'shish uchun hech kimni surish shart emas. Yangi buyurtma "mendan keyin — eski birinchi" deb yozadi, tamom. Bu — linked list g'oyasi. Bugun uni noldan quramiz va massiv bilan halol solishtiramiz.

2. Tuzilma: tugunlar va havolalar

2.1 Tugun

Tugun (node) — linked list'ning bitta "bo'g'ini". Unda ikki narsa bor: qiymat (value) va keyingi tugunga havola (next). Oxirgi tugunning next i — null: "mendan keyin hech kim yo'q".

O'xshatish: xazina qidirish o'yini. Har xatda ikki narsa yozilgan: kichik sovg'a va keyingi xat qayerda yashiringanligi. Birinchi xat qayerdaligini bilsangiz — hammasini topasiz. Xatlar uyning turli burchaklarida — yonma-yon emas.

class ListNode {
  constructor(value, next = null) {
    this.value = value; // ma'lumot
    this.next = next; // keyingi tugunga havola (yoki null)
  }
}

const third = new ListNode(30); // manti
const second = new ListNode(28, third); // lag'mon
const first = new ListNode(35, second); // osh

console.log(first.value, first.next.value, first.next.next.value);
console.log(first.next.next.next); // null

Konsolda:

35 28 30
null

first.next.next — "birinchining keyingisining keyingisi". Har .next — zanjirda bitta qadam.

Diqqat: Ko'p kitoblarda klass Node deb ataladi. Brauzerda esa Node — DOM'ning o'rnatilgan klassi (DOM daraxti). Uni qayta e'lon qilish chalkashlik keltiradi. Shuning uchun biz ListNode deymiz.

2.2 head va tail

Zanjirning birinchi tuguniga havola — head (bosh). Butun ro'yxat aslida shu bitta havola: boshqa tugunlarga faqat next lar orqali yetamiz. Oxirgi tugunga havola — tail (dum). U shart emas, lekin oxiriga tez qo'shish uchun juda foydali (keyinroq ko'ramiz).

Massiv bilan farqni bir jadvalda ko'ring:

3. Aylanib chiqish (traversal)

Ro'yxatdagi hamma buyurtmalar summasini hisoblaylik. Indeks yo'q, for (let i…) ishlamaydi. Buning o'rniga current havolasini head dan boshlab, next bo'ylab surib boramiz — null ga yetguncha. Bu aylanib chiqish (traversal) deyiladi:

Strelkalarga qarang: current = current.next — "keyingi xatni ochish". Biz zanjirni o'zgartirmayapmiz, faqat u bo'ylab yuryapmiz. Har tugun bir marta ko'riladi — O(n) vaqt, current va total — O(1) xotira.

E'tibor bering: head ning o'zini surmadik, alohida current ochdik. head = head.next qilsak, sikldan keyin ro'yxat boshini yo'qotardik. Havolasi qolmagan tugunlarni esa axlat yig'uvchi o'chirib yuboradi.

Tekshirib ko'ring: 1 000 ta tugunli ro'yxatda 500-tugunning qiymatini olish uchun nechta .next dan o'tish kerak? Massivda-chi?

4. LinkedList klassi

4.1 Uch amal

Tugunlarni qo'lda ulash noqulay. Ularni bitta klassga yig'amiz: head, tail va size (tugunlar soni). Uchta asosiy amalni qo'shamiz:

• prepend(value) — boshiga qo'shish. Yangi tugun next i — eski head, keyin head — yangi tugun.
• append(value) — oxiriga qo'shish. tail.next yangi tugunga ulanadi, tail suriladi.
• remove(value) — qiymat bo'yicha o'chirish. Oldingi tugunni (prev) topib, uning next ini o'chiriladigan tugundan "aylanib o'tadigan" qilamiz.

Kodni qadamma-qadam kuzating. Grafda har qadamda qaysi havola o'zgarayotganiga qarang:

4.2 Nega prepend va append O(1)?

prepend ikkita havolani o'zgartiradi — ro'yxat uzunligi qancha bo'lmasin. Hech kim surilmaydi: eski tugunlar joyida qoladi, faqat yangi "boshliq" paydo bo'ladi. O(1).

append ham ikkita havola: tail.next va tail. Agar tail bo'lmasa-chi? Unda oxirgi tugunni topish uchun head dan butun zanjir bo'ylab yurish kerak — O(n). Bitta qo'shimcha havola amalni O(n) dan O(1) ga tushirdi. Bu — ma'lumotlar tuzilmasining asosiy hiylasi: kerakli narsani oldindan "qo'l ostida" ushlab turish.

4.3 O'chirish: nega oldingi tugun kerak

Tugunni o'chirish — uni zanjirdan "uzish": oldingi tugun next i o'chiriladigan tugundan keyingisiga ulanadi. prev.next = prev.next.next — butun o'chirish shu bitta qator. O'chirilgan tugunga endi hech kim ishora qilmaydi va u xotiradan tozalanadi.

Muammo — oldingi tugunni topish. Bizning tugunlarda faqat next bor, prev yo'q. Shuning uchun head dan boshlab, "keyingisi kerakli qiymatmi?" deb so'rab yuramiz. Qidiruv — O(n), uzishning o'zi — O(1).

Ikki maxsus holat bor. Birinchisi — o'chiriladigan tugun head: oldingisi yo'q, shunchaki head = head.next. Ikkinchisi — o'chiriladigan tugun tail: tail ni prev ga surish kerak. Aks holda keyingi append o'chirilgan tugunga ulanadi va yangi element zanjirdan yo'qoladi. Vizualdagi 104 aynan shu xavfdan qutuldi.

Endi o'zingiz kuzating. Ro'yxat 103 → 101 → 104. remove(101) dan keyin 103.next qaysi tugunga ishora qiladi? Javob: .

Tekshirib ko'ring: Bitta elementli ro'yxatda remove qilsak, nima uchun tail ham null bo'lishi kerak?

4.4 for…of bilan aylanish

Har safar current siklini yozish noqulay. Klassga generator bilan [Symbol.iterator] qo'shamiz — shunda ro'yxat for…of va spread bilan ishlaydi (Iteratsiya protokoli):

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  append(value) {
    const node = new ListNode(value);
    if (this.tail === null) this.head = node;
    else this.tail.next = node;
    this.tail = node;
    this.size++;
  }
  *[Symbol.iterator]() {
    for (let c = this.head; c !== null; c = c.next) yield c.value;
  }
}

const orders = new LinkedList();
for (const id of [101, 102, 103]) orders.append(id);
console.log([...orders]); // [ 101, 102, 103 ]
console.log(orders.size); // 3

for (let c = this.head; c !== null; c = c.next) — aylanib chiqishning ixcham shakli: boshlanish, shart va qadam bitta qatorda.

4.5 removeFirst: navbatning boshidan olish

Oshxonada eng ko'p bajariladigan amal — navbatdagi birinchi buyurtmani olish. Massivda bu shift — hamma qolganlar bir o'ringa suriladi, O(n). Ro'yxatda esa head bitta qadam oldinga siljiydi:

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  append(value) {
    const node = new ListNode(value);
    if (this.tail === null) this.head = node;
    else this.tail.next = node;
    this.tail = node;
    this.size++;
  }
  removeFirst() {
    if (this.head === null) return undefined; // bo'sh
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null; // oxirgisi ketdi
    this.size--;
    return value;
  }
}

const kitchen = new LinkedList();
kitchen.append(101);
kitchen.append(102);
console.log(kitchen.removeFirst()); // 101
console.log(kitchen.removeFirst()); // 102
console.log(kitchen.removeFirst()); // undefined
console.log(kitchen.size, kitchen.tail); // 0 null

append oxiriga qo'shadi, removeFirst boshidan oladi — ikkalasi O(1). Bu juftlik — haqiqiy navbat (queue): kim birinchi kelgan bo'lsa, o'sha birinchi xizmat oladi. Queue va deque darsida aynan shu g'oyani o'lchab, massivdagi shift bilan solishtiramiz.

Tekshirib ko'ring: removeFirst da if (this.head === null) this.tail = null qatori bo'lmasa, yuqoridagi kodning oxirgi qatori nima chiqaradi?

5. Massiv bilan taqqoslash

5.1 Murakkablik jadvali

Linked list "boshida" va "ma'lum joyda" ishlashda yutadi. Massiv "indeks bilan" ishlashda yutadi. Qidiruv ikkalasida ham O(n).

5.2 O'lchov: boshiga qo'shish

n ta buyurtmani birma-bir boshiga qo'shdik: massivda unshift, ro'yxatda prepend. Usul — benchmarking darsidagidek: har n alohida jarayonda, isitish, mediana:

Har unshift O(n), n tasi — O(n²): n ikki baravar — vaqt to'rt baravar (200 mingda hatto olti baravar — katta massiv keshga sig'may qoldi). Ro'yxatdagi prepend esa har biri O(1), jami O(n). 200 ming buyurtmada farq ≈ 3 700 baravar: 4,8 soniya va 1,3 millisekund.

prepend vaqtlari shunchalik kichikki, ularda shovqin ko'p — nisbatlar sakraydi. Chiziqli o'sishni ko'rish uchun uni 1–8 million tugunda ham o'lchadik: ≈ 19, 84, 176, 432 ms. Har qadamda taxminan ikki baravar (bittasi ×4,3) — bu yerda vaqtning katta qismini millionlab yangi obyekt uchun xotira ajratish va axlat yig'uvchi oladi.

5.3 O'lchov: aylanib chiqish — massiv yutadi

Endi n ta sonning yig'indisi: ikkalasi ham O(n). Kim tezroq?

Ikkalasida ham n ikki baravar — vaqt taxminan ikki baravar: O(n). Lekin massiv bir necha baravar tez. Sabab — kesh (Massiv xotirada): massiv elementlari yonma-yon, protsessor ularni bo'lak-bo'lak oldindan yuklaydi. Ro'yxat tugunlari xotira bo'ylab tarqoq — har .next yangi joyga "sakrash".

Xotira ham farq qiladi. --expose-gc bilan heapUsed ni o'lchadik (Xotira murakkabligi darsidagi usul): million sonli massiv ≈ 7,6 MB, million tugunli ro'yxat ≈ 38 MB. Har tugun — alohida obyekt: qiymat, next havolasi va obyekt sarlavhasi. Taxminan 5 baravar ko'p.

5.4 «Bahor»da qaysi birini tanlash kerak?

O'lchovlardan keyin Sardor har vazifa uchun alohida qaror qildi:

• Menyu (60 ta taom, ko'pincha indeks yoki filtr bilan o'qiladi) — massiv. Kam o'zgaradi, tez-tez o'qiladi, kesh yutug'i katta.
• Oshxona navbati (oxiriga qo'shiladi, boshidan olinadi, ba'zan boshiga shoshilinch qo'shiladi) — linked list. Hamma amal O(1).
• Kunlik hisobot (bir marta yig'iladi, keyin saralanadi va hisoblanadi) — massiv. sort, reduce va indeks kerak.
• "Oxirgi 20 ta ko'rilgan taom" (yangisi boshiga, eskisi oxiridan tushadi) — ikkalasi ham ishlaydi. Kichik n da massiv yetarli; katta n da linked list yoki ring buffer.

Qoida oddiy: avval amallarni sanang. Qaysi amal eng ko'p bajarilsa, o'shani arzon qiladigan tuzilmani tanlang. Shubha bo'lsa — massivdan boshlang va o'lchang.

Maslahat: Amalda JavaScript'da linked list kam yoziladi — massiv ko'p hollarda tezroq va qulayroq. Linked list'ni boshidan yoki o'rtasidan tez-tez qo'shish va olib tashlash kerak bo'lganda tanlang: navbatlar, LRU kesh, tarix. U Queue va LRU kesh darslarida asosiy g'isht bo'ladi.

6. Chegaraviy holatlar

7. Ko'p uchraydigan xatolar

7.1 null ning xususiyatini o'qish

const head = { value: 101, next: null };
console.log(head.next.value);

Konsolda:

TypeError: Cannot read properties of null (reading 'value')

Tarjimasi: "Tur xatosi: null ning xususiyatlarini o'qib bo'lmaydi (value ni o'qishda)". head.next — null, undan .value so'radik. Linked list'dagi eng ko'p uchraydigan xato: sikl sharti current.next !== null o'rniga current !== null bo'lishi kerak bo'lgan joyda (yoki aksincha) adashish. Tuzatish: .next. dan oldin doim "u null bo'lishi mumkinmi?" deb so'rang.

7.2 tail ni yangilashni unutish

Oxirgi tugun o'chirildi, tail esa eskisida qoldi. Keyingi append yo'qolib ketadi — xato xabari yo'q. Tuzatish: har remove va removeFirst da "bu tail emasmidi?" deb tekshiring, test yozing.

7.3 head ni o'zini surish

while (head) head = head.next — sikldan keyin ro'yxat bo'sh bo'lib qoladi. Tuzatish: aylanish uchun alohida current o'zgaruvchisi.

7.4 size ni yangilamaslik

size++/size-- ni bitta tarmoqda unutish — get va insertAt dagi chegaralar buziladi. Tuzatish: har qo'shish va o'chirishda, testda size ni tekshiring.

8. Mashqlar

1-mashq (oson): Qog'ozda chizing

Bo'sh ro'yxatga ketma-ket: append(5), prepend(3), append(8), prepend(1), remove(5). Har amaldan keyin zanjirni head → … → null ko'rinishida yozing va tail qaysi tugun ekanini ko'rsating.

2-mashq (o'rta): Indeks bilan olish va qo'yish

LinkedList ga ikki metod qo'shing: get(index) — i-tugun qiymati (chegaradan tashqarida undefined) va insertAt(index, value) — shu o'ringa qo'yish. insertAt(0, …) — prepend, insertAt(size, …) — append. Noto'g'ri indeksda RangeError tashlang. Ikkalasining murakkabligi qanday? Ishora: insertAt uchun index - 1 o'rindagi tugunni toping.

get(index) {
  if (index < 0 || index >= this.size) return undefined;
  let current = this.head;
  for (let i = 0; i < index; i++) current = current.next;
  return current.value;
}
insertAt(index, value) {
  if (index < 0 || index > this.size) {
    throw new RangeError("indeks");
  }
  if (index === 0) return this.prepend(value);
  if (index === this.size) return this.append(value);
  let prev = this.head;
  for (let i = 0; i < index - 1; i++) prev = prev.next;
  prev.next = new ListNode(value, prev.next);
  this.size++;
}

3-mashq (qiyin): To'liq klass va testlar

kurs/mashqlar/14/16-linked-list/royxat.test.mjs faylida ListNode va LinkedList ni yozing: prepend, append, removeFirst (head qiymatini qaytaradi), get, insertAt va [Symbol.iterator]. node:test bilan sinang: bo'sh ro'yxat, tartib, removeFirst dan keyin tail tozalanishi va 2-mashqdagi metodlar.

// kurs/mashqlar/14/16-linked-list/royxat.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  prepend(value) {
    this.head = new ListNode(value, this.head);
    if (this.tail === null) this.tail = this.head;
    this.size++;
  }
  append(value) {
    const node = new ListNode(value);
    if (this.tail === null) this.head = node;
    else this.tail.next = node;
    this.tail = node;
    this.size++;
  }
  removeFirst() {
    if (this.head === null) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null;
    this.size--;
    return value;
  }
  get(index) {
    if (index < 0 || index >= this.size) return undefined;
    let current = this.head;
    for (let i = 0; i < index; i++) current = current.next;
    return current.value;
  }
  insertAt(index, value) {
    if (index < 0 || index > this.size) {
      throw new RangeError("indeks");
    }
    if (index === 0) return this.prepend(value);
    if (index === this.size) return this.append(value);
    let prev = this.head;
    for (let i = 0; i < index - 1; i++) prev = prev.next;
    prev.next = new ListNode(value, prev.next);
    this.size++;
  }
  *[Symbol.iterator]() {
    for (let c = this.head; c !== null; c = c.next) yield c.value;
  }
}

test("bo'sh ro'yxat", () => {
  const list = new LinkedList();
  assert.equal(list.size, 0);
  assert.equal(list.removeFirst(), undefined);
  assert.equal(list.get(0), undefined);
  assert.deepEqual([...list], []);
});

test("prepend va append tartibi", () => {
  const list = new LinkedList();
  list.append(101);
  list.append(102);
  list.prepend(103);
  assert.deepEqual([...list], [103, 101, 102]);
  assert.equal(list.head.value, 103);
  assert.equal(list.tail.value, 102);
});

test("removeFirst oxirgi elementda tail ni ham tozalaydi", () => {
  const list = new LinkedList();
  list.append(101);
  assert.equal(list.removeFirst(), 101);
  assert.equal(list.head, null);
  assert.equal(list.tail, null);
  list.append(102); // tail eskisiga ulanib qolmasligi kerak
  assert.deepEqual([...list], [102]);
});

test("get va insertAt", () => {
  const list = new LinkedList();
  for (const id of [101, 102, 104]) list.append(id);
  list.insertAt(2, 103);
  list.insertAt(0, 100);
  list.insertAt(5, 105);
  assert.deepEqual([...list], [100, 101, 102, 103, 104, 105]);
  assert.equal(list.get(3), 103);
  assert.equal(list.get(6), undefined);
  assert.equal(list.tail.value, 105);
  assert.throws(() => list.insertAt(9, 1), RangeError);
});

✔ bo'sh ro'yxat (1.2208ms)
✔ prepend va append tartibi (0.4427ms)
✔ removeFirst oxirgi elementda tail ni ham tozalaydi (0.1334ms)
✔ get va insertAt (0.4835ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 94.0261

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga "Ma'lumotlar tuzilmalari" degan yangi jadval oching: ustunlar — amal, massiv, linked list. Shu darsdagi 6 ta amalni yozing va har birida o'lchangan raqamingizni (bo'lsa) qavsda qo'shing.

## Ma'lumotlar tuzilmalari

| Amal | Massiv | Linked list |
|---|---|---|
| i-element | O(1) | O(n) |
| Boshiga qo'shish | O(n) unshift | O(1) prepend |
| Oxiriga qo'shish | O(1) amort. push | O(1) tail bilan |
| Boshidan olish | O(n) shift | O(1) removeFirst |
| Qidirish | O(n) | O(n) |
| Ma'lum joydan o'chirish | O(n) splice | O(1) prev bo'lsa |

git add 14/MURAKKABLIK.md 14/16-linked-list
git commit -m "14/16: LinkedList klassi va testlar"

9. Real ishda

• Navbatlar va keshlar. Ko'p navbat (queue) va LRU kesh implementatsiyalari ichida linked list bor: boshidan olish va ma'lum joydan o'chirish O(1) bo'lishi kerak.
• Brauzer va freymvorklar ichida. React komponentlar daraxtini "fiber" tugunlarida saqlaydi — har tugunda child, sibling, return havolalari bor (React'ni kursda alohida o'rganamiz). DOM'ning o'zida ham nextSibling — bog'langan tuzilma.
• Operatsion tizim va xotira. Bo'sh xotira bloklari ro'yxati, jarayonlar navbati — klassik linked list.
• Intervyu. Linked list — eng ko'p so'raladigan tuzilmalardan: "Design Linked List" (LeetCode 707), "Remove Linked List Elements" (203). Keyingi darsdagi masalalar esa undan ham mashhur.

Xulosa

• Linked list — value va next li tugunlar zanjiri; ro'yxat — head havolasi, oxiri — null.
• prepend va (tail bilan) append — O(1): faqat ikki havola o'zgaradi, hech kim surilmaydi.
• Indeks bilan kirish va qidirish — O(n): head dan yurish kerak. O'chirish uchun oldingi tugun kerak.
• Head, tail, bitta tugun va bo'sh ro'yxat — xatolarning asosiy manbai; tail ni yangilashni unutmang.
• O'lchovda: boshiga qo'shishda ro'yxat massivdan yuzlab baravar tez, aylanib chiqishda esa massiv bir necha baravar tez (kesh) va 5 baravar kam xotira oladi.

Keyingi dars: Linked list masalalari — ro'yxatni ag'darish, tez va sekin ko'rsatkich (o'rtani topish, siklni aniqlash), ikki saralangan ro'yxatni birlashtirish, dummy head, doubly va circular list.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 10-bob (linked lists).
• MDN: Iteration protocols, Symbol.iterator — developer.mozilla.org
• V8 blogi: "Fast properties in V8" (obyekt tuzilishi va xotira) — v8.dev/blog/fast-properties
• LeetCode: 707 "Design Linked List" — leetcode.com/problems/design-linked-list