Python

Bu yerda siz o'rganib borayotgan ma'lumotlar tuzilmalari va algoritmlarning Python dasturlash tilidagi kod implementatsiyasini ko'rib o'rganib chiqsangiz bo'ladi. Biz imkon qadar kodlarni sizga tushuntirishga va sizni tasavvuringizni uyg'otishga harakat qilamiz. Har bir mavzuga tegishli kodlarni shu yerdan topishingiz mumkin. Agar sizga boshqa bir mavzu kerak bo'lsa o'ng tomondagi menu orqali o'zingiz hohlagan mavzuga tez o'tishingiz mumkin.

Har bir kodni ustida komment orqali u nima vazifa bajarishini yozib o'tishga harakat qilamiz. Uni o'zingiz ham sinab ko'rishni unutmang!

Big O

Big O notationda o'rgangan bilimlaringizni keling endi amaliyotlarda misollar bilan ko'rib chiqamiz va biz odatiy yozadigan kodlarimizni analiz qilishni o'rganamiz. Misol uchun pastdagi kodga e'tibor bering:

def juftlar(arry: list[int]) -> list:
    result = []
    for num in arry:
        if num % 2 == 0:
            result.append(num)
    return result

Yuqoridagi kodning Time va Space Complexitysi nima deb o'ylaysiz? Keling tahlil qilamiz. Bu yerda for loop bor demak bizni kodimiz linear harakat qiladi ya'ni bu qandaydir shartlar asosida emas berilgan uzunlik asosida birma-bir iteratsiya bo'ladi. Shuning xisobiga ko'ra bu n marta harakat qilayabdi. Ochilgan List esa har bir element uchun bitta xotira sarflaydi. Agar funksiyaga berilgan array ichida faqat juft sonlar bo'lsa loop barcha listni iteratsiya qiladi. Biz shu tomonini ham o'ylagan holda uni ham n ta element oladi deb xisoblaymiz.

Time: O(n)

Space : O(n)

Keling endi keyingi misolga to'xtasak:

def access_element(arr: list, index : int) -> any:
    return arr[index]

Ushbu misolda bizning funksiya List olib uning berilgan indeksidagi elementni qaytarayabdi. Listlarda indeksga kirish uchun ketkaziladigan vaqt O(1) bo'ladi. Xotira esa bu yerda 1 chunki biz hech qanday yangi data type yaratmayabmiz. Demak xulosa:

Time: O(1)

Space : O(1)

def summing(numbers: list) -> int:
    result = 0
    for num in numbers:
        result += num
    return result

Mana bu misolga qaraylik, bu yerda vaziyat biroz boshqacha endi biz result o'zgaruvchisini increment qilayabmiz. Ya'ni ortiqcha o'zgaruvchilar ochmagan holda faqat result ustida amal qilib yana unga qiymat saqlayabmiz (shunchaki update qilayabmiz). Shuni inobatga olgan holda bu yerda space O(1) ga, time esa O(n) ga teng. Chunki bizning loop nta amal bajaradi eng ko'pi bilan.

Bunday misollarni ko'plab keltirishimiz mumkin ammo keling endi qolganlarini yo'l-yo'lakay ko'rib tahlil qilib ketamiz...

Array

Python dasturlash tilida Array degan built-in data structure mavjud emas ammo uning ekvivalenti bor u esa List.

List - turli xil data typedagai ma'lumotlarni saqlab turuvchi konteyner xisoblanadi.

# Pythonda List yaratish:
my_list = ['o', 'apple', 17, 3.14]
 
# Bo'sh list yaratish:
new_list = list() 
 
# yoki
new_list = []

List metodlari

Yuqoridagi rasmda ba'zi metodlar keltirilgan ularni shunchaki ko'rib emas balkim ishlatib ko'rishni ham maslahat beraman. Agar siz ko'proq metodlar haqida o'rganmoqchi bo'lsangiz Python dokumentatsiyasida (opens in a new tab) ko'proq yoritib o'tilgan.

Indexes

List ichidagi elementlarni access qilish ya'ni kirish uchun biz indexlardan foydalanamiz. Yuqoridagi rasmda ko'rib turganingizdek sanoq 1 dan emas 0 dan boshlangan.

Xazil: Agar sizga biror dasturchi sen mening birinchi muhabbatimsan desa ishonmang. Chunki dasturlashda sanoq 0dan boshlanadi. 😌

nums = [3, 8, 1, 0, 5, -2, 32] # Rasmdagi list 
 
print(nums[3]) # List ichidan 3chi indeksdagi qiymatni oldik.

