Linked list (bog‘langan ro‘yxat)

Tasavvur qiling, musiqa pleyeridagi qo‘shiqlar ketma-ketligini boshqaryapsiz. Har bir qo‘shiqdan keyin qaysi qo‘shiq ijro etilishi kerakligini bilish kifoya. Ro‘yxat o‘rtasiga yangi qo‘shiq qo‘shilsa, undan keyingi barcha qo‘shiqlarni boshqa joyga ko‘chirish shart emas: oldingi qo‘shiqning “keyingisi” haqidagi ma’lumotini yangi qo‘shiqqa, yangi qo‘shiqnikini esa navbatdagi qo‘shiqqa yo‘naltirish mumkin.

Linked list, ya’ni bog‘langan ro‘yxat, elementlarni aynan shu g‘oya asosida saqlaydigan ma’lumotlar tuzilmasidir. Undagi elementlar xotirada yonma-yon turishi shart emas. Har bir element o‘z qiymati bilan birga ketma-ketlikdagi boshqa elementga olib boruvchi bog‘lanishni ham saqlaydi.

[10 | keyingi] → [20 | keyingi] → [30 | mavjud emas]

Bu tuzilma arraydagi muhim cheklovni yumshatish uchun kerak: array o‘rtasiga element qo‘shilganda yoki undan element o‘chirilganda boshqa elementlarni surish talab qilinishi mumkin. Linked listda esa kerakli joy oldindan topilgan bo‘lsa, odatda bir nechta bog‘lanishni almashtirish yetarli. Buning evaziga linked list arraydagi index orqali tezkor kirish imkoniyatidan voz kechadi. Masalan, uchinchi elementga yetish uchun birinchi elementdan boshlab bog‘lanishlar bo‘ylab yurish kerak.

Linked listni tushunishning markazida bitta muvozanat turadi: elementlarni jismonan yonma-yon saqlash o‘rniga, ularning mantiqiy tartibini bog‘lanishlar orqali saqlash. Bu ayrim qo‘shish va o‘chirish amallarini qulay qiladi, lekin qidirish, index bo‘yicha kirish va xotiradan samarali foydalanishni qimmatlashtiradi.

Zanjir analogiyasi

Linked listni alohida halqalardan tuzilgan zanjirga o‘xshatish mumkin. Har bir halqa keyingi halqaga ulangan. Zanjirning boshini bilsak, birinchi halqadan ikkinchisiga, undan uchinchisiga o‘tib, oxirigacha yetamiz.

O‘rtaga yangi halqa qo‘shish uchun butun zanjirni yangidan yasash shart emas. Bitta ulanishni uzib, yangi halqani ikki tomonga ulaymiz. Ammo “yuzinchi halqani darhol ber” deyilsa, zanjirning boshidan boshlab 99 ta ulanish bo‘ylab yurishga to‘g‘ri keladi. Chunki halqalarda arraydagi kabi joylashuv indexidan manzil hisoblaydigan mexanizm yo‘q.

Analogiyaning chegarasi ham bor: kompyuter xotirasidagi node’lar bir-biriga jismonan tegib turmaydi. Ularni bog‘laydigan narsa — boshqa node joylashgan manzilni bildiruvchi reference.

Asosiy terminlar

Linked list bilan ishlaganda quyidagi tushunchalarni ajratish kerak:

• node (tugun) — qiymat va kamida bitta bog‘lanishni saqlaydigan yaxlit qism;
• value yoki data — node ichidagi foydali ma’lumot, masalan, son, buyurtma yoki qo‘shiq;
• reference — boshqa node’ni topish imkonini beruvchi ma’lumot;
• next — keyingi node’ga olib boruvchi reference;
• previous yoki prev — oldingi node’ga olib boruvchi reference;
• head — ro‘yxatdagi birinchi node’ga reference;
• tail — ro‘yxatdagi oxirgi node’ga reference;
• traversal — bog‘lanishlar bo‘ylab node’larni ketma-ket ko‘rib chiqish;
• length — ro‘yxatdagi node’lar soni.

Element va node bir xil tushuncha emas. Element deganda foydalanuvchi saqlamoqchi bo‘lgan qiymat nazarda tutilishi mumkin. Node esa shu qiymatni va tuzilma ishlashi uchun zarur reference’larni o‘rab turadi:

element:  25

node:
+----------+------------------+
| value=25 | next=manzil_8200 |
+----------+------------------+

Reference bilan obyektning o‘zini ham aralashtirmaslik kerak. Reference node’ning nusxasi emas; u node’ga qanday yetib borishni bildiradi. Past darajali tushuntirishlarda buning uchun ko‘pincha pointer so‘zi ishlatiladi. Pointer odatda xotira manzilini bevosita saqlaydi. Yuqori darajali tillardagi reference esa tashqi ko‘rinishda boshqacha boshqarilishi mumkin. Linked listning fundamental modeli uchun ikkalasi ham “boshqa node’ga olib boruvchi bog‘lanish” vazifasini bajaradi.

Bog‘lanishning mavjud emasligini pseudocodeda NULL bilan belgilaymiz. Muayyan til bunga null, nil, None yoki boshqa nom berishi mumkin.

Xotirada qanday ishlaydi?

Klassik array uchun elementlar uzluksiz xotira (contiguous memory) hududida yonma-yon joylashadi. Linked list node’lari esa xotiraning turli joylarida bo‘lishi mumkin. Faraz qilaylik, uchta node quyidagi manzillarda yaratilgan:

head = 5000

