Mirzo Ulugʻbek nomidagi Oʻzbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

Bogʻlangan roʻyxatlar. Bogʻlangan roʻyxatlar eng koʻp tarqalgan dinamik tuzilmalardan xisoblanadi.
Ma'lumotlarni mantiqiy tasvirlash nuqtayi nazaridan roʻyxatlar ikkitaga ajratiladi: Chiziqli va chiziqsiz.
Chiziqli roʻyxatlarda elementlar orasidagi bogʻliqlik qat'iy tartiblangan boʻladi, ya'ni element koʻrsatkichi oʻzidan navbatdagi element adresini oʻz ichiga oladi yoki aksincha. Chiziqli roʻyxatlarga bir va ikki bogʻlamli roʻyxatlar kiradi. Chiziqsiz roʻyxatlarga esa koʻp bogʻlamli roʻyxatlar kiradi. Umuman olganda roʻyxat elementi bir yoki bir necha koʻrsatkichlar yozuvi maydonini namoyish qiladi.
Bir bogʻlamli roʻyxatlar
Bir bogʻlamli roʻyxat elementi ikkita maydonga ega (chizma): informatsion maydon (INFO) va koʻrsatkich maydoni (PTR).



1.2-chizma. Bir bogʻlamli roʻyxat
Bir bogʻlamli roʻyxatda koʻrsatkichni oʻziga xosligi shundan iboratki, bunda faqatgina oʻzidan keyin keluvchi roʻyxat elementi adresini koʻrsatadi. Roʻyxat eng soʻngi elementining koʻrsatkich maydoni boʻsh boʻladi (NIL). LST - roʻyxat boshiga koʻrsatkich. Umuman olganda roʻyxat boʻsh ham boʻlishi mumkin, bu holda LST NIL bilan ustma-ust tushadi, ya'ni teng boʻladi. Roʻyxat elementiga murojat faqatgina roʻyxat boshidan amalga oshiriladi, ya'ni bu roʻyxatda teskari aloqa yoʻq.
Halqasimon bir bogʻlamli roʻyxat. Halqasimon bir bogʻlamli roʻyxat oddiy bir bogʻlamli roʻyxatda eng soʻngi element koʻrsatkichiga roʻyxat boshi elementi koʻrsatkichi qiymatini oʻzlashtirish orqali xosil qilinadi (chizma).

1.3-chizma. Halqasimon bir bogʻlamli roʻyxat

Koʻpgina masalalarni hal qilishda bir tomonga yoʻnaltirilgan roʻyxatlardan foydalanish ma'lum bir qiyinchiliklarni keltirib chiqaradi. Sababi, bir tomonga yoʻnaltirilgan roʻyxatda har doim roʻyxatda bosh boʻgʻimdan roʻyxatning soʻngi boʻgʻimi tomoniga xarakatlanish mumkin holos. Lekin koʻpgina masalalar hal qilinayotganda ma'lum bir elementni qayta ishlash uchun undan oldin kelgan elementga murojaat qilish zarurati paydo boʻladi. Ushbu holatda berilgan elementdan oldin kelgan elementga murojaat qilish bir bogʻlamli roʻyxatda noqulay va ancha sekin amalga oshiriladi xamda uni amalga oshirish algoritmi murakkablashadi.
Ushbu noqulayliklarni yoʻqotish maqsadida roʻyxatning har bir boʻgʻimiga yana bitta maydon qoʻshiladi. Ushbu maydon qiymati oʻzidan oldin kelgan boʻgʻimga murojaatdan iborat boʻladi. Ushbu koʻrinishdagi elementlardan tashkil topgan dinamik tuzilmaga ikkitomonlama yoʻnaltirilgan yoki ikki bogʻlamli roʻyxat deyiladi.
Ikki bogʻlamli roʻyxatning har bir elementi ikkita koʻrsatkichga ega. Bittasi oldingi elementga koʻrsatadi (teskari), ikkinchisi navbatdagi elementni koʻrsatadi (toʻgʻri) (chizma).

1.4-chizma. Ikki bogʻlamli roʻyxat.

Umuman olganda, ikki bogʻlamli roʻyxat bu elementlari soni bir xil faqatgina teskari ketma-ketlikda yozilgan ikkita bir bogʻlamli roʻyxatdir.