Slicing

Tasavvur qiling sizda 100ta elementli list bor ammo sizga uni faqat 20-50 ideks oralig'idagi qiymatlari kerak. Bunday holatda sizga listdagi qiymatlarni o'chirish emas balkim shunchaki uni bo'laklarga bo'lish kifoya qiladi.

list[start:stop:step]
# start - boshlang'ich nuqta
# step - tugash nuqtasi
# step - qadam
ls = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
 
ls[2:]    # [3, 4, 5, 6, 7, 8, 9, 10]
ls[1:6]   # [2, 3, 4, 5, 6]
ls[:5]    # [1, 2, 3, 4, 5]
ls[1:4:2] # [2, 4]
ls[::2]   # [1, 3, 5, 7, 9]
ls[::-1]  # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
ls[::-2]  # [10, 8, 6, 4, 2]

Yuqorida keltirilgan misollarni tushunishlik uchun ozgina tahlil qilib o'zingiz ham mashq qilib ko'ring.

Python Array

Pythonda Array bor va uni yaratish uchun yoki tushunish uchun siz shunchaki array (opens in a new tab) Python Standart Library ishlatishingiz kerak:

from array import array
 
nums = array('l', [1, 2, 3, 4, 5]) 
 
nums.append(0) # array('l', [1, 2, 3, 4, 5, 0]) 
nums.remove(3) # array('l', [1, 2, 4, 5, 0]) 
...
 
print(nums[2]) # 4
# Qolgan amallar xuddi listdek ishlatilaveradi. array yaratilishi boshqacha

Ammo biz ushbu qo'llanmada bu kutubxonani to'liq ishlatmaymiz ammo sizga list va arrayni taqqoslab ular qanday ishlatilishini qisqacha ko'rsatib o'tdik. Qolgan ma'lumotlarni link orqali o'zingiz o'rganishingiz mumkin.

https://docs.python.org/3/library/array.html (opens in a new tab)

Keling endi ularni farqi nimadaligiga biroz chuqurroq kirishamiz. Pythonda hamma narsa object, xattoki funksiyalar ham. List esa juda moslashuvchan va ixtiyoriy ma'lumotlarni saqlashi mumkin, ammo ular Arrayga qaraganda ko'proq xotira ishlatadi. Pastdagi rasmga e'tibor bering:

Har bir list pointer ichidagi pointer blokini xosil qiladi, natijada biz birinchi doim memory pointerga boramiz va undan keyin object pointerga boramiz. Tushunarliroq qiladigan bo'lsak tasavvur qiling sizda my_list = [1, 2, 3, 4, 5] mavjud va siz my_list[2] ni olmoqchisiz. Bu yerda python interpreter birinchi bo'lib my_listni xotirada qayerda joylashganini aniqlaydi. So'ngra my_listda 2chi indexni xisoblaydi va keyin sizga siz hohlagan elementni qaytaradi.

Arrayda esa xolat biroz boshqacha va keling yuqoridagi list misolini array qilib olamiz. Python interpreter my_list degan arrayni birinchi qiymatini qidiradi. Va xotirani hozirgi hex qiymatiga biz hohlagan indeksni qo'shish orqali o'sha elementga oson kiradi.

Listni afzalliklaridan ba'zilari bu uning kengayib, kichirayishida. List yana boshqa turdagi ma'lumotlarni ham saqlay oladi.

Arrayning afzalliklaridan ba'zilari bu uning tezligida va listga nisbatan qaralganda ancha kam xotira sarflashida. Array faqat bir xil turdagi ma'lumotlarni o'zida saqlay oladi va uning xajmi o'zgarmaydi.

Challenges

1. Merge Two sorted list (opens in a new tab)
2. Find two number that sums up to K (opens in a new tab)

Linked List

Linked List pythonda built-in data structure sifatida kiritilmagan. Biz uni classlar yordamida yaratamiz chunki pythonda hamma narsa object.

Agar siz Pythonda OOPni qanday ishlashini bilmasangiz, avval OOPni o'rganib chiqishingizni maslahat beramiz.

Singly Linked List

Linked Listni turlicha usullar bilan implementatsiya qilishimiz mumkin. Bugun biz ba'zi keng tarqalgan yo'llarini ko'rib chiqamiz.

class Node:
    def __init__(self, value: any) -> None:
        self.value = value
        self.next = None
 
class LinkedList:
    def __init__(self) -> None:
        self.head = None
 
my_list = LinkedList()

