Muhammad al xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Ikki bog’lamli halqasimon ro’yxat. Ikki bog’lamli (ikki yo’nalishli) halqasimon ro’yxatning har bir elementi (tuguni) ikkita ko’rsatkichlar maydonidan iborat bo’lib, o’zidan oldingi (prev) va keyingi (next) elementlarning xotira adresini o’zida saqlaydi. Ro’yxatning bosh elementining prev ko’rsatkichi ro’yxat oxiri elementiga bog’lanadi, ro’yxat oxiri elementining next ko’rsatkichi ro’yxat boshi elementiga bog’lanadi

Ikki bog’lamli halqasimon ro’yxat

Ikki bog’lamli halqasimon ro’yxat elementini quyidagicha tuzilma ko’rinishida tavsiflanadi:
struct list {
int field; //ma’lumot maydoni
struct list *next; //keyingi elementga ko’rsatkich
struct list *prev; //oldingi elementga ko’rsatkich
};
Ikki bog’lamli halqasimon ro’yxat elementi ustida bajariladigan amallar:
– Ro’yxatni yaratish;
– Ro’yxatga yangi tugun qo’shish;
– Ro’yxatdan tugunni o’chirish;
– Ro’yxatga element qo’shish;
– Ro’yxat elementlarini teskari tartibda chiqarish;
– Ro’yxatning ikkita tugunini o’zaro almashtirish.
4. Ikki bog’lamli halqasimon ro’yxat (IBHR)ni yaratish. Ro’yxatni yaratish bosh (birinchi) tugunni yaratishdan boshlanadi, har bir tugun uchun oldingi va keyingi ko’rsatkichlar maydoni hosil qilinadi 

Ikki bog’lamli ro’yxatning bosh elementi

struct list * init(int a) { //a –tugun qiymati
struct list *lst;  //birinchi tugun uchun xotira ajratish
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->next = lst;// key ingi elementga ko’rsatkich
lst->prev = lst; // oldingi elementga ko’rsatkich
return(lst);
}
IBHR ga tugun qo’shish. IBHRga yangi tugun qo’shish funksiyasi oddiy ikki bog’lamli chiziqli ro’yxatdagiga o’xshash va ikkita argument qabul qilinadi:
– qo’shishdan keyin hosil bo’ladigan tugunga ko’rsatkich;
– qo’shilgan tugun uchun ma’lumot maydoni.
Yangi tugunni qo’shish prosedurasi quyidagi rasm asosida tasvirlash mumkin (12-rasm):

Yangi tugun qo’shish

IBHRga element qo’shish quyidagi bosqichlarda amalga oshiriladi:
– qo’shiladigan element uchun tugunni hosil qilish va uning maydonlarini ma’lumot bilan to’ldirish;
– “keyingi” tugunning prev ko’rsatkichini qo’shiladigan tugun uchun qayta o’rnatish;
– “oldingi” tugunning next ko’rsatkichini qo’shiladigan tugun uchun qayta o’rnatish;
– qo’shiladigan tugunning next ko’rsatkichini ro’yxatdagi keyingi tugunga o’rnatish;
– qo’shiladigan tugunning prev ko’rsatkichini ro’yxatdagi keyingi tugunga o’rnatish.
Ushbu bosqichlardan iborat yangi tugun qo’shish funksiyasi quyidagi ko’rinishda bo’ladi: