Tarkibga o'tish

Doubly linked list (ikki tomonlama bog‘langan ro‘yxat)

Musiqa pleyeridagi qo‘shiqlar ro‘yxatini yana bir bor eslang. Singly linked listda faqat “keyingi qo‘shiq”qa o‘tish mumkin edi. Endi foydalanuvchi “oldingi qo‘shiq”ni bosganini tasavvur qiling. Har bir node faqat nextni saqlasa, oldingi qo‘shiqqa qaytish uchun ro‘yxat boshidan boshlab, joriy qo‘shiqqacha yana yurishga to‘g‘ri keladi. Bu amaliy jihatdan noqulay: oddiy “orqaga qaytish” tugmasi uchun butun ro‘yxatni qayta aylanib chiqish shart emas.

Doubly linked list, ya’ni ikki tomonlama bog‘langan ro‘yxat, aynan shu muammoni hal qiladi. Har bir node nafaqat keyingi, balki oldingi node’ga ham reference saqlaydi:

NULL ← [10] ⇄ [20] ⇄ [30] → NULL

Bu singly linked list maqolasida ko‘rilgan model ustiga qurilgan kichik, ammo ta’sirchan qo‘shimcha. Bitta qo‘shimcha reference evaziga ro‘yxat bo‘ylab ikkala yo‘nalishda ham yurish, va muhimi, allaqachon qo‘lda bor node’ni ro‘yxatdan O(1) vaqtda uzib olish mumkin bo‘ladi.

Nega faqat “next” yetarli emas?

Singly linked listda C node’da turib, undan oldingi Bga qaytish kerak bo‘lsa, tayyor yo‘l yo‘q. Yagona chora — headdan boshlab, nexti C bo‘lgan node’ni topguncha yurish. Bu ayniqsa quyidagi ikkita amalda muammo tug‘diradi:

  • Berilgan node’ni o‘chirish. Node’ning o‘zini bilsak ham, uni zanjirdan chiqarish uchun undan oldingi node’ning nextini o‘zgartirish kerak. Oldingi node’ga reference bo‘lmasa, uni qidirishga to‘g‘ri keladi.
  • Orqaga qarab yurish. Undo tarixi, brauzer navigatsiyasi yoki musiqa pleyeri kabi vazifalarda ikkala yo‘nalish ham tabiiy ravishda kerak bo‘ladi.

Doubly linked list bu ikkala holatni ham previous reference’i orqali hal qiladi. Buning narxi bor: har bir node qo‘shimcha reference saqlaydi va har bir qo‘shish yoki o‘chirishda ikkita emas, to‘rtta bog‘lanishni to‘g‘ri yangilash kerak bo‘ladi.

Node modeli

Singly linked listdagi node’dan farqli o‘laroq, doubly linked listdagi node uchta qismdan iborat:

+----------+-----------+----------+
| previous |   value   |   next   |
+----------+-----------+----------+
  • previous — oldingi node’ga olib boruvchi reference; birinchi node’da bu NULL;
  • value — foydali ma’lumot;
  • next — keyingi node’ga olib boruvchi reference; oxirgi node’da bu NULL.

Ro‘yxatning o‘zi odatda uchta boshqaruv qiymatini saqlaydi:

list:
    head   → birinchi node
    tail   → oxirgi node
    length → node’lar soni (ixtiyoriy)

Singly turda tail ixtiyoriy edi, chunki uni saqlamasak ham, oxiriga yetish uchun oddiy traversal yetarli edi — faqat sekinroq. Doubly turda esa tail ko‘pincha shart hisoblanadi, chunki uning asosiy afzalliklaridan biri — ro‘yxat oxiridan orqaga yurish yoki oxiridan O(1) vaqtda o‘chirish — aynan tail orqali beriladi.

Xotirada qanday ishlaydi?

Node’lar singly turdagi kabi xotiraning turli joylarida joylashishi mumkin. Farq shundaki, har bir node endi ikki yo‘nalishga reference saqlaydi:

head = 4000                                              tail = 7700

Manzil 4000                  Manzil 9200                 Manzil 7700
+------+------+------+       +------+------+------+      +------+------+------+
| NULL |  10  | 9200 | ----> | 4000 |  20  | 7700 | ----> | 9200 |  30  | NULL |
+------+------+------+       +------+------+------+      +------+------+------+
  prev  value  next            prev  value  next           prev  value  next

20 qiymatli node’dan next orqali 30ga, previous orqali esa 10ga qaytish mumkin. Ikkala yo‘nalish ham bog‘lanishlar orqali ifodalangan; xotiradagi jismoniy joylashuv mantiqiy tartibga bevosita ta’sir qilmaydi.

Har bir node qo‘shimcha reference saqlagani uchun doubly linked listning doimiy xotira xarajati singly turdan kattaroq:

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

Ikkalasi ham Big O nuqtai nazaridan O(n), ammo doubly listning har bir node’i amalda ko‘proq joy egallaydi. Bu — qo‘shimcha yo‘nalish evaziga to‘lanadigan narx.

Asosiy invariant

Doubly linked listning to‘g‘ri ishlashi bitta qoidaga tayanadi: agar A.next = B bo‘lsa, B.previous ham albatta Ani ko‘rsatishi kerak. Ikki yo‘nalish doim bir-biriga mos kelishi shart.

[A] ⇄ [B]

A.next = B
B.previous = A     ← ikkalasi ham to‘g‘ri bo‘lishi shart

Amalda bu shuni anglatadiki, har qanday qo‘shish yoki o‘chirish amalida bog‘lanishni faqat bitta tomondan yangilash yetarli emas. Quyidagi bo‘limlarda ko‘rinadiki, bitta amalda odatda ikki emas, to‘rttagacha reference yangilanadi — ikkitasi next yo‘nalishida, ikkitasi previous yo‘nalishida.

Asosiy amallar

Quyida head, tail va length saqlanadi deb faraz qilinadi.

Bo‘sh ro‘yxat yaratish

head = NULL
tail = NULL
length = 0

O(1) vaqt va O(1) xotira, chunki node’lar sonidan qat’i nazar faqat bir nechta boshqaruv qiymati yaratiladi.

Oldinga va orqaga traversal

FUNCTION TRAVERSE_FORWARD(head)
    current = head

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

FUNCTION TRAVERSE_BACKWARD(tail)
    current = tail

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

Ikkala yo‘nalish ham O(n) vaqt va O(1) qo‘shimcha xotira talab qiladi. Farq shundaki, singly linked listda faqat birinchi funksiya mumkin edi; orqaga yurish uchun butun ro‘yxatni saqlaydigan qo‘shimcha tuzilma kerak bo‘lardi. Doubly turda orqaga yurish tayyor previous reference’i tufayli qo‘shimcha tuzilmasiz amalga oshadi.

Boshiga element qo‘shish

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

    IF list.head != NULL
        list.head.previous = new_node

    list.head = new_node

    IF list.tail = NULL
        list.tail = new_node

    list.length = list.length + 1

Singly turdagi PREPENDdan farqi — list.head.previous = new_node qatori. Eski head endi yagona emas, uning previousi ham yangi node’ga yo‘naltirilishi kerak. Bu qadam tashlab ketilsa, orqaga yurishda yangi node’ga hech qachon qaytib bo‘lmaydi, garchi oldinga yurish to‘g‘ri ishlayotgandek ko‘rinsa ham.

Vaqt O(1), chunki ro‘yxat kattaligidan qat’i nazar bir xil miqdordagi reference yangilanadi. Yangi node uchun O(1) qo‘shimcha xotira ajratiladi.

Oxiriga element qo‘shish

FUNCTION APPEND(list, value)
    new_node = NEW NODE(value)
    new_node.next = NULL
    new_node.previous = list.tail

    IF list.tail != NULL
        list.tail.next = new_node

    list.tail = new_node

    IF list.head = NULL
        list.head = new_node

    list.length = list.length + 1

tail mavjud bo‘lgani uchun oxirgi node’ni qidirish shart emas — vaqt O(1). Bu jihatdan singly va doubly linked list bir xil, agar ikkalasi ham tail saqlasa. Farq oxiridan o‘chirishda ko‘rinadi.

Ma’lum node’dan oldin yoki keyin qo‘shish

Reference node orqali berilgan bo‘lsa, undan keyin qo‘shish:

FUNCTION INSERT_AFTER(list, node, value)
    new_node = NEW NODE(value)
    new_node.previous = node
    new_node.next = node.next

    IF node.next != NULL
        node.next.previous = new_node
    ELSE
        list.tail = new_node

    node.next = new_node
    list.length = list.length + 1

Oldin:  [10] ⇄ [30]

Keyin:  [10] ⇄ [20] ⇄ [30]

To‘rtta bog‘lanish yangilanadi: yangi node’ning previous va nexti, undan oldingi node’ning nexti, undan keyingi node’ning previousi. Agar node ro‘yxatning oxirgisi bo‘lsa, list.tail ham yangilanishi shart, aks holda tail eski oxirgi node’ni ko‘rsatib qoladi.

