Ikki bog'lamli ro'yhat

Ikki bog'lamli ro'yhat
Ko’pgina masalalarni hal qilishda bir tomonga yo’naltirilgan ro’yhatlardan foydalanish ma'lum bir qiyinchiliklarni keltirib chiqaradi. Sababi, bir tomonga yo’naltirilgan ro’yhatda har doim bironta elementdan ro’yhatning so’ngi elementi tomoniga harakatlanish mumkin. Lekin ko’pgina masalalar hal qilinayotganda ma'lum bir elementni qayta ishlash uchun undan oldin kelgan elementga muroyaat qilish zarurati paydo bo’ladi. Ushbuholatda berilgan elementdan oldin kelgan elementga muroyaat qilish bir bog’lamli ro’yhatda noqulay va ancha sekin amalga oshiriladihamda uni amalga oshirish algoritmi murakkablashadi.
Ushba noqulayliklarni yo’qotish maqsadida ro’yhatning har bo’g’imiga yana bitta maydonqo’shiladi. Ushbu maydon qiymati o’zidan oldin kelgan bo’g’imga muroyaatdan iborat bo’ladi. Ushba ko’rinishdagi elementlardan tashkil topgan dinamik tuzilmaga ikkitomonlama yo’naltirilgan yokiikki bog’lamli ro’yhat deyiladi.
Ikki bog’lamli ro’yhatning har bir elementi ikkita ko’rsatkichga ega. Bittasi o’zidan oldingi elementga ko’rsatadi (teskari), ikkinchisi navbatdagi elementni ko’rsatadi (to’g’ri) (chizma).

Ikki bo’g’lamli ro’yhat ustidagi amallar:
- Ro’yhat elementini yaratish;
- ro’yhatda elementniqidirish;
- Ro’yhatning ko’rsatilgan yoyiga elemental qo’yish;
- berilgan elementni ro’yhatdan o’chirish.

Ushbu rasmda chiziqli ikki bog’lamli ro’yhat tuzilmasi keltirilgan. Unda roy’hat boshi va oxirini ko’rsatuvchi ikkita ko’rsatkich qabul qilingan, head va tail. Ushbu tuzilmani C++ tilida quyidagicha e’lon qilish mumkin:
Class Node{
int info;
Node *prev;
Node *next;
}
Ushbu yaratilgan nostandart toifada ro’yhat boshi ko’rsatkichini e’lon qilishimiz mumkin.
Node *head=new Node;
Ro’yhatga yangi elementni kiritish algoritmi
Bunning uchun yangi elementni yaratib ro’yhatga quyidagi qadamlar bilan ro’yhat oxiriga qo’shiladi:

• 
  Yangi element yaratiladi, uning 3 ta maydoni e’lon qilinadi.
  
• 
  info maydoniga el sonini kiritamiz;
  

• 
  next maydoniga NULL qiymat kiritamiz;
  
• 
  prev maydoniga tail ni qiymatini yozib qo’yamiz, chunki bu element oxirgi turgan elementdan keyinga qo’shiladi va prev maydoni bilan o’zidan oldingi elementni ko’rsatib turishi kerak. Undan oldin keladigan element (xozircha oxirgi element tail da ko’rsatilyapti) adresi tail da saqlanyapti.
  
• 
  Yangi element kiritilgach, tail ko’rsatkichni ushbu yangi elementga o’rnatamiz. Chunki endi oxirgi element bo’lib, yangi element hisoblanadi.
  
• 
  Qachonki, yana yangi element kiritiladigan bo’lsa, boya kiritilgan elementning next maydonidagi NULL ni o’rniga yangi kiritilayotgan elementning adresi yoziladi.
  

Ushbu aytilgan xarakatlarni quyidagi rasmda keltiramiz.

Ushbu algoritmni C++ dagi dastur kodini keltiramiz.



Ikki bog’lamli ro’yhat oxiridan elementni o’chirish algoritmi
Oxiridan element o’chirish amalida tail ko’rsatkich ko’rsatayotgan element o’chiriladi.Bunda undan oldingi turgan elementning next maydoniga NULL yozib qo’yiladi.Keyin element o’chiriladi.Quyidagi amallar ketma-keltligini bayaramiz.

• 
  O’chirilayotgan elementni prev maydonidagi adres bilan oldingi turgan element olinadi;
  
• 
  Uning next maydoniga NULL yoziladi;
  
• 
  O’chirilayotgan elementni xotiradan tozalash mumkin.
  

Bu algoritmni bayarishda shu narsaga axamiyat berish kerakki, tuzilma ustida amal bayarishda ro’yhat bo’sh yoki bo’sh emaslikka tekshirish kerak. Ya’ni quyidagicha:
if (!list.isEmpty())
n = list.deleteFromDLLTail();
elsedo not delete;