Bog‘langan ro‘yxat amallari

Bog‘langan ro‘yxat amallari

Bog‘langan ro‘yxatlar bilan bajarishimiz mumkin bo‘lgan asosiy amallar:

1. Aylanib chiqish (traversal)
2. Tugunni o‘chirish
3. Tugun qo‘shish
4. Saralash

Soddalik uchun quyida bu amallarni tushuntirishda bir tomonlama bog‘langan ro‘yxatlardan foydalaniladi.

Bog‘langan ro‘yxatni aylanib chiqish

Bog‘langan ro‘yxatni aylanib chiqish — bir tugundan keyingisiga havolalar bo‘ylab borib, bog‘langan ro‘yxat bo‘ylab o‘tish demakdir.

Bog‘langan ro‘yxatlarni aylanib chiqish odatda muayyan tugunni qidirish va tugun tarkibini o‘qish yoki o‘zgartirish, tugunni o‘chirish yoki shu tugundan darhol oldin yoki keyin tugun qo‘shish uchun bajariladi.

Bir tomonlama bog‘langan ro‘yxatni aylanib chiqish uchun ro‘yxatdagi birinchi tugun — head tugunidan boshlaymiz va quyidagi animatsiyadagidek, keyingi manzil null bo‘lguncha shu tugunning next havolasi, keyingi tugunning next havolasi va hokazo bo‘ylab boramiz:

Quyidagi kod yuqoridagi animatsiyadagi kabi bog‘langan ro‘yxatni aylanib chiqar ekan, tugunlarning qiymatlarini chiqaradi.

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)

Bog‘langan ro‘yxatdagi eng kichik qiymatni topish

Bir tomonlama bog‘langan ro‘yxatni aylanib chiqib va har bir qiymatni tekshirib, undagi eng kichik qiymatni topaylik.

Bog‘langan ro‘yxatdagi eng kichik qiymatni topish massivdagi eng kichik qiymatni topganimizga juda o‘xshaydi, faqat keyingi tugunga o‘tish uchun next havolasi bo‘ylab borishimiz kerak.

Bog‘langan ro‘yxatdagi eng kichik qiymatni topish tamoyil jihatidan quyidagicha ishlaydi:

Eng kichik qiymatni topish uchun ro‘yxatni oldingi koddagi kabi aylanib chiqishimiz kerak. Ammo ro‘yxatni aylanib chiqishdan tashqari, kichikroq qiymatli tugun topilganda joriy eng kichik qiymatni ham yangilashimiz kerak.

Quyidagi kodda eng kichik qiymatni topish algoritmi findLowestValue deb nomlangan funksiyaga ko‘chirilgan.

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))

Bog‘langan ro‘yxatdagi tugunni o‘chirish

Bu holda bizda o‘chirmoqchi bo‘lgan tugunga havola (yoki ko‘rsatkich yoki manzil) bor.

Bog‘langan ro‘yxat uzilib qolmasligi uchun tugunni o‘chirishdan oldin uning ikki tomonidagi tugunlarni bir-biriga ulash muhim.

Shuning uchun tugunni o‘chirishdan oldin oldingi tugundan next ko‘rsatkichini olishimiz va o‘rtadagi tugunni o‘chirishdan oldin oldingi tugunni yangi keyingi tugunga ulashimiz kerak.

Bu yerdagi kabi bir tomonlama bog‘langan ro‘yxatda oldingi tugundan next ko‘rsatkichini olish uchun aslida ro‘yxatni boshidan aylanib chiqishimiz kerak, chunki o‘chirmoqchi bo‘lgan tugundan orqaga qaytishning imkoni yo‘q.

Quyidagi simulyatsiyada biz o‘chirmoqchi bo‘lgan tugun hamda bog‘langan ro‘yxatni uzmasdan tugunni o‘chirishdan oldin ro‘yxatni to‘g‘ri ulash uchun avval ro‘yxat qanday aylanib chiqilishi kerakligi ko‘rsatilgan.

Shuningdek, o‘chirmoqchi bo‘lgan tugunni o‘chirishdan oldin avval next ko‘rsatkichini undan keyingi tugunga ulash maqsadga muvofiq. Bu qisqa bir lahzaga bo‘lsa ham, "osilib qolgan" (dangling) ko‘rsatkich, ya’ni hech narsani ko‘rsatmaydigan ko‘rsatkich paydo bo‘lishining oldini olish uchun kerak.

Quyidagi kodda tugunni o‘chirish algoritmi deleteSpecificNode deb nomlangan funksiyaga ko‘chirilgan.

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)

Yuqoridagi deleteSpecificNode funksiyasida qaytariladigan qiymat bog‘langan ro‘yxatning yangi head’i bo‘ladi. Masalan, agar o‘chiriladigan tugun birinchi tugun bo‘lsa, qaytariladigan yangi head keyingi tugun bo‘ladi.

Bog‘langan ro‘yxatga tugun qo‘shish

Bog‘langan ro‘yxatga tugun qo‘shish tugunni o‘chirishga juda o‘xshaydi, chunki ikkala holatda ham bog‘langan ro‘yxatni uzib qo‘ymaslik uchun next ko‘rsatkichlariga e’tibor berishimiz kerak.

Bog‘langan ro‘yxatga tugun qo‘shish uchun avval tugunni yaratishimiz, so‘ngra uni qo‘shayotgan pozitsiyada ko‘rsatkichlarni shunday sozlashimiz kerakki, oldingi tugun yangi tugunni, yangi tugun esa to‘g‘ri keyingi tugunni ko‘rsatsin.

Quyidagi simulyatsiyada yangi tugun qo‘shilganda havolalar qanday sozlanishi ko‘rsatilgan.

1. Yangi tugun yaratiladi
2. 1-tugun yangi tugunga bog‘lanadi
3. Yangi tugun keyingi tugunga bog‘lanadi

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 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)

Yuqoridagi insertNodeAtPosition funksiyasida qaytariladigan qiymat bog‘langan ro‘yxatning yangi head’i bo‘ladi. Masalan, agar tugun bog‘langan ro‘yxat boshiga qo‘shilsa, qaytariladigan yangi head yangi tugun bo‘ladi.

Bog‘langan ro‘yxatlar ustidagi boshqa amallar

Yuqorida bog‘langan ro‘yxatlar ustidagi faqat uchta asosiy amalni ko‘rib chiqdik: aylanib chiqish (yoki qidirish), tugunni o‘chirish va tugun qo‘shish.

Bog‘langan ro‘yxatlar bilan bajarish mumkin bo‘lgan ko‘plab boshqa amallar ham bor, masalan, saralash.

Darslikning avvalgi qismlarida ko‘plab saralash algoritmlarini ko‘rib chiqdik va ulardan ko‘pchiligini bog‘langan ro‘yxatlarga ham qo‘llashimiz mumkin. Misol uchun selection sort’ni olaylik. Selection sort’da eng kichik qiymatni topamiz, uni o‘chiramiz va boshiga qo‘yamiz. Xuddi shuni bog‘langan ro‘yxat bilan ham qila olamiz, to‘g‘rimi? Hozirgina bog‘langan ro‘yxat bo‘ylab qanday qidirish, tugunni qanday o‘chirish va tugunni qanday qo‘shishni ko‘rdik.

Bog‘langan ro‘yxatlar va massivlar

Massivlar bilan solishtirganda bog‘langan ro‘yxatlarning ba’zi asosiy xususiyatlari quyidagilar:

• Bog‘langan ro‘yxatlar uchun xotirada massivlardagi kabi belgilangan o‘lchamdagi joy ajratilmaydi, shuning uchun belgilangan xotira joyi to‘lganda bog‘langan ro‘yxatlar massivlar kabi butun ro‘yxatni kattaroq xotira joyiga ko‘chirishni talab qilmaydi.
• Bog‘langan ro‘yxat tugunlari xotirada birin-ketin (uzluksiz) joylashtirilmaydi, shuning uchun tugunlar qo‘shilganda yoki o‘chirilganda bog‘langan ro‘yxat tugunlarini xotirada yuqoriga yoki pastga siljitish shart emas.
• Bog‘langan ro‘yxat tugunlari boshqa tugunlarga bir yoki bir nechta havolani saqlash uchun ko‘proq xotira talab qiladi. Massiv elementlari esa buncha xotira talab qilmaydi, chunki massiv elementlarida boshqa elementlarga havolalar bo‘lmaydi.
• Bog‘langan ro‘yxat amallarini dasturlash odatda qiyinroq va ular shunga o‘xshash massiv amallariga qaraganda ko‘proq kod qatorini talab qiladi, chunki dasturlash tillarida massivlar uchun o‘rnatilgan qo‘llab-quvvatlash yaxshiroq.
• Muayyan pozitsiyadagi tugunni topish uchun bog‘langan ro‘yxatni aylanib chiqishimiz kerak, massivlarda esa myArray[5] deb yozib, elementga to‘g‘ridan-to‘g‘ri murojaat qilishimiz mumkin.

Bog‘langan ro‘yxat amallarining vaqt murakkabligi

Bu yerda bog‘langan ro‘yxat amallarining vaqt murakkabligini muhokama qilamiz va ularni ushbu darslikda avvalroq ko‘rib chiqqan massiv algoritmlarining vaqt murakkabligi bilan taqqoslaymiz.

Esda tutingki, vaqt murakkabligi faqat katta hajmdagi ma’lumotlar to‘plami \(n\) asosida algoritmga kerak bo‘ladigan amallarning taxminiy soni haqida ma’lumot beradi va algoritmning muayyan amalga oshirilishi aniq qancha vaqt olishini aytmaydi.

Bu shuni anglatadiki, Linear Search massivlar uchun ham, bog‘langan ro‘yxat uchun ham bir xil vaqt murakkabligiga ega deyilsa-da: \(O(n)\), bu ular bir xil vaqt oladi degani emas. Algoritm bajarilishi uchun ketadigan aniq vaqt dasturlash tiliga, kompyuter apparat ta’minotiga, massivlar va bog‘langan ro‘yxatlardagi amallar uchun kerak bo‘ladigan vaqt farqlariga va boshqa ko‘plab omillarga bog‘liq.

Bog‘langan ro‘yxatlar uchun Linear Search massivlardagi kabi ishlaydi. Saralanmagan qiymatlar ro‘yxati bosh tugundan boshlab, kerakli qiymatga ega tugun topilguncha aylanib chiqiladi. Vaqt murakkabligi \(O(n)\).

Bog‘langan ro‘yxatlar uchun Binary Search mumkin emas, chunki bu algoritm massivning turli elementlariga to‘g‘ridan-to‘g‘ri sakrashga asoslangan, bog‘langan ro‘yxatlarda esa buni qilib bo‘lmaydi.

Saralash algoritmlari massivlardagi kabi vaqt murakkabliklariga ega va ular ushbu darslikda avvalroq tushuntirilgan. Biroq esda tuting: massiv elementiga indeks orqali to‘g‘ridan-to‘g‘ri murojaat qilishga asoslangan saralash algoritmlari bog‘langan ro‘yxatlarda ishlamaydi.

def traverseAndPrint(head):
    currentNode = 
    while currentNode:
        print(currentNode.data, end=" -> ")
        currentNode = currentNode.
    print("null")