Warning

Bog‘lanishlarni yangilash tartibi muhim. node.nextni yangi node’ga o‘tkazishdan oldin node.next.previousni yangi node’ga yo‘naltirish kerak — aks holda eski keyingi node’ga olib boruvchi yagona yo‘l yo‘qoladi.

Vaqt O(1), chunki node allaqachon berilgan. Agar node index yoki qiymat orqali topilishi kerak bo‘lsa, uni topish alohida O(n) xarajat qo‘shadi — bu joyni topish narxi bilan ulash narxini ajratishning yana bir misoli.

Ma’lum node’ni o‘chirish

Bu yerda doubly linked listning eng katta amaliy foydasi ko‘rinadi: node’ning o‘zi berilgan bo‘lsa, oldingi node’ni qidirish shart emas, chunki u previous orqali darhol ma’lum:

FUNCTION REMOVE_NODE(list, node)
    IF node.previous != NULL
        node.previous.next = node.next
    ELSE
        list.head = node.next

    IF node.next != NULL
        node.next.previous = node.previous
    ELSE
        list.tail = node.previous

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

Oldin:  [10] ⇄ [20] ⇄ [30]

20 o'chirilmoqda:
[20].previous.next = [20].next     → 10.next = 30
[20].next.previous = [20].previous → 30.previous = 10

Keyin:  [10] ⇄ [30]

Vaqt O(1). Solishtirish uchun: singly linked listda xuddi shu amal uchun nodedan oldingi node’ga reference kerak bo‘lardi, u esa odatda alohida qidirishni talab qiladi — natijada O(n). Bu farq doubly linked listni tanlashning asosiy sabablaridan biridir: kerakli node allaqachon qo‘lda bo‘lganda, uni zanjirdan chiqarish qo‘shni node’larni qidirmasdan bajariladi.

To‘rtta shart alohida ko‘rib chiqiladi: node ro‘yxat boshi bo‘lishi mumkin (previous = NULL), oxiri bo‘lishi mumkin (next = NULL), yoki ikkalasi ham — bitta elementli ro‘yxatda. Shartlarning istalganini o‘tkazib yuborish head yoki tailni noto‘g‘ri holatda qoldiradi.

Oxiridan o‘chirish

FUNCTION REMOVE_LAST(list)
    IF list.tail = NULL
        RETURN XATO

    RETURN REMOVE_NODE(list, list.tail)

tail.previous yangi oxirgi node’ni darhol ko‘rsatgani uchun bu amal O(1). Singly linked listda xuddi shu amal uchun yangi tail bo‘ladigan node’ni topish uchun boshidan yurish kerak edi, ya’ni O(n). Bu — ikkinchi reference saqlashning aniq mevasi: singly turda faqat oldinga qo‘shish tez bo‘lsa, doubly turda ikkala chetdan ham qo‘shish va o‘chirish O(1) bo‘ladi.

Qidirish

FUNCTION FIND(head, target)
    current = head

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

        current = current.next

    RETURN TOPILMADI

Qidirishning o‘zi singly linked listdagi bilan bir xil: eng yaxshi holat O(1), eng yomon holat O(n), chunki previous reference’i qidiruv yo‘nalishini emas, faqat orqaga qaytish imkoniyatini beradi. Maqsadli qiymat ro‘yxatning oxiriga yaqinroq ekani oldindan ma’lum bo‘lsa, taildan orqaga qidirish amaliy jihatdan tezroq tugashi mumkin, ammo eng yomon holat baribir O(n) bo‘lib qoladi.

Vaqt va xotira murakkabligi

Amal Doubly linked list Nega?
Boshidagi yoki oxiridagi elementni olish O(1) head va tail bevosita ko‘rsatadi
Index bo‘yicha kirish O(n) Bog‘lanishlar bo‘ylab yurish kerak
Qiymat bo‘yicha qidirish O(n) Eng yomon holatda barcha node tekshiriladi
Boshiga yoki oxiriga qo‘shish O(1) head va tail orqali darhol ulanadi
Ma’lum node’dan oldin yoki keyin qo‘shish O(1) Joy allaqachon topilgan, to‘rtta bog‘lanish yangilanadi
Ma’lum node’ni o‘chirish O(1) previous orqali qo‘shni node qidirilmasdan topiladi
Oxiridan o‘chirish O(1) tail.previous yangi tail’ni darhol beradi
To‘liq traversal (ikkala yo‘nalishda ham) O(n) Har bir node bir marta ko‘riladi

Jadvaldagi O(1) natijalar kerakli node’ga reference oldindan mavjud bo‘lganda to‘g‘ri keladi. Node index yoki qiymat orqali topilishi kerak bo‘lsa, uni topishning o‘zi O(n), ulash esa shundan keyin O(1) bo‘ladi.

Xotira murakkabligi n ta element uchun O(n), ammo doimiy koeffitsient singly linked listdan kattaroq: har bir node ikkita reference saqlaydi. Iterativ amallar O(1) qo‘shimcha xotira ishlatadi.

Singly va doubly linked list taqqoslanishi

Xususiyat Singly linked list Doubly linked list
Har node’dagi reference soni 1 (next) 2 (previous, next)
Orqaga yurish Yo‘q Bor
Berilgan node’ni o‘chirish (node ma’lum) O(n) (oldingisi qidiriladi) O(1)
Oxiridan o‘chirish (tail bilan) O(n) O(1)
Har node uchun qo‘shimcha xotira Kamroq Ko‘proq
Bog‘lanishlarni to‘g‘ri saqlash murakkabligi Nisbatan sodda Ikki yo‘nalishni muvofiqlashtirish kerak

Bu taqqoslash shuni ko‘rsatadiki, doubly linked list singly turning “yaxshilangan versiyasi” emas — u boshqa almashinuv taklif qiladi. Orqaga yurish va berilgan node’ni tez o‘chirish kerak bo‘lmasa, qo‘shimcha reference foydasiz xotira xarajatidan boshqa narsa emas.

Real qo‘llanishlar

LRU cache

LRU (least recently used) cache sig‘imi to‘lganda eng uzoq vaqt ishlatilmagan yozuvni chiqarib tashlaydi. Doubly linked list foydalanish tartibini saqlaydi: yozuv o‘qilganda uning node’i ro‘yxat boshiga ko‘chiriladi, sig‘im to‘lganda esa tail chiqariladi. Hash table kalitdan node’ga tez yetkazadi, doubly linked list esa topilgan node’ni joyidan O(1) vaqtda uzib, boshqa joyga ulash imkonini beradi. Aynan shu “node ma’lum, uni tez ko‘chirish kerak” talabi doubly linked listni singly turdan afzal qiladi: singly turda node’ni uzish uchun undan oldingi node ham kerak bo‘lardi.

Brauzer tarixi va undo/redo

Orqaga va oldinga tugmalari bor har qanday tizim — brauzer tarixi, matn muharriridagi undo/redo, slayd taqdimotidagi navigatsiya — ikki yo‘nalishli harakatni talab qiladi. Joriy holatning previousi orqaga, nexti oldinga olib boradi. Foydalanuvchi undo qilgandan keyin yangi amal bajarsa, odatda oldingi redo tarmog‘i bekor qilinadi va chiziqli tarix davom etadi. Tarmoqlanadigan (branching) tarix kerak bo‘lsa, bu vazifa uchun tree ko‘proq mos keladi.

Musiqa yoki video pleyeri navbati

Qo‘shiq yoki video navbatida foydalanuvchi ham oldinga, ham orqaga o‘tishi mumkin. Joriy elementga reference tayyor bo‘lgani uchun “keyingisi” va “oldingisi” tugmalari O(1) vaqtda ishlaydi. Navbat o‘rtasidan bitta qo‘shiq o‘chirilsa, uning qo‘shnilari qidirilmasdan qayta ulanadi.

Matn muharriridagi kursor atrofi

Ayrim matn tuzilmalarida kursor atrofidagi belgilar yoki so‘zlarga tez kirish va ularni tez o‘zgartirish kerak bo‘ladi. Doubly bog‘lanish orqa va old tomonga tez siljishni beradi, ammo katta hajmdagi matn uchun amalda rope yoki piece table kabi murakkabroq tuzilmalar ko‘proq ishlatiladi. Bu yerda doubly linked list ko‘proq tushunchani tushuntiruvchi model, aynan implementatsiyaning o‘zi emas.

Afzalliklari

  • Ikkala yo‘nalishda ham yurish mumkin. Orqaga qaytish uchun ro‘yxatni boshidan qayta aylanib chiqish shart emas.
  • Berilgan node’ni o‘chirish O(1). Oldingi node’ni qidirish kerak emas, chunki previous uni darhol beradi.
  • Ikkala chetdan ham O(1) qo‘shish va o‘chirish. head va tail orqali ro‘yxat boshi va oxiri bir xil tezlikda boshqariladi.

Bu afzalliklarning har biri qo‘shimcha reference va murakkabroq bog‘lanish mantig‘i evaziga keladi.