Manzil 5000                         Manzil 9100
+------------+------------+         +------------+------------+
| value = 10 | next = 2400| ------> | value = 30 | next = NULL|
+------------+------------+         +------------+------------+
               |
               |   Manzil 2400
               +-> +------------+------------+
                   | value = 20 | next = 9100|
                   +------------+------------+

Mantiqiy tartib: 10 → 20 → 30

Diagrammadagi qutilarning chizilish tartibi xotiradagi jismoniy tartibni bildirmaydi. 20 qiymatli node pastroq manzilda tursa ham, mantiqiy ketma-ketlikda ikkinchi keladi. Tartibni manzillarning kattaligi emas, next reference’lari belgilaydi.

Ro‘yxatning o‘zi hech bo‘lmaganda head reference’ini saqlashi kerak. Ko‘p implementatsiyalarda oxiriga tez qo‘shish uchun tail, uzunlikni darhol bilish uchun esa length ham saqlanadi:

list:
    head   → birinchi node
    tail   → oxirgi node       (ixtiyoriy, lekin ko‘p uchraydi)
    length → node’lar soni     (ixtiyoriy)

tail va length qulaylik beradi, ammo har bir o‘zgarishda ularni ham to‘g‘ri yangilash kerak. Masalan, oxirgi node o‘chirilganda tail yangi oxirgi node’ga o‘tishi shart. Aks holda tuzilmaning ichki holati buziladi.

Node yaratish va xotirani bo‘shatish

Yangi element qo‘shilganda odatda yangi node uchun alohida xotira ajratiladi. Qiymat va reference shu node ichiga yoziladi, keyin mavjud bog‘lanishlar yangilanadi. Node o‘chirilganda esa unga olib boruvchi bog‘lanish zanjirdan chiqariladi. Shundan so‘ng xotirani kim va qachon bo‘shatishi dasturlash tilining xotira boshqaruviga bog‘liq:

• qo‘lda boshqariladigan muhitda dasturchi ajratilgan xotirani bo‘shatishi kerak;
• avtomatik xotira boshqaruvida node’ga boshqa reference qolmagach, garbage collector uni keyinroq tozalashi mumkin.

Bog‘lanishni uzishning o‘zi har qanday muhitda xotira darhol bo‘shadi degani emas. Boshqa joyda o‘sha node’ga reference saqlanib turgan bo‘lishi mumkin.

Nega linked list amalda arraydan sekinroq bo‘lishi mumkin?

Big O ikki amal o‘sish tartibi haqida ma’lumot beradi, lekin apparatdagi barcha xarajatni ko‘rsatmaydi. Array elementlari yonma-yon bo‘lgani uchun protsessor bir elementni o‘qiyotganda uning yonidagilarni ham tezkor xotira — CPU cachega olib kelishi mumkin. Linked list node’lari tarqoq joylashgani sababli navbatdagi node uchun asosiy xotiraning boshqa hududiga murojaat qilish talab qilinishi mumkin.

Shu sababli array va linked list bo‘ylab yurish ikkalasi ham O(n) bo‘lsa-da, array amalda ko‘pincha tezroq bo‘ladi. Bundan tashqari, har bir linked list node’i qiymatdan tashqari kamida bitta reference saqlaydi va odatda alohida ajratiladi. Bu qo‘shimcha xotira va xotira boshqaruvi xarajatini keltirib chiqaradi.

Nega aynan shunday qurilgan?

Array tartibni elementlarning xotiradagi joylashuvi bilan ifodalaydi. Shu sababli indexdan manzilni hisoblash oson, ammo o‘rtada bo‘sh joy ochish qiyin. Linked list tartibni xotiradagi joylashuvdan ajratadi: “qaysi node keyin keladi?” degan javob next ichida turadi.

Bu qaror quyidagi almashinuvni yuzaga keltiradi:

• elementlarni ko‘chirmasdan bog‘lanishni o‘zgartirish mumkin;
• ro‘yxat uchun oldindan katta uzluksiz xotira hududi kerak emas;
• lekin har bir node reference uchun qo‘shimcha joy ishlatadi;
• kerakli o‘ringa bog‘lanishlar bo‘ylab yetib borish talab qilinadi;
• node’larning tarqoq joylashuvi cache samaradorligini pasaytiradi.

Demak, linked list “arrayning har jihatdan yaxshiroq turi” emas. U boshqa operatsiyalar to‘plamini ustun qo‘yadigan modeldir.

Linked list turlari

Bog‘langan ro‘yxatlar node ichida qaysi yo‘nalishdagi reference’lar saqlanishi va oxirgi node qayerga ulanishiga qarab farqlanadi.

Singly linked list

Singly linked list, ya’ni bir tomonlama bog‘langan ro‘yxatda har bir node faqat keyingi node’ga reference saqlaydi. Oxirgi node’ning next qiymati NULL bo‘ladi.

head                                         tail
 ↓                                            ↓
[A | next] → [B | next] → [C | next] → [D | NULL]

Ro‘yxat bo‘ylab faqat oldinga yurish mumkin. C node’da turganda B ga qaytish uchun oldingi node’ga tayyor bog‘lanish yo‘q. Uni topish kerak bo‘lsa, headdan yana yurish talab qilinadi.

Singly linked list reference uchun kamroq qo‘shimcha xotira ishlatadi va bog‘lanishlarni boshqarish nisbatan sodda. U quyidagi vaziyatlarda mos keladi:

• faqat oldinga ketma-ket ishlov beriladigan vazifalar;
• elementlar boshiga tez-tez qo‘shiladigan ro‘yxat;
• alohida zanjirlash ishlatadigan hash table bucketlari;
• bo‘sh bloklar zanjiri kabi sodda ichki boshqaruv tuzilmalari.

Masalan, hash table’da bir xil bucketga tushgan yozuvlar kichik singly linked listga ulanadigan implementatsiya bo‘lishi mumkin. Yangi yozuvni zanjir boshiga ulash tez, barcha yozuvlarni faqat oldinga ko‘rib chiqish esa bu vazifa uchun yetarli. Zamonaviy implementatsiyalar uzun zanjirlar uchun boshqa tuzilmalarga o‘tishi ham mumkin; bu universal qoida emas.

Doubly linked list

Doubly linked list, ya’ni ikki tomonlama bog‘langan ro‘yxatda har bir node keyingi node’dan tashqari oldingi node’ga ham reference saqlaydi.

NULL ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → NULL
        ↑                   ↑
       head                tail

Aniqroq node modeli quyidagicha:

+----------+-----------+----------+
| previous |   value   |   next   |
+----------+-----------+----------+

Bu ro‘yxatda oldinga ham, orqaga ham yurish mumkin. Agar o‘chiriladigan node’ga reference allaqachon mavjud bo‘lsa, uning oldingi node’ini boshidan qidirmasdan previous orqali topish mumkin. Buning evaziga har bir node yana bitta reference saqlaydi va har bir qo‘shish yoki o‘chirishda ko‘proq bog‘lanishni to‘g‘ri yangilash talab qilinadi.

Real misol sifatida LRU cacheni ko‘rish mumkin. U yaqinda ishlatilgan elementlarni bir chetga, eng uzoq vaqt ishlatilmaganini boshqa chetga ko‘chirib turadi. Hash table elementni tez topadi, doubly linked list esa topilgan node’ni ro‘yxat o‘rtasidan uzib, boshiga O(1) vaqtda ulash imkonini beradi. Eng eski element tail tomondan tez chiqariladi. Bu yerda faqat linked listning o‘zi kalit bo‘yicha tez qidirishni ta’minlamaydi; O(1) kutiladigan qidirish hash table bilan birgalikda hosil bo‘ladi.

Brauzer tarixini soddalashtirilgan modelda ikki tomonlama ro‘yxat bilan tasvirlash ham mumkin: previous orqaga, next oldinga o‘tishni bildiradi. Amaliy brauzerlar tarix, tab va navigatsiyani bundan murakkabroq tuzilmalar bilan boshqarishi mumkin, lekin ikki yo‘nalishli bog‘lanish g‘oyasini bu misol yaxshi ko‘rsatadi.

Circular linked list

Circular linked list, ya’ni halqasimon bog‘langan ro‘yxatda oxirgi node ro‘yxat tugaganini bildiruvchi NULL o‘rniga yana boshidagi node’ga ulanadi.

        ┌───────────────────────────┐
        ↓                           │
head → [A | next] → [B | next] → [C | next]

Circular ro‘yxat singly yoki doubly bo‘lishi mumkin. Doubly circular ko‘rinishda head.previous tail’ga, tail.next esa head’ga ulanadi:

      ┌──────────────────────────┐
      ↓                          │
     [A] ⇄ [B] ⇄ [C]
      │                          ↑
      └──────────────────────────┘

Bu model tabiiy oxiri bo‘lmagan navbatlar uchun qulay. Masalan, round-robin rejalashtirishda vazifalar navbat bilan oz miqdorda protsessor vaqti oladi. Oxirgi vazifadan keyin navbat yana birinchi vazifaga o‘tadi. Ko‘p o‘yinchili stol o‘yinida ham yurish oxirgi o‘yinchidan keyin birinchi o‘yinchiga qaytadi.

Circular tuzilmaning asosiy xavfi — traversal uchun NULLga yetishni to‘xtash sharti qilib bo‘lmaydi. Boshlagan node’ga qaytilgani tekshirilmasa, sikl cheksiz davom etadi.

Sentinel node ishlatiladigan ro‘yxat

Ba’zi implementatsiyalar haqiqiy foydalanuvchi qiymatini saqlamaydigan maxsus sentinel yoki dummy node’dan foydalanadi. U ro‘yxat boshi yoki oxiridagi alohida holatlarni kamaytiradi:

[SENTINEL] → [10] → [20] → [30] → NULL

Masalan, birinchi haqiqiy node’ni o‘chirish ham o‘rtadagi node’ni o‘chirishga o‘xshab qoladi, chunki undan oldin sentinel mavjud. Koddagi shartlar kamayadi, ammo bitta qo‘shimcha node saqlanadi va sentinelni haqiqiy ma’lumot bilan adashtirmaslik kerak. Sentinel alohida asosiy turdan ko‘ra implementatsiya usulidir.

Asosiy amallar

Quyidagi pseudocode avvalo singly linked listni ko‘rsatadi. Unda head, ixtiyoriy tail va length mavjud deb faraz qilamiz. Implementatsiya bu maydonlarning ayrimlarini saqlamasa, ayrim amallarning narxi o‘zgaradi.

Bo‘sh ro‘yxat yaratish

Bo‘sh linked listda birinchi node yo‘q:

head = NULL
tail = NULL
length = 0

Bu amal O(1) vaqt va O(1) xotira talab qiladi, chunki elementlar sonidan qat’i nazar faqat bir nechta boshqaruv qiymati yaratiladi.

Traversal

Traversal ro‘yxat boshidan boshlanib, next reference’lari bo‘ylab oxirigacha yuradi:

FUNCTION TRAVERSE(head)
    current = head

    WHILE current != NULL
        VISIT current.value
        current = current.next

Har bir node bir marta ko‘riladi. n ta node bo‘lsa, vaqt murakkabligi O(n). current uchun bitta qo‘shimcha reference yetarli bo‘lgani sababli iterativ traversalning qo‘shimcha xotira murakkabligi O(1).

Circular ro‘yxatda algoritm boshqacha to‘xtashi kerak:

FUNCTION TRAVERSE_CIRCULAR(head)
    IF head = NULL
        RETURN

    current = head

    REPEAT
        VISIT current.value
        current = current.next
    UNTIL current = head

Avval bo‘sh ro‘yxat tekshiriladi. Aks holda mavjud bo‘lmagan node’ga murojaat qilinadi.

Index bo‘yicha elementga kirish

Arrayda index orqali manzil hisoblanadi. Linked listda esa index faqat nechta qadam yurish kerakligini bildiradi:

FUNCTION GET(head, index, length)
    IF index < 0 OR index >= length
        RETURN XATO

    current = head
    position = 0

    WHILE position < index
        current = current.next
        position = position + 1

    RETURN current.value

0-index uchun yurish talab qilinmaydi va eng yaxshi holat O(1). Oxirgi index uchun deyarli barcha node’lardan o‘tiladi, shuning uchun eng yomon holat O(n). Umumiy holda i-indexga kirish O(i), Big O jadvalida esa odatda O(n) deb ko‘rsatiladi. Qo‘shimcha xotira O(1).

Doubly linked listda tail mavjud bo‘lsa, index ro‘yxatning ikkinchi yarmida ekaniga qarab orqadan yurish mumkin. Bu qadamlar sonini kamaytiradi, lekin eng yomon holat baribir O(n) bo‘lib qoladi.

Qiymatni qidirish

Saralanmagan linked listda qidiruv boshidan ketma-ket amalga oshiriladi:

FUNCTION FIND(head, target)
    current = head

    WHILE current != NULL
        IF current.value = target
            RETURN current

        current = current.next

    RETURN TOPILMADI

Birinchi node mos kelsa eng yaxshi holat O(1). Qiymat oxirida bo‘lsa yoki umuman mavjud bo‘lmasa, barcha n ta node tekshiriladi — O(n). Faqat bitta current reference’i ishlatilgani uchun qo‘shimcha xotira O(1).

Ro‘yxat saralangan bo‘lsa, targetdan katta qiymatga yetganda qidiruvni erta to‘xtatish mumkin. Ammo o‘rtadagi node’ga bevosita kira olmaganimiz sababli oddiy linked listda arraydagidek samarali binary search qilib bo‘lmaydi. O‘rtani topishning o‘zi yurishni talab qiladi.

Boshiga element qo‘shish

Yangi node avval eski head’ga ulanadi, keyin head yangi node’ga o‘tkaziladi:

Oldin:  head → [20] → [30] → NULL

Keyin:  head → [10] → [20] → [30] → NULL

FUNCTION PREPEND(list, value)
    new_node = NEW NODE(value)
    new_node.next = list.head
    list.head = new_node

    IF list.tail = NULL
        list.tail = new_node

    list.length = list.length + 1

Ro‘yxat qanchalik katta bo‘lmasin, bir xil miqdordagi reference yangilanadi. Vaqt O(1). Yangi node uchun O(1) qo‘shimcha xotira ajratiladi. Bo‘sh ro‘yxatda yangi node ham head, ham tail bo‘lishi alohida hisobga olinadi.

Oxiriga element qo‘shish

tail saqlansa, oxirgi node’ni qidirmasdan yangi node ulash mumkin:

FUNCTION APPEND(list, value)
    new_node = NEW NODE(value)

    IF list.head = NULL
        list.head = new_node
        list.tail = new_node
    ELSE
        list.tail.next = new_node
        list.tail = new_node

    list.length = list.length + 1

tail bilan vaqt O(1). tail saqlanmasa, avval oxirgi node’ni topish uchun boshidan yurish kerak va vaqt O(n) bo‘ladi. Demak, “linked list oxiriga qo‘shish har doim O(1)” degan gap to‘liq emas; bu implementatsiya qaysi boshqaruv reference’larini saqlashiga bog‘liq.

Ma’lum node’dan keyin qo‘shish

Oldingi node’ga reference previous_node ko‘rinishida allaqachon berilgan bo‘lsa:

FUNCTION INSERT_AFTER(previous_node, value)
    IF previous_node = NULL
        RETURN XATO

    new_node = NEW NODE(value)
    new_node.next = previous_node.next
    previous_node.next = new_node

Oldin: [10] ─────────→ [30]

Keyin: [10] → [20] → [30]

Bog‘lanishlarni yangilash O(1). Ammo “qiymati 10 bo‘lgan node’dan keyin qo‘sh” deyilsa va o‘sha node’ga reference tayyor bo‘lmasa, uni topish O(n) vaqt olishi mumkin. Joyni topish narxi bilan topilgan joyga ulash narxini alohida hisoblash kerak.

Index bo‘yicha qo‘shish

FUNCTION INSERT_AT(list, index, value)
    IF index < 0 OR index > list.length
        RETURN XATO

    IF index = 0
        PREPEND(list, value)
        RETURN

    previous = NODE_AT(list.head, index - 1)
    new_node = NEW NODE(value)
    new_node.next = previous.next
    previous.next = new_node

    IF new_node.next = NULL
        list.tail = new_node

    list.length = list.length + 1