Yuqoridagi misolda biz oddiy Singly Linked List yaratdik. U yerda siz 2ta class ko'rishingiz mumkin. Node classi odatda 2ta ma'lumotni ushlab turish uchun kerak ya'ni data va next. LinkedList esa Node classlarni ushlab turadi. Ammo bizda muammo bor qanday qilib biz LinkedList classiga Nodelarni qo'shib boramiz?

Keling endi LinkedList classidagi self.headga node qo'shish uchun method yaratamiz va uni nomini append deb qo'yamiz.

# Biz self.head ga qiymat qo'shish uchun append yaratdik.
def append(self, value: any) -> None:
    # Birinchi bo'lib Node classidan yangi object yaratib olamiz.
    new_node = Node(value)
 
    # Endi esa linkedlistimiz bo'sh emasligini tekshirishimiz kerak.
    # Buning uchun self.headni tekshirish kifoya. Agar u None bo'lsa linked list bo'sh degani.
    if self.head is None:
        self.head = new_node
        return 
    
    # Agar linkedlistimizda nodelar bo'lsa, demak biz oxirgi nodeni topishimiz kerak.
    # Oxirgi nodeni topish uchun qaysi nodeni nexti None ekanligni aniqlashmiz kerak.
    # Buning uchun self.head dan boshlab oxirgi nodegacha iteratsiya qilamiz.
    last_node = self.head
    while last_node.next:
        last_node = last_node.next
    
    # Demak last_node oxirgi elementni topdi. Uni nexti hozircha None.
    # Yangi element esa uni nextiga tushishi kerak.
    last_node.next = new_node

Yuqoridagi kodni kommentlarini o'qib chiqing va harakatlar ketma-ketligni tahlil qiling. Shunda jarayon yanada soddalashadi. Kodni bir necha marta implementatsiya qilib ko'ring, bu esa sizga tajriba va tushunishingizni aniqlashtiradi. Keling endi boshqa methodlarini ham yaratib chiqamiz.

class Node:
    def __init__(self, value: any) -> None:
        self.value = value
        self.next = None
 
class LinkedList:
    def __init__(self) -> None:
        self.head = None
    
    def append(self, value: any) -> None:
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return 
 
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
 
    # Bu method berilgan qiymatni linkedlistni boshiga qo'shadi ya'ni headga.
    def insert(self, value: any) -> None:
        # Avval linked listni tekshiramiz va head bo'lmasa headga qo'shamiz.
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        
        # Head bo'lsa demak yangi elementni nextini headga qaratamiz.
        new_node.next = self.head
        # va new_node ni esa head deb tayinlaymiz. 
        self.head = new_node
        
 
my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.insert(0)
 
# Buning ko'rinishi mana bunday: 0 -> 1 -> 2 -> 3 -> None
print(my_list.head.value)
print(my_list.head.next.value)
print(my_list.head.next.next.value)
print(my_list.head.next.next.next.value)
print(my_list.head.next.next.next.next)

Keling boshqa methodlarini ham kiritib chiqsak va ularni keyin tahlil qilsak. Biz faqat methodni o'zini yozib ketamiz, siz esa uni classingiz ichiga qo'shib, ishlatib va tahlil qilishingiz mumkin:

# Bu method headni qaytarish uchun.
def get_head(self) -> any:
    return self.head
 
 
# Linked List bo'shmi yo'qmi tekshirish uchun method
def is_empty(self) -> any:
    return self.head is None
 
 
# Linked Listdagi barcha nodelarni bitta oddiy list qilib chiqarish uchun.
def print_list(self) -> None:
    result = []
    # Agar head None bo'lsa [] qaytarsin.
    if self.head is None:
        return result
    # Agar unday bo'lmasa demak iteratsiya qilib har bir nodeni datasi listga qo'shadi.
    current_node = self.head
    while current_node:
        result.append(current_node.data)
        current_node = current_node.next
    print(result)
 
 
# Biror qiymatni qidirish uchun ishlatiladi agar bo'lsa True bo'lmasa False qaytaradi.
def search(self, value: any) -> bool:
    # Agar Linked List bo'sh bo'lsa None qaytarishi kerak qidirmasdan.
    if self.head_node is None:
        return False
    # Agar qiymatlar bo'lsa, iteratsiya qilib ularni valuesi tekshiriladi.
    current_node = self.head_node
    while current_node:
        if current_node.data == value:
            return True
        current_node = current_node.next_element
    return False

Qolgan methodlarni esa o'zingiz talabdan kelib chiqib tuzasiz degan umiddaman. Asosiysi biz uni qanday implement qilishni tushunib oldik!

Doubly Linked List

Circular Linked List