Cheklovlari

  • Har bir node singly turga nisbatan qo‘shimcha reference saqlaydi, bu xotira xarajatini oshiradi.
  • Har bir qo‘shish yoki o‘chirishda ko‘proq bog‘lanish yangilanadi, bu esa xatoga yo‘l qo‘yish ehtimolini oshiradi.
  • Index bo‘yicha bevosita kirish hamon yo‘q; bu cheklov singly linked listdan meros qolgan.
  • Node’larning tarqoq joylashuvi tufayli CPU cache samaradorligi array bilan solishtirganda odatda pastroq.

Keng tarqalgan xatolar va nozik holatlar

Faqat bir tomonni yangilash

Eng ko‘p uchraydigan xato — nextni yangilab, previousni unutish yoki aksincha. Natijada ro‘yxat bir yo‘nalishda to‘g‘ri, ikkinchi yo‘nalishda esa noto‘g‘ri ko‘rinadi:

A.next = C   ← bajarildi
C.previous = A   ← unutildi

Oldinga: A → C            (to'g'ri ko'rinadi)
Orqaga:  C → B → A         (hali eski B ga olib boradi)

Har bir o‘zgarishda “bu bog‘lanishning ikkala tomoni ham yangilandimi?” degan savol berish foydali.

Chekka holatlarni unutish

Node ro‘yxatning boshi yoki oxiri bo‘lganda, node.previous yoki node.next NULL bo‘ladi. REMOVE_NODE funksiyasidagi kabi shartlar aynan shu holatlar uchun kerak — ularsiz NULL.nextga murojaat qilishga urinish xato beradi.

Bitta elementli ro‘yxat

Yagona node o‘chirilganda, head ham, tail ham NULL bo‘lishi kerak. Faqat bittasini yangilash ro‘yxatni nomuvofiq holatga olib keladi — masalan, head = NULL, lekin tail hali eski node’ni ko‘rsatib turishi mumkin.

Circular doubly linked list bilan aralashtirish

Doubly linked listning circular varianti ham mavjud, unda head.previous tail’ga, tail.next esa head’ga ulanadi. Oddiy (circular bo‘lmagan) doubly linked listda esa head.previous va tail.next doim NULL bo‘lishi kerak. Ikkala modelni aralashtirib yozish traversalda cheksiz siklga olib kelishi mumkin.

Qachon ishlatish kerak?

Doubly linked list quyidagi talablar mavjud bo‘lganda mos keladi:

  • ro‘yxat bo‘ylab ikkala yo‘nalishda ham yurish kerak;
  • allaqachon qo‘lda bor node’ni tez-tez zanjirdan chiqarish kerak (masalan, LRU cache’dagi kabi);
  • ro‘yxatning ikkala chetidan ham tez-tez qo‘shish va o‘chirish bajariladi.

Qachon ishlatmaslik kerak?

  • Faqat oldinga yurish yetarli bo‘lsa, singly linked list kamroq xotira bilan xuddi shu vazifani bajaradi.
  • Index bo‘yicha tez-tez kirish kerak bo‘lsa, array yoki dynamic array ancha mosroq.
  • Xotira juda cheklangan bo‘lsa, qo‘shimcha previous reference’i sezilarli xarajat bo‘lishi mumkin.
  • Asosiy ish ketma-ket o‘qish bo‘lsa, array cache samaradorligi tufayli odatda amalda tezroq ishlaydi.

Eng muhim xulosa

Doubly linked list singly linked list modeliga bitta qo‘shimcha reference — previous — qo‘shadi. Bu qo‘shimcha reference orqaga yurish va berilgan node’ni O(1) vaqtda o‘chirish imkonini beradi, ammo har bir node ko‘proq xotira egallaydi va har bir o‘zgarishda ko‘proq bog‘lanishni to‘g‘ri yangilash kerak bo‘ladi.

Ikkala tur ham index bo‘yicha kirish va qiymat bo‘yicha qidirishda bir xil O(n) chegaraga ega — qo‘shimcha reference bu cheklovni yo‘qotmaydi, faqat orqaga yurish va zanjirdan chiqarishni tezlashtiradi.

Endi node’lar va bog‘lanishlar qanday ishlashini bilib oldik. Navbatdagi qadam — shu bilimni amaliy masalalarga qo‘llash: ro‘yxatning o‘rtasini topish, uni teskari aylantirish, ichida tsikl bor-yo‘qligini aniqlash va shunga o‘xshash klassik masalalarni yechish orqali linked list ustida fikrlashni mustahkamlash.