Birinchi joyga qo‘shish O(1). Umumiy index uchun oldingi node’ni topish kerak, shu sababli eng yomon vaqt O(n). Ulanishning o‘zi esa O(1). Yangi node O(1) qo‘shimcha xotira oladi.

Boshidan element o‘chirish

FUNCTION REMOVE_FIRST(list)
    IF list.head = NULL
        RETURN XATO

    removed = list.head
    list.head = list.head.next

    IF list.head = NULL
        list.tail = NULL

    list.length = list.length - 1
    RETURN removed.value

Faqat head o‘zgartiriladi, shuning uchun vaqt O(1), yordamchi xotira O(1). Bitta elementli ro‘yxatda o‘chirishdan keyin head ham, tail ham NULL bo‘lishi kerak.

Ma’lum node’dan keyingi elementni o‘chirish

FUNCTION REMOVE_AFTER(list, previous_node)
    IF previous_node = NULL OR previous_node.next = NULL
        RETURN XATO

    removed = previous_node.next
    previous_node.next = removed.next

    IF removed = list.tail
        list.tail = previous_node

    list.length = list.length - 1
    RETURN removed.value

Oldingi node tayyor bo‘lsa, bu amal O(1). Singly linked listda faqat o‘chiriladigan node’ning o‘ziga reference berilishi har doim yetarli emas: uning oldingisidagi nextni o‘zgartirish kerak. Doubly linked listda removed.previous mavjud bo‘lgani uchun, head va tail holatlari to‘g‘ri boshqarilsa, berilgan node’ni O(1) vaqtda uzish mumkin.

Oxiridan element o‘chirish

Singly linked listda tail’ni bilishning o‘zi yetmaydi. Yangi tail bo‘ladigan oldingi node’ni topish uchun boshidan yurish kerak:

FUNCTION REMOVE_LAST_SINGLY(list)
    IF list.head = NULL
        RETURN XATO

    IF list.head.next = NULL
        value = list.head.value
        list.head = NULL
        list.tail = NULL
        list.length = 0
        RETURN value

    current = list.head

    WHILE current.next != list.tail
        current = current.next

    value = list.tail.value
    current.next = NULL
    list.tail = current
    list.length = list.length - 1
    RETURN value

Vaqt O(n), qo‘shimcha xotira O(1). Doubly linked listda esa tail.previous yangi tail’ni darhol beradi, shuning uchun oxiridan o‘chirish O(1) bo‘lishi mumkin. Yana bir reference saqlash aynan shunday amallarni tezlashtirish evaziga keladi.

Qiymatni yangilash

Node’ga reference tayyor bo‘lsa, uning qiymatini almashtirish O(1):

node.value = new_value

Lekin index yoki eski qiymat orqali yangilash so‘ralsa, avval kerakli node qidiriladi. Bu qidiruv odatda O(n), almashtirish esa O(1). Node qiymatini yangilash uning next yoki previous bog‘lanishini o‘zgartirmaydi.

Bosqichma-bosqich misol

Boshlanishida quyidagi singly linked list bor:

head → [12] → [25] → [40] → NULL

25 dan keyin 30 qo‘shamiz. previous reference’i 25 node’ni ko‘rsatib turibdi deb faraz qilamiz.

1. 30 qiymatli yangi node yaratiladi.
2. Yangi node’ning next qiymati 25.next, ya’ni 40 node’ga o‘rnatiladi.
3. 25.next yangi node’ga o‘rnatiladi.

1-qadam:
head → [12] → [25] → [40] → NULL       [30] → NULL

2-qadam:
head → [12] → [25] → [40] → NULL
                         ↑
                       [30]

3-qadam:
head → [12] → [25] → [30] → [40] → NULL

Ikkinchi va uchinchi qadam teskari bajarilsa, 40 ga olib boruvchi yagona bog‘lanish yo‘qolishi mumkin. Avval yangi node’ni zanjirning qolgan qismiga ulash, keyin oldingi node’ni yangi node’ga yo‘naltirish xavfsizroq.

Endi 25 ni o‘chirish uchun undan oldingi 12 node’i ma’lum deb olamiz:

Oldin: head → [12] → [25] → [30] → [40] → NULL

12.next = 25.next

Keyin: head → [12] ───────→ [30] → [40] → NULL
                         [25] zanjirdan chiqdi

Qiymatlar nusxalanmadi va 30, 40 node’lari xotirada ko‘chirilmadi. Faqat 12.next reference’i o‘zgardi. Linked listning qo‘shish va o‘chirishdagi asosiy foydasi shu.

Vaqt va xotira murakkabligi

Big O real sekundni emas, ma’lumot hajmi oshganda ish miqdori qanday o‘sishini bildiradi. O(1) amal mutlaqo vaqt olmaydi degani emas; ro‘yxat 10 ta yoki millionta node’dan iborat bo‘lsa ham, bajariladigan bog‘lanish yangilanishlari soni o‘zgarmaydi. O(n) esa eng yomon holatda node’lar soniga mutanosib yurish kerakligini bildiradi.

Quyidagi jadval klassik implementatsiyalar uchun umumiy ko‘rinishni beradi:

Jadvaldagi O(1) qo‘shish va o‘chirish natijasi kerakli node’ga reference oldindan mavjud bo‘lganda to‘g‘ri. Joyni qiymat yoki index orqali avval topish kerak bo‘lsa, umumiy amal O(n) bo‘ladi.

Tuzilmaning xotira murakkabligi

