Bir bog‘lamli ro‘yxatlar ustida amallar va ularning algoritmlari

BIR MARTA BOG'LANGAN RO'YXAT

Yagona bog'langan ro'yxat ketma-ket bog'langan tugunlar to'plami bo'lib, unda yakka bog'langan ro'yxatning har bir tugunida ma'lumotlar maydoni va keyingi tugunning havolasini o'z ichiga olgan manzil maydoni mavjud.
Yagona bog'langan ro'yxatdagi tugunning tuzilishi.

Tugunlar bir-biriga ushbu shaklda ulanadi, bu erda oxirgi tugunning keyingi o'zgaruvchisi qiymati NULL, ya'ni keyingi = NULL, bu bog'langan ro'yxatning oxirini ko'rsatadi.

Yagona bog'langan ro'yxat - bu bir tomonlama bo'lgan bog'langan ro'yxat turi , ya'ni uni boshidan oxirgi tugun (dum)gacha faqat bitta yo'nalishda kesib o'tish mumkin.
Bog'langan ro'yxatdagi har bir element tugun deb ataladi. Bitta tugun ma'lumotlar va keyingi tugunga ko'rsatgichni o'z ichiga oladi , bu ro'yxatning tuzilishini saqlashga yordam beradi.
Birinchi tugun bosh deb ataladi. U ro'yxatning birinchi tuguniga ishora qiladi va bizga ro'yxatdagi har bir boshqa elementga kirishga yordam beradi. Oxirgi tugun, ba'zan tail deb ham ataladi, NULL ga ishora qiladi, bu bizga ro'yxat qachon tugashini aniqlashda yordam beradi.
Ruyhat elementlariga murojat faqat ruyhatning oldidan amalga oshiriladi. Teskaridan kirib bulmaydi.
Ruyhat elementlari ketma ket bog’langan bulmasin tuzulmani tashkil etsada, ular xotirada tartibsiz joylashgan bo’ladi.

Umumiy bir-biriga bog'langan ro'yxat operatsiyalari:

• 
  Ro'yxatdagi tugunni qidirish
  
• 
  Ro'yxatga tugun qo’shish
  
• 
  Ro'yxatdan tugunni olib tashlang
  

Muayyan tugunni old tomondan, oxiridan yoki ro'yxatning istalgan joyidan aniqlashingiz va olishingiz mumkin. Ro'yxatning istalgan joyidan tugunni olish uchun eng yomon holat Vaqt murakkabligi O(n) dir .

Siz tugunni old, oxirida yoki bog'langan ro'yxatning istalgan joyiga qo'shishingiz mumkin.
Ushbu operatsiyalarni bajarish uchun eng yomon vaqt murakkabligi quyidagicha:

• 
  Roʻyxatning old qismiga element qoʻshing: O(1)
  
• 
  Roʻyxat oxiriga element qoʻshing: O(n)
  
• 
  Roʻyxatning istalgan joyiga element qoʻshing: O(n)
  

Siz tugunni oldidan, oxiridan yoki roʻyxatning istalgan joyidan olib tashlashingiz mumkin.
Ushbu operatsiyani bajarish uchun eng yomon holat Vaqt murakkabligi quyidagicha:

• 
  Roʻyxatning oldingi elementini olib tashlang: O(1)
  
• 
  Roʻyxat oxiridagi elementni olib tashlang: O(n)
  
• 
  Roʻyxatning istalgan joyidan elementni olib tashlang: O(n)
  

Bir bog’lamli ro’yhatning ishlash strukturasi:

#include using namespace std; // Int ma'lumotlari va ko'rsatgichni o'z ichiga olgan tugun strukturasini yaratish // keyingi node struct Node { int data;