DSA bog‘langan ro‘yxatlar xotirada

Kompyuter xotirasi

Bog‘langan ro‘yxatlar nima ekanini va ular massivlardan qanday farq qilishini tushuntirish uchun kompyuter xotirasi qanday ishlashiga oid ba’zi asoslarni tushunishimiz kerak.

Kompyuter xotirasi — dasturingiz ishlayotganda foydalanadigan saqlash joyi. O‘zgaruvchilaringiz, massivlaringiz va bog‘langan ro‘yxatlaringiz aynan shu yerda saqlanadi.

Xotiradagi o‘zgaruvchilar

Tasavvur qilaylik, biz "17" butun sonini myNumber o‘zgaruvchisida saqlamoqchimiz. Soddalik uchun butun son ikki baytda (16 bit) saqlanadi va myNumber ning xotiradagi manzili 0x7F25 deb faraz qilaylik.

0x7F25 aslida myNumber butun son qiymati saqlanadigan ikki bayt xotiraning birinchisi manzilidir. Kompyuter butun son qiymatini o‘qish uchun 0x7F25 manziliga borganda, birinchi va ikkinchi baytlarning ikkalasini ham o‘qishi kerakligini biladi, chunki ushbu kompyuterda butun sonlar ikki baytni egallaydi.

Quyidagi rasmda myNumber = 17 o‘zgaruvchisi xotirada qanday saqlanishi ko‘rsatilgan.

Yuqoridagi misol oddiy, ammo mashhur Arduino Uno mikrokontrollerida butun son qiymati qanday saqlanishini ko‘rsatadi. Bu mikrokontroller 16 bitli manzil shinasiga ega 8 bitli arxitekturaga ega bo‘lib, butun sonlar uchun ikki bayt va xotira manzillari uchun ikki bayt ishlatadi. Taqqoslash uchun, shaxsiy kompyuterlar va smartfonlar butun sonlar va manzillar uchun 32 yoki 64 bit ishlatadi, ammo xotira asosan xuddi shunday ishlaydi.

Xotiradagi massivlar

Bog‘langan ro‘yxatlarni tushunish uchun avval massivlar xotirada qanday saqlanishini bilish foydali.

Massiv elementlari xotirada uzluksiz ketma-ketlikda saqlanadi. Bu har bir element oldingi elementdan darhol keyin saqlanishini anglatadi.

Quyidagi rasmda myArray = [3,5,13,2] butun sonlar massivi xotirada qanday saqlanishi ko‘rsatilgan. G‘oyani tushunib olish uchun bu yerda oldingi misoldagi kabi har bir butun son uchun ikki baytdan foydalaniladigan oddiy turdagi xotiradan foydalanamiz.

Kompyuterda faqat myArray ning birinchi baytining manzili bor, shuning uchun myArray[2] kodi bilan 3-elementga murojaat qilish uchun kompyuter 0x7F23 manzilidan boshlaydi va dastlabki ikkita butun sondan sakrab o‘tadi. Kompyuter butun son ikki baytda saqlanishini biladi, shuning uchun u 0x7F23 manzilidan 2x2 bayt oldinga sakraydi va 0x7F27 manzilidan boshlab 13 qiymatini o‘qiydi.

Massivdan element o‘chirilganda yoki unga element qo‘yilganda, undan keyin keladigan har bir element yo yangi elementga joy bo‘shatish uchun yuqoriga, yo o‘chirilgan element o‘rnini egallash uchun pastga siljitilishi kerak. Bunday siljitish amallari ko‘p vaqt oladi va, masalan, real vaqt tizimlarida muammolarga sabab bo‘lishi mumkin.

Quyidagi rasmda massiv elementi o‘chirilganda elementlar qanday siljitilishi ko‘rsatilgan.

Agar C tilida dasturlayotgan bo‘lsangiz, massivlar ustida amallar bajarish haqida ham o‘ylashingiz kerak, chunki unda element qo‘yish yoki o‘chirishda boshqa elementlarni o‘zingiz aniq ko‘chirishingiz lozim. C tilida bu fonda sodir bo‘lmaydi.

C tilida, shuningdek, keyinchalik ko‘proq element qo‘shish imkoni bo‘lishi uchun massivga boshidanoq yetarli joy ajratganingizga ishonch hosil qilishingiz kerak.

Massivlar haqida DSA darsligining ushbu oldingi sahifasida batafsil o‘qishingiz mumkin.

Xotiradagi bog‘langan ro‘yxatlar

Ma’lumotlar to‘plamini massiv sifatida saqlash o‘rniga bog‘langan ro‘yxat yaratishimiz mumkin.

Bog‘langan ro‘yxatlar ko‘plab holatlarda qo‘llaniladi, ulardan ba’zilarini aytib o‘tadigan bo‘lsak: ma’lumotlarni dinamik saqlash, stek va navbatni amalga oshirish yoki grafni ifodalash.

Bog‘langan ro‘yxat biror turdagi ma’lumotga hamda boshqa tugunlarga kamida bitta ko‘rsatkich yoki havolaga ega tugunlardan iborat.

Bog‘langan ro‘yxatlardan foydalanishning katta afzalligi shundaki, tugunlar xotiraning qayerida bo‘sh joy bo‘lsa, o‘sha yerda saqlanadi, ya’ni tugunlar massiv elementlari kabi ketma-ket, bir-biridan keyin saqlanishi shart emas. Bog‘langan ro‘yxatlarning yana bir qulay jihati — tugunlar qo‘shilganda yoki o‘chirilganda ro‘yxatdagi qolgan tugunlarni siljitish shart emas.

Quyidagi rasmda bog‘langan ro‘yxat xotirada qanday saqlanishi mumkinligi ko‘rsatilgan. Bog‘langan ro‘yxatda 3, 5, 13 va 2 qiymatli to‘rtta tugun bor va har bir tugun ro‘yxatdagi keyingi tugunga ko‘rsatkichga ega.

Har bir tugun to‘rt baytni egallaydi. Ikki bayt butun son qiymatini saqlash uchun, yana ikki bayt esa ro‘yxatdagi keyingi tugun manzilini saqlash uchun ishlatiladi. Avval aytib o‘tilganidek, butun sonlar va manzillarni saqlash uchun necha bayt kerakligi kompyuter arxitekturasiga bog‘liq. Bu misol ham, oldingi massiv misoli kabi, oddiy 8 bitli mikrokontroller arxitekturasiga mos keladi.

Tugunlar bir-biri bilan qanday bog‘langanini osonroq ko‘rish uchun bog‘langan ro‘yxatdagi tugunlarni quyidagi rasmdagidek, ularning xotiradagi joylashuviga kamroq bog‘liq bo‘lgan soddaroq ko‘rinishda tasvirlaymiz:

Agar oldingi misoldagi o‘sha to‘rtta tugunni ushbu yangi tasvirlash usulida birlashtirsak, u quyidagicha ko‘rinadi:

Ko‘rib turganingizdek, bog‘langan ro‘yxatdagi birinchi tugun "Head" (bosh), oxirgi tugun esa "Tail" (dum) deb ataladi.

Massivlardan farqli ravishda, bog‘langan ro‘yxatdagi tugunlar xotirada bir-biridan darhol keyin joylashtirilmaydi. Bu tugun qo‘shilganda yoki o‘chirilganda boshqa tugunlarni siljitish shart emasligini anglatadi, bu esa yaxshi.

Bog‘langan ro‘yxatlarning unchalik yaxshi bo‘lmagan jihati shundaki, massivdagi kabi, masalan, shunchaki myArray[5] deb yozib, tugunga to‘g‘ridan-to‘g‘ri murojaat qila olmaymiz. Bog‘langan ro‘yxatdagi 5-tugunga yetib borish uchun "head" deb ataladigan birinchi tugundan boshlab, keyingi tugunga o‘tish uchun shu tugunning ko‘rsatkichidan foydalanishimiz va 5-tugunga yetguncha o‘tilgan tugunlar sonini hisoblab borgan holda shunday davom etishimiz kerak.

Bog‘langan ro‘yxatlarni o‘rganish xotira ajratish va ko‘rsatkichlar kabi tushunchalarni yaxshiroq tushunishimizga yordam beradi.

Bog‘langan ro‘yxatlar yordamida amalga oshirilishi mumkin bo‘lgan daraxtlar va graflar kabi murakkabroq ma’lumotlar tuzilmalarini o‘rganishdan oldin bog‘langan ro‘yxatlarni tushunib olish ham muhim.

Zamonaviy kompyuterlardagi xotira

Shu paytgacha ushbu sahifada soddaroq va tushunarliroq bo‘lishi uchun misol sifatida 8 bitli mikrokontroller xotirasidan foydalandik.

Zamonaviy kompyuterlardagi xotira tamoyil jihatidan 8 bitli mikrokontroller xotirasi kabi ishlaydi, ammo butun sonlarni saqlash uchun ham, xotira manzillarini saqlash uchun ham ko‘proq xotira ishlatiladi.

Quyidagi kod ushbu misollarni ishga tushirayotgan serverimizdagi butun son o‘lchami va xotira manzili o‘lchamini beradi.

#include <stdio.h>

int main() {

    int myVal = 13;
    
    printf("Value of integer 'myVal': %d\n", myVal);
    printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
    printf("Address to 'myVal': %p\n", &myVal);
    printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes

    return 0;
}

Yuqoridagi kod misoli faqat C tilida ishlaydi, chunki Java va Python aniq/to‘g‘ridan-to‘g‘ri xotira ajratishdan yuqoriroq abstraksiya darajasida ishlaydi.

Bog‘langan ro‘yxatni C tilida amalga oshirish

Avvalroq ko‘rgan ushbu bog‘langan ro‘yxatni amalga oshiraylik:

Bog‘langan ro‘yxatlar xotirada qanday saqlanishining aniq misolini ko‘rish uchun ushbu bog‘langan ro‘yxatni C tilida amalga oshiraylik.

Quyidagi kodda kutubxonalarni ulagandan so‘ng tugun nima ekanini ifodalovchi, sinfga o‘xshash node struct’ini yaratamiz: tugun ma’lumot va keyingi tugunga ko‘rsatkichni o‘z ichiga oladi.

createNode() funksiyasi yangi tugun uchun xotira ajratadi, tugunning ma’lumot qismini funksiyaga argument sifatida berilgan butun son bilan to‘ldiradi va yangi tugunga ko‘rsatkichni (xotira manzilini) qaytaradi.

printList() funksiyasi shunchaki bog‘langan ro‘yxat bo‘ylab o‘tish va har bir tugunning qiymatini chiqarish uchun mo‘ljallangan.

main() funksiyasi ichida to‘rtta tugun yaratiladi, o‘zaro bog‘lanadi, chiqariladi va so‘ngra xotira bo‘shatiladi. Xotira sizib chiqishining (memory leak) oldini olish uchun xotiradan foydalanib bo‘lgach, uni bo‘shatish yaxshi amaliyot hisoblanadi. Xotira sizib chiqishi — xotira foydalanilgandan keyin bo‘shatilmay, asta-sekin tobora ko‘proq xotira egallanib borishi.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void printList(Node* node) {
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    Node* node1 = createNode(3);
    Node* node2 = createNode(5);
    Node* node3 = createNode(13);
    Node* node4 = createNode(2);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printList(node1);

    // Free the memory
    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

Yuqoridagi kodda bog‘langan ro‘yxatni chiqarish uchun printList() funksiyasi "next" ko‘rsatkichlari yordamida bir tugundan keyingisiga o‘tadi, bu esa bog‘langan ro‘yxatni "aylanib chiqish" (traversing yoki traversal) deb ataladi. Bog‘langan ro‘yxatni aylanib chiqish va bog‘langan ro‘yxatlar ustidagi boshqa amallar haqida Bog‘langan ro‘yxat amallari sahifasida ko‘proq bilib olasiz.

Bog‘langan ro‘yxatni Python va Java’da amalga oshirish

Endi xuddi shu bog‘langan ro‘yxatni Python va Java yordamida amalga oshiramiz.

Quyidagi Python kodida Node sinfi tugun nima ekanini ifodalaydi: tugun ma’lumot va keyingi tugunga havolani o‘z ichiga oladi.

Node sinfi to‘rtta tugun yaratish uchun ishlatiladi, so‘ngra tugunlar o‘zaro bog‘lanadi va oxirida chiqariladi.

Ko‘rib turganingizdek, Python kodi C kodidan ancha qisqa va, agar siz bog‘langan ro‘yxatlar xotirada qanday saqlanishini emas, balki shunchaki bog‘langan ro‘yxat tushunchasini tushunmoqchi bo‘lsangiz, ehtimol, yaxshiroqdir.

Java kodi Python kodiga juda o‘xshash. Java kodini ko‘rish uchun quyidagi "Misolni ishga tushirish" tugmasini bosing va "Java" yorlig‘ini tanlang.

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

A good thing about Linked Lists 
is that when inserting or 
removing a node, other elements 
do not have to be  in memory.