n ta qiymat uchun linked listning umumiy xotirasi O(n). Singly turda har bir node qiymat va bitta next, doubly turda esa qiymat, next va previous saqlaydi:

Singly: n × (qiymat + 1 reference)
Doubly: n × (qiymat + 2 reference)

Big O ikkalasini ham O(n) deydi, ammo doubly listning doimiy xarajati kattaroq. Bundan tashqari, node obyektining xizmat ma’lumotlari va xotira ajratish tizimining xarajatlari ham bo‘lishi mumkin. Aniq bayt miqdori til, platforma va implementatsiyaga bog‘liq.

Iterativ amallar odatda O(1) yordamchi xotira ishlatadi. Rekursiv traversal yozilsa, har bir chaqiruv call stackda joy egallashi sababli O(n) yordamchi xotira talab qilishi va juda uzun ro‘yxatda stack chegarasidan oshishi mumkin.

Linked list bilan keng tarqalgan algoritmik yondashuvlar

Bu yondashuvlar bog‘langan ro‘yxat masalalarida tez-tez uchraydi. Ularning to‘liq masalalari alohida mashq mavzusi bo‘lsa-da, asosiy g‘oyani tushunish linked listning tabiatini ochib beradi.

Ikki ko‘rsatkich

Bir ro‘yxat bo‘ylab ikki reference turli tezlikda yoki turli masofada yurishi mumkin. Ko‘pincha ular slow va fast deb ataladi:

slow = head
fast = head

WHILE fast != NULL AND fast.next != NULL
    slow = slow.next
    fast = fast.next.next

slow bir qadam, fast ikki qadam yuradi. fast oxirga yetganda slow taxminan o‘rtada bo‘ladi. Shu usul bilan uzunlikni oldindan bilmasdan o‘rta node’ni topish mumkin. Halqa mavjud bo‘lsa, tez va sekin ko‘rsatkichlar ma’lum sharoitda uchrashadi; bu cycle detection algoritmlarining asosiy g‘oyasidir.

Oraliqni saqlaydigan ikki ko‘rsatkich

Oxiridan k-node’ni topish uchun birinchi reference avval k qadam oldinga yuradi. Keyin ikkala reference bir vaqtda siljiydi. Birinchisi oxirga yetganda ikkinchisi kerakli masofada turadi. Bu usul ro‘yxat uzunligini alohida hisoblamasdan bitta traversal bilan ishlaydi.

Bog‘lanishlarni teskari aylantirish

Singly linked listni teskari qilishda node qiymatlari ko‘chirilmaydi; next yo‘nalishlari almashtiriladi:

Oldin:  A → B → C → NULL
Keyin:  NULL ← A ← B ← C

Bunda previous, current va next_node kabi reference’lar kerak bo‘ladi. current.next o‘zgartirilishidan oldin eski keyingi node saqlanmasa, zanjirning qolgan qismi yo‘qoladi. Har bir node bir marta ko‘rilgani uchun vaqt O(n), iterativ variantda yordamchi xotira O(1).

Array va linked list taqqoslanishi

Ikki tuzilma ham tartibli elementlar ketma-ketligini ifodalaydi, ammo tartibni turli yo‘l bilan saqlaydi.

Linked list o‘rtasiga qo‘shishning O(1) bo‘lishi ko‘pincha noto‘g‘ri talqin qilinadi. Agar “5000-indexga yangi element qo‘sh” deyilsa, oldingi node’ga yetish O(n). Arrayda esa joy darhol topiladi, ammo keyingi elementlarni surish O(n). Ikkalasining umumiy murakkabligi bir xil ko‘rinsa ham, xarajatning sababi boshqa.

Amaliy dasturda dynamic array ko‘pincha boshlang‘ich tanlov bo‘ladi: index orqali tez kiradi, cache bilan yaxshi ishlaydi va xotira xarajati kam. Linked list esa node’ga reference’lar uzoq vaqt saqlanadigan hamda ro‘yxat ichida tez-tez uzish-ulash haqiqatan kerak bo‘ladigan vazifalarda foydali.

Real qo‘llanishlar

LRU cache

LRU cache sig‘imi to‘lganda eng uzoq vaqt ishlatilmagan yozuvni chiqaradi. Doubly linked list foydalanish tartibini saqlaydi, hash table esa kalitdan node’ni tez topadi. Yozuv o‘qilganda uning node’i ro‘yxat boshiga ko‘chiriladi; sig‘im to‘lganda tail chiqariladi. Aynan ikki tomonlama bog‘lanish node’ni oldingi va keyingi qo‘shnilaridan tez uzishga imkon beradi.

Matn muharriridagi ketma-ket bo‘laklar

Katta matnni bitta uzluksiz arrayda saqlashda o‘rtaga kiritish ko‘p belgini ko‘chirishga olib kelishi mumkin. Ayrim muharrir tuzilmalari matnni bo‘laklarga ajratib, bo‘laklar orasidagi bog‘lanishlarni boshqaradi. Oddiy linked list bu vazifaning barcha talabini hal qilmaydi — amalda piece table, rope yoki muvozanatlangan daraxt kabi tuzilmalar ishlatilishi mumkin — ammo “ma’lumotni ko‘chirish o‘rniga bo‘laklarni qayta ulash” g‘oyasi linked list modeliga yaqin.

Round-robin navbat

Vazifalar yoki o‘yinchilar navbati doim takrorlansa, circular linked list oxiridan boshiga tabiiy o‘tishni beradi. Joriy node’dan nextga o‘tish O(1). Vazifa navbatdan chiqsa, uning qo‘shni bog‘lanishlari yangilanadi. Amaliy rejalashtiruvchi tizimlarda ustuvorlik, kutish va parallel bajarilish sabab tuzilma murakkabroq bo‘lishi mumkin.

Undo/redo va navigatsiya

Holatlar orasida oldinga va orqaga yurish kerak bo‘lsa, doubly linked list mantiqiy model bo‘la oladi. Joriy holatning previous bog‘lanishi undo’ga, next bog‘lanishi redo’ga olib boradi. Foydalanuvchi undo’dan keyin yangi amal bajarsa, oldingi redo tarmog‘i odatda bekor qilinadi. Oddiy chiziqli tarix uchun bu model mos, tarmoqlanadigan tarix uchun esa tree yoki graph kerak bo‘lishi mumkin.

Hash collision zanjirlari

Alohida zanjirlash (separate chaining) usulidagi hash table bir bucketga tushgan bir nechta yozuvni zanjirda saqlashi mumkin. Bucket zanjir boshini ko‘rsatadi, keyin mos kalit topilguncha node’lar tekshiriladi. Unumdorlik zanjirlar qisqa bo‘lishiga bog‘liq; juda ko‘p collision yuz bersa qidirish O(n)gacha yomonlashadi.

Afzalliklari

• O‘lcham bosqichma-bosqich o‘sadi. Har yangi element uchun node ajratiladi; oldindan katta uzluksiz hudud topish shart emas.
• Topilgan joyda uzish va ulash tez. Zarur node reference’lari tayyor bo‘lsa, elementlarni ko‘chirmasdan bir nechta bog‘lanish yangilanadi.
• Node reference’i barqaror bo‘lishi mumkin. Boshqa node’lar qo‘shilganda dynamic arraydagi qayta joylashishga o‘xshab barcha node’lar bitta yangi blokka ko‘chirilmaydi. Aniq barqarorlik xotira boshqaruvi va til modeliga bog‘liq.
• Turli bog‘lanish modellari mavjud. Faqat oldinga, ikki tomonga yoki halqa bo‘ylab yurish vazifaga mos tanlanadi.

Bu afzalliklarning har biri xarajatga ega: alohida xotira ajratish, reference’lar uchun joy, murakkabroq bog‘lanish invariantlari va sustroq cache ishlashi.

Cheklovlari

• Index orqali ixtiyoriy elementga bevosita kirib bo‘lmaydi.
• Oddiy qidirish va traversal O(n) vaqt oladi.
• Har node qiymatdan tashqari bir yoki ikki reference saqlaydi.
• Node’larning tarqoq joylashuvi CPU cache’dan foydalanishni yomonlashtirishi mumkin.
• Ko‘p mayda xotira ajratish va bo‘shatish qo‘shimcha xarajat hamda fragmentatsiyaga sabab bo‘lishi mumkin.
• Bog‘lanishlarni noto‘g‘ri yangilash ma’lumotning bir qismini yo‘qotishi yoki cheksiz sikl yaratishi mumkin.
• Binary search uchun mos emas, chunki o‘rtadagi elementga O(1) vaqtda kirish yo‘q.

Keng tarqalgan xatolar va nozik holatlar

Bo‘sh ro‘yxatni hisobga olmaslik

head = NULL bo‘lganda head.next yoki head.valuega murojaat qilib bo‘lmaydi. Traversal, o‘chirish va qidirish oldidan bo‘shlik tekshiriladi. Birinchi element qo‘shilganda head va tail bir node’ni ko‘rsatishi mumkin.

Bitta elementli ro‘yxat

Yagona node o‘chirilsa, ro‘yxat yana bo‘sh holatga qaytadi. Faqat headni tozalab, tailni eski node’da qoldirish ichki holatni buzadi. Circular ro‘yxatda esa bitta node’ning nexti ko‘pincha o‘zini ko‘rsatadi.

Bog‘lanishni juda erta almashtirish

current.next o‘zgartirilishidan oldin eski keyingi node kerak bo‘lsa, u vaqtinchalik reference’da saqlanishi shart. Aks holda ro‘yxatning qolgan qismiga yo‘l yo‘qoladi. Har bir o‘zgarishda “qaysi reference hali kerak?” degan savol berish foydali.

Head va tail’ni yangilamaslik

Birinchi yoki oxirgi node qo‘shilganda va o‘chirilganda ro‘yxatning tashqi reference’lari ham yangilanadi. O‘rtadagi node uchun to‘g‘ri ishlaydigan kod chekka node’larda xato berishi mumkin.

Doubly listda faqat bir tomonni yangilash

A ⇄ B ⇄ C ichidan B o‘chirilganda A.next = Cning o‘zi yetarli emas; C.previous = A ham bajarilishi kerak. Aks holda oldinga yurish to‘g‘ri ko‘rinsa-da, orqaga yurish o‘chirilgan node’ga kiradi. Doubly linked listning invarianti shuki, qo‘shni node’lar ikki yo‘nalishda bir-biriga mos kelishi kerak.

Circular ro‘yxatda noto‘g‘ri to‘xtash sharti

Circular ro‘yxatda next tabiiy ravishda NULL bo‘lmasligi mumkin. Traversal boshlang‘ich node’ga qaytilganda yoki oldindan belgilangan qadamlar soniga yetganda to‘xtashi kerak. Bo‘sh ro‘yxat alohida tekshirilmasa, boshlang‘ich node’ning o‘zi mavjud bo‘lmaydi.

Qiymat va node’ni adashtirish

Takroriy qiymatlar bo‘lishi mumkin:

[10] → [20] → [10] → NULL

“10 ni o‘chir” talabi birinchi mos node’nimi, barcha mos node’larnimi yoki aniq bir node’nimi — algoritm buni belgilashi kerak. Bir xil qiymatli node’lar xotirada alohida obyektlardir.

Tashqi reference’larning ta’siri

Node ro‘yxatdan uzilganidan keyin unga tashqi reference qolishi mumkin. Bu node hali mavjud bo‘lsa ham, endi ro‘yxatning a’zosi emas. Aksincha, node’ga yetib boruvchi yagona bog‘lanish tasodifan yo‘qotilsa, uning ortidagi butun zanjir ro‘yxatdan uzilishi mumkin.

Rekursiyada stack chegarasi

Rekursiv traversal qisqa ko‘rinadi, ammo har node uchun yangi funksiya chaqiruvi hosil qiladi. Juda uzun ro‘yxat call stackni to‘ldirishi mumkin. Oddiy traversal uchun iterativ yondashuv odatda xavfsizroq va O(1) yordamchi xotira ishlatadi.

Qachon ishlatish kerak?

Linked list quyidagi talablar ustun bo‘lganda mos kelishi mumkin:

• kerakli node’ga reference allaqachon mavjud va uning atrofida tez-tez qo‘shish yoki o‘chirish bajariladi;
• elementlar soni o‘zgaradi va ularni bitta uzluksiz xotira hududida saqlash talab qilinmaydi;
• ketma-ket faqat oldinga yoki ikki tomonga yurish yetarli;
• node’larni boshqa tuzilmalar, masalan, hash table bilan birga barqaror tartibda ulash kerak;
• circular navbat kabi oxiridan boshiga tabiiy qaytadigan model kerak.

Tanlovni tuzilmaning nomi emas, eng ko‘p bajariladigan operatsiya belgilaydi. “Tez-tez o‘chirish bor” degan jumla ham yetarli emas: o‘chiriladigan node qanday topilishi va oldingi node ma’lummi, shuni aniqlash kerak.

Qachon ishlatmaslik kerak?

Quyidagi vaziyatlarda boshqa tuzilma ko‘pincha yaxshiroq:

• Index bo‘yicha tez-tez kirish kerak bo‘lsa, array yoki dynamic array mosroq. Linked list har safar boshidan yuradi.
• Asosiy ish ketma-ket o‘qish bo‘lsa, array cache samaradorligi va kamroq xotira xarajati sababli odatda ustun.
• Kalit bo‘yicha tez qidirish kerak bo‘lsa, hash table; tartibli qidirish va diapazonlar kerak bo‘lsa, muvozanatlangan qidiruv daraxti ma’qul bo‘lishi mumkin.
• Faqat oxiriga qo‘shish va index orqali o‘qish kerak bo‘lsa, amortized O(1) append beradigan dynamic array odatda soddaroq va amalda tezroq. Amortized degani ayrim kengayishlar qimmat bo‘lsa ham, ko‘p qo‘shishlarning o‘rtacha taqsimlangan xarajati doimiy bo‘lishidir.
• Xotira juda cheklangan bo‘lsa, har bir node uchun reference va ajratish xarajati qimmat tushishi mumkin.
• Binary search kerak bo‘lsa, saralangan array mosroq, chunki o‘rtadagi elementga tez kiradi.
• Parallel ishlov berish ko‘p bo‘lsa, pointer bog‘lanishlarini xavfsiz o‘zgartirish murakkablashadi. Maxsus concurrent tuzilma yoki boshqa model talab qilinishi mumkin.

Stack va queue abstraksiyalarini linked list bilan qurish mumkin, lekin bu ularning yagona implementatsiyasi emas. Dynamic array yoki circular buffer amaliy talabga qarab yaxshiroq cache samaradorligi berishi mumkin.

Eng muhim xulosa

Linked list elementlarni xotirada yonma-yon joylashtirish orqali emas, node’lar orasidagi reference’lar orqali tartiblaydi. Shu sababli kerakli joy allaqachon topilgan bo‘lsa, node’ni qo‘shish yoki o‘chirish bir nechta bog‘lanishni almashtirish bilan O(1) vaqtda bajariladi. Ammo index bo‘yicha kirish va qidirish odatda O(n), har bir node esa qo‘shimcha reference xotirasini talab qiladi.

Singly linked list kamroq xotira bilan faqat oldinga yuradi. Doubly linked list ikki yo‘nalishda yurish va ma’lum node’ni tez uzishni qo‘shimcha reference evaziga beradi. Circular linked list esa oxirgi node’ni yana boshiga ulab, takrorlanuvchi navbatlarni tabiiy ifodalaydi.

Linked listni tanlashdan oldin uchta savol bering:

1. Kerakli node qanday topiladi?
2. Eng ko‘p bajariladigan amal index bo‘yicha kirishmi yoki topilgan joyda uzish-ulashmi?
3. Qo‘shimcha reference va sustroq cache ishlashi bu foydaga arziydimi?

Linked list node va reference’lar orqali chiziqli ketma-ketlik quradi. Keyingi tabiiy qadam — shu ketma-ketlikka amal bajarish qoidalarini qo‘shadigan stack va queue kabi abstrakt tuzilmalarni o‘rganishdir: ularda elementlarning qanday bog‘langani emas, qaysi tartibda qo‘shilib, qaysi tartibda olinishi markaziy masalaga aylanadi.