DSA bog‘langan ro‘yxat turlari

Bog‘langan ro‘yxat turlari

Bog‘langan ro‘yxatlarning uchta asosiy shakli mavjud:

1. Bir tomonlama bog‘langan ro‘yxatlar
2. Ikki tomonlama bog‘langan ro‘yxatlar
3. Halqasimon bog‘langan ro‘yxatlar

Bir tomonlama bog‘langan ro‘yxat — bog‘langan ro‘yxatlarning eng oddiy turi. U xotirada kamroq joy egallaydi, chunki quyidagi rasmdagidek har bir tugunda keyingi tugunga faqat bitta manzil bo‘ladi.

Ikki tomonlama bog‘langan ro‘yxat tugunlarida quyidagi rasmdagidek ham oldingi, ham keyingi tugunga manzil bo‘ladi, shuning uchun u ko‘proq xotira egallaydi. Ammo ro‘yxat bo‘ylab ham yuqoriga, ham pastga harakatlana olishni istasangiz, ikki tomonlama bog‘langan ro‘yxatlar qulay.

Halqasimon bog‘langan ro‘yxat — birinchi tuguni ("head") va oxirgi tuguni ("tail") o‘zaro ulangan bir tomonlama yoki ikki tomonlama bog‘langan ro‘yxatga o‘xshaydi.

Bir tomonlama yoki ikki tomonlama bog‘langan ro‘yxatlarda ro‘yxatning boshi va oxirini shunchaki havolalar null ekanligini tekshirish orqali topishimiz mumkin. Ammo halqasimon bog‘langan ro‘yxatlarda ayrim qo‘llanishlarda boshlang‘ich va oxirgi tugunlarni aniq tekshirish uchun murakkabroq kod kerak bo‘ladi.

Halqasimon bog‘langan ro‘yxatlar uzluksiz aylanib chiqish kerak bo‘lgan ro‘yxatlar uchun qulay.

Quyidagi rasm bir tomonlama halqasimon bog‘langan ro‘yxatga misol:

Quyidagi rasm ikki tomonlama halqasimon bog‘langan ro‘yxatga misol:

Bog‘langan ro‘yxatlarni amalga oshirish

Quyida quyidagilarning oddiy amalga oshirilishi keltirilgan:

1. Bir tomonlama bog‘langan ro‘yxat
2. Ikki tomonlama bog‘langan ro‘yxat
3. Halqasimon bir tomonlama bog‘langan ro‘yxat
4. Halqasimon ikki tomonlama bog‘langan ro‘yxat

Keyingi sahifada bog‘langan ro‘yxatlar ustida bajarilishi mumkin bo‘lgan turli amallar ko‘rib chiqiladi.

1. Bir tomonlama bog‘langan ro‘yxatni amalga oshirish

Quyida ushbu bir tomonlama bog‘langan ro‘yxatning amalga oshirilishi keltirilgan:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

node1.next = node2
node2.next = node3
node3.next = node4

currentNode = node1
while currentNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.next
print("null")

2. Ikki tomonlama bog‘langan ro‘yxatni amalga oshirish

Quyida ushbu ikki tomonlama bog‘langan ro‘yxatning amalga oshirilishi keltirilgan:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
    
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

node1.next = node2

node2.prev = node1
node2.next = node3

node3.prev = node2
node3.next = node4

node4.prev = node3

print("\nTraversing forward:")
currentNode = node1
while currentNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.next
print("null")

print("\nTraversing backward:")
currentNode = node4
while currentNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.prev
print("null")

3. Halqasimon bir tomonlama bog‘langan ro‘yxatni amalga oshirish

Quyida ushbu halqasimon bir tomonlama bog‘langan ro‘yxatning amalga oshirilishi keltirilgan:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ") 
currentNode = currentNode.next 

while currentNode != startNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.next

print("...")

14-qator: Bu bir tomonlama ro‘yxatni halqasimon qiladi.

17-qator: Dastur ro‘yxat bo‘ylab faqat bir marta o‘tishi uchun qachon to‘xtashni aynan shu orqali biladi.

4. Halqasimon ikki tomonlama bog‘langan ro‘yxatni amalga oshirish

Quyida ushbu halqasimon ikki tomonlama bog‘langan ro‘yxatning amalga oshirilishi keltirilgan:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

node1.next = node2
node1.prev = node4

node2.prev = node1
node2.next = node3

node3.prev = node2
node3.next = node4

node4.prev = node3
node4.next = node1

print("\nTraversing forward:")
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next

while currentNode != startNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.next
print("...")

print("\nTraversing backward:")
currentNode = node4
startNode = node4
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev

while currentNode != startNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.prev
print("...")

13- va 22-qatorlar: Bu havolalar ikki tomonlama bog‘langan ro‘yxatni halqasimon qiladi.

26-qator: Dastur ro‘yxat bo‘ylab faqat bir marta o‘tishi uchun qachon to‘xtashni aynan shu orqali biladi.

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Ushbu bir tomonlama bog‘langan ro‘yxatga qarang:

Bu bog‘langan ro‘yxatni qanday qilib halqasimon qilish mumkin?

The list can be made circular 
by connecting the next pointer 
in the last node, to the  node.

Javobni yuborish »

Mashqni boshlash