Bog‘langan ro‘yxatlar
Bog‘langan list, so‘zdan ko‘rinib turibdiki, tugunlar bir-biriga bog‘langan ro‘yxatdir. Har bir tugun ma’lumotlar va ko‘rsatgichni o‘z ichiga oladi. Ularning bir-biriga bog‘langanligi shundaki, har bir tugun keyingi tugunning xotirada joylashgan joyiga ishora qiladi.
Bog‘langan listlar
Bog‘langan list qandaydir ma’lumotlarga ega bo‘lgan tugunlardan va keyingi tugunga ko‘rsatgich yoki havoladan iborat.
Bog‘langan listlar va massivlar
Bog‘langan listlarni tushunishning eng oson yo‘li, ehtimol, bog‘langan listlarni massivlar bilan solishtirishdir.
Bog‘langan listlar tugunlardan iborat bo‘lib, biz foydalanishimiz mumkin bo‘lgan dasturlash tilida mavjud ma’lumotlar strukturasi bo‘lgan massivlardan farqli o‘laroq, biz o‘zimiz yaratadigan chiziqli ma’lumotlar strukturasidir.
Bog‘langan ro‘yxatdagi tugunlar boshqa tugunlarga havolalarni saqlaydi, lekin massiv elementlari boshqa elementlarga havolalarni saqlashi shart emas.
Eslatma: Bog‘langan listlar va massivlar xotirada qanday saqlanishi Xotiradagi bog‘langan listlar sahifasida batafsil tavsiflangan.
Quyidagi jadval bog‘langan listlar nima ekanligini yaxshiroq tushunish uchun massivlar bilan bog‘langan listlarni taqqoslaydi.
| Massivlar | Bog‘langan listlar | |
|---|---|---|
| Dasturlash tilida mavjud ma’lumotlar strukturasi | Ha | Yo‘q |
| Xotirada qat’iy belgilangan hajm | Ha | Yo‘q |
| Elementlar yoki tugunlar xotirada ketma-ket (uzluksiz) saqlanadi | Ha | Yo‘q |
| Xotira sarfi kam (har bir tugun faqat ma’lumotni saqlaydi, boshqa tugunlarga havolalar yo‘q) |
Ha | Yo‘q |
| Elementlar yoki tugunlarga to‘g‘ridan-to‘g‘ri murojaat qilish mumkin (random access) | Ha | Yo‘q |
| Elementlar yoki tugunlar doimiy vaqtda kiritilishi yoki o‘chirilishi mumkin, xotirada o‘zgartirish operatsiyalari kerak emas. | Yo‘q | Ha |
Bular massivlar bilan solishtirganda ba’zi asosiy bog‘langan list xususiyatlari:
- Bog‘langan listlar massivlar kabi xotirada qat’iy belgilangan hajmga ajratilmaydi, shuning uchun bog‘langan listlar qattiq xotira maydoni to‘ldirilganda butun listni kattaroq xotira maydoniga ko‘chirishni talab qilmaydi, masalan, massivlar.
- Bog‘langan list tugunlari xotirada birin-ketin joylashtirilmaydi (birin-ketin), shuning uchun tugunlar kiritilganda yoki o‘chirilganda bog‘langan list tugunlari xotirada yuqoriga yoki pastga siljishi shart emas.
- Bog‘langan list tugunlari boshqa tugunlarga bir yoki bir nechta havolalarni saqlash uchun ko‘proq xotira talab qiladi. Massiv elementlari u qadar ko‘p xotirani talab qilmaydi, chunki massiv elementlari boshqa elementlarga havolalarni o‘z ichiga olmaydi.
- Bog‘langan list operatsiyalarini dasturlash odatda qiyinroq va shunga o‘xshash massiv operatsiyalariga qaraganda ko‘proq stringlarni talab qiladi, chunki dasturlash tillari massivlarni qo‘llab-quvvatlashda yaxshiroq qurilgan.
- Muayyan pozitsiyada tugunni topish uchun biz bog‘langan listni aylanib o‘tishimiz kerak, lekin massivlar bilan biz myArray[5] ni yozish orqali to‘g‘ridan-to‘g‘ri elementga kira olamiz.
Bog‘langan listlar turlari
Bog‘langan listlarning uchta asosiy shakli mavjud:
- Bir-biriga bog‘langan listlar
- Ikki marta bog‘langan listlar
- Doiraviy bog‘langan listlar
Yagona bog‘langan list bog‘langan listlarning eng oddiy turidir. U xotirada kamroq joy egallaydi, chunki har bir tugun quyidagi rasmdagi kabi keyingi tugunning faqat bitta manziliga ega.
Ikki marta bog‘langan list quyidagi rasmda bo‘lgani kabi oldingi va keyingi tugunning manzillari bo‘lgan tugunlarga ega va shuning uchun ko‘proq xotirani egallaydi. Ammo ikki marta bog‘langan listlar, agar siz listda yuqoriga va pastga siljishni istasangiz yaxshi bo‘ladi.
Doiraviy bog‘langan list birinchi tugun "bosh" va oxirgi tugun "dum" bilan bog‘langan bir yoki ikki marta bog‘langan listga o‘xshaydi.
Yakka yoki ikki marta bog‘langan listlarda biz havolalar null yoki yo‘qligini tekshirish orqali listning boshi va oxirini topishimiz mumkin. Ammo dumaloq bog‘langan listlar uchun ma’lum ilovalarda boshlang‘ich va tugun tugunlarini aniq tekshirish uchun murakkabroq kod kerak bo‘ladi.
Doiraviy bog‘langan listlar siz doimiy ravishda aylanib chiqishingiz kerak bo‘lgan listlar uchun yaxshi.
Quyidagi rasm bitta dumaloq bog‘langan listning namunasidir:
Quyidagi rasmda ikkilangan dumaloq bog‘langan listning namunasi keltirilgan:
Eslatma: Sizga qanday bog‘langan list kerakligi siz hal qilmoqchi bo‘lgan muammoga bog‘liq.
Bog‘langan list operatsiyalari
Bog‘langan listlar bilan biz qila oladigan asosiy narsalar:
- O‘tish
- Tugunni olib tashlang
- Tugunni kiriting
- Saralash
Oddiylik uchun quyida ushbu operatsiyalarni tushuntirish uchun alohida bog‘langan ro‘yxatlardan foydalaniladi.
Bog‘langan listni o‘tkazish
Bog‘langan list bo‘ylab o‘tish bir tugundan ikkinchisiga havolalarni kuzatib, bog‘langan list bo‘ylab o‘tishni anglatadi.
Bog‘langan listlar bo‘ylab harakatlanish odatda ma’lum bir tugunni qidirish va tugun tarkibini o‘qish yoki o‘zgartirish, tugunni olib tashlash yoki tugunni shu tugun oldidan yoki undan keyin kiritish uchun amalga oshiriladi.
Yagona bog‘langan listni aylanib o‘tish uchun biz ro‘yxatdagi birinchi tugun, bosh tugundan boshlaymiz va keyingi manzil null bo‘lgunga qadar ushbu tugunning keyingi havolasini va keyingi tugunning keyingi havolasini va hokazolarni kuzatib boramiz.
Quyidagi kod yuqoridagi animatsiya kabi bog‘langan list bo‘ylab harakatlanayotganda tugun qiymatlarini chop etadi.
Misol
Python-da bitta bog‘langan listni o‘tkazish:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
traverseAndPrint(node1)
Misolni ishga tushirish »
Bog‘langan ro‘yxatdagi eng past qiymatni toping
Keling, bitta bog‘langan ro‘yxatdagi eng past qiymatni uni kesib o‘tish va har bir qiymatni tekshirish orqali topamiz.
Bog‘langan ro‘yxatdagi eng kichik qiymatni topish massivdagi eng kichik qiymatni topishga juda o‘xshaydi, faqat keyingi tugunga o‘tish uchun next havolasini kuzatib borish kerak bo‘ladi.
Eng past qiymatni topish uchun oldingi koddagi kabi listni aylanib o‘tishimiz kerak. Ammo listni aylanib o‘tishdan tashqari, biz pastroq qiymatga ega bo‘lgan tugunni topganimizda joriy eng past qiymatni ham yangilashimiz kerak.
Quyidagi kodda eng past qiymatni topish algoritmi findLowestValue deb nomlangan funksiyaga o‘tkaziladi.
Misol
Python-da bitta bog‘langan ro‘yxatdagi eng past qiymatni topish:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findLowestValue(head):
minValue = head.data
currentNode = head.next
while currentNode:
if currentNode.data < minValue:
minValue = currentNode.data
currentNode = currentNode.next
return minValue
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("The lowest value in the linked list is:", findLowestValue(node1))
Misolni ishga tushirish »
Bog‘langan ro‘yxatdagi tugunni o‘chirish
Agar siz bog‘langan ro‘yxatdagi tugunni o‘chirmoqchi bo‘lsangiz, bog‘langan list buzilmasligi uchun uni o‘chirishdan oldin tugunning har bir tomonidagi tugunlarni ulash muhimdir.
Shunday qilib, tugunni o‘chirishdan oldin, oldingi tugundan keyingi ko‘rsatkichni olishimiz kerak va ular orasidagi tugunni o‘chirishdan oldin oldingi tugunni yangi keyingi tugunga ulashimiz kerak.
Bundan tashqari, biz o‘chirmoqchi bo‘lgan tugunni o‘chirishdan oldin keyingi ko‘rsatgichni tugunga ulash yaxshi fikrdir. Bu qisqa vaqtga bo‘lsa ham, hech narsaga ishora qilmaydigan "osilib turgan" ko‘rsatgichdan qochish uchundir.
Quyidagi simulyatsiya biz o‘chirmoqchi bo‘lgan tugunni va bog‘langan listni buzmasdan tugunni o‘chirishdan oldin listni to‘g‘ri ulash uchun avval listni qanday bosib o‘tish kerakligini ko‘rsatadi.
Quyidagi kodda tugunni o‘chirish algoritmi deleteSpecificNode deb nomlangan funksiyaga ko‘chiriladi.
Misol
Python-da alohida bog‘langan ro‘yxatdagi ma’lum bir tugunni o‘chirish:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def deleteSpecificNode(head, nodeToDelete):
if head == nodeToDelete:
return head.next
currentNode = head
while currentNode.next and currentNode.next != nodeToDelete:
currentNode = currentNode.next
if currentNode.next is None:
return head
currentNode.next = currentNode.next.next
return head
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Before deletion:")
traverseAndPrint(node1)
# Delete node4
node1 = deleteSpecificNode(node1, node4)
print("\nAfter deletion:")
traverseAndPrint(node1)
Misolni ishga tushirish »
Yuqoridagi deleteSpecificNode funksiyasida qaytariladigan qiymat bog‘langan listning yangi boshidir. Masalan, agar o‘chiriladigan tugun birinchi tugun bo‘lsa, qaytarilgan yangi bosh keyingi tugun bo‘ladi.
Bog‘langan listga tugun qo‘shing
Bog‘langan listga tugunni kiritish tugunni o‘chirishga juda o‘xshaydi, chunki ikkala holatda ham biz bog‘langan listni buzmasligimiz uchun keyingi ko‘rsatkichlar haqida g‘amxo‘rlik qilishimiz kerak.
Bog‘langan listga tugunni kiritish uchun biz birinchi navbatda tugunni yaratishimiz kerak, so‘ngra uni joylashtirgan joyda ko‘rsatkichlarni sozlashimiz kerak, shunda oldingi tugun yangi tugunga, yangi tugun esa to‘g‘ri keyingi tugunga ishora qiladi.
Quyidagi simulyatsiya yangi tugunni kiritishda havolalar qanday sozlanishini ko‘rsatadi.
- Yangi tugun yaratildi
- 1-tugun yangi tugun bilan bog‘langan
- Yangi tugun keyingi tugunga ulanadi
Misol
Python-da bitta bog‘langan listga tugunni kiritish:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def insertNodeAtPosition(head, newNode, position):
if position == 1:
newNode.next = head
return newNode
currentNode = head
for _ in range(position - 2):
if currentNode.next is None:
break
currentNode = currentNode.next
newNode.next = currentNode.next
currentNode.next = newNode
return head
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
print("Original list:")
traverseAndPrint(node1)
# Insert a new node with value 97 at position 2
newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)
print("\nAfter insertion:")
traverseAndPrint(node1)
Misolni ishga tushirish »
Yuqoridagi insertNodeAtPosition funksiyasida qaytarish qiymati bog‘langan listning yangi boshidir. Masalan, agar tugun bog‘langan listning boshiga kiritilgan bo‘lsa, qaytarilgan yangi bosh yangi tugun bo‘ladi.
Bog‘langan listlar operatsiyalarining vaqt murakkabligi
Bu yerda biz bog‘langan list operatsiyalarining vaqt murakkabligini muhokama qilamiz va ularni ushbu qo‘llanmada ilgari muhokama qilgan massiv algoritmlarining vaqt murakkabligi bilan solishtiramiz.
Esda tutingki, vaqt murakkabligi (n) ko‘p ma’lumotlar to‘plamiga asoslangan algoritm uchun zarur bo‘lgan operatsiyalarning taxminiy soni haqida ma’lumot beradi va bizga algoritmni ma’lum bir amalga oshirish uchun zarur bo‘lgan aniq vaqtni aytmaydi.
Bu shuni anglatadiki, chiziqli qidiruv massivlar uchun bog‘langan ro‘yxatdagi kabi bir xil vaqt murakkabligiga ega deb aytilgan bo‘lsa ham:O(n), bu ular bir xil vaqtni oladi degani emas. Algoritmni ishga tushirish uchun zarur bo‘lgan aniq vaqt dasturlash tiliga, kompyuter uskunasiga, massivlar va bog‘langan ro‘yxatlardagi operatsiyalar uchun zarur bo‘lgan vaqt farqiga va boshqa ko‘p narsalarga bog‘liq.
Bog‘langan listlar uchun chiziqli qidiruv massivlar bilan bir xil ishlaydi. Saralanmagan qiymatlar ro‘yxati ma’lum bir qiymatga ega bo‘lgan tugun topilgunga qadar bosh tugundan o‘tkaziladi. Vaqt murakkabligi O(n).
Bog‘langan ro‘yxatlar uchun ikkilik qidiruv (Ikkilik qidiruv) mumkin emas, chunki bu algoritm turli elementlarga to‘g‘ridan-to‘g‘ri sakrashga asoslangan, bog‘langan ro‘yxatlarda esa bunga imkon yo‘q.
Saralash algoritmlari massivlar bilan bir xil vaqt murakkabligiga ega va ular ushbu qo‘llanmada avvalroq tushuntirilgan. Ammo esda tutingki, indeks asosida massiv elementiga bevosita kirishga asoslangan tartiblash algoritmlari bog‘langan listlarda ishlamaydi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!