Linked list'lar va Python list'lari: qachon qaysi birini ishlatish kerak

List elementlaringiz sizga nafaqat qiymatni, balki keyin qayerga borish kerakligini ham aytib berishini xohlaganmisiz? Agar shunday bo'lsa, linked list'lar aynan siz izlagan narsa bo'lishi mumkin. Linked list'lar har bir node'da qiymat saqlashdan tashqari keyingi node'ga reference ham saqlaydi va sizni to'g'ri yo'nalishga yo'naltirib turadi.

Ushbu maqolada siz linked list'larning asosiy tarkibiy qismlari va keng tarqalgan amallari haqida ko'proq bilib olibgina qolmay, Python'da linked list'larning turli xillarini qanday amalga oshirishni ham ko'rasiz. Oddiy list'lar bilan qisqacha taqqoslashdan boshlab, sizni linked list bo'yicha klassik intervyu savollari bilan tanishtiramiz va Python'da allaqachon built-in bo'lgan muqobillarni ham ko'rsatamiz, shunda siz ishlarni bajarishning yagona usuliga bog'lanib qolmaysiz.

Linked list nima?

Linked list — computer science'ning asosini tashkil etuvchi chiziqli ma'lumotlar tuzilmasi. Bu node deb ataladigan elementlar ketma-ketligidan foydalanadigan ma'lumotlarni tashkil etish usullaridan biri. Har bir node quyidagilarni o'z ichiga oladi:

• Muayyan ma'lumot qiymati

• Zanjirdagi keyingi node'ga reference/pointer

Linked list bo'ylab uning head'idan, ya'ni birinchi node'idan tail'igacha, ya'ni oxirgi node'igacha bir node'dan keyingisiga o'tib borishingiz mumkin. Oddiy, singly linked list'da oxirgi node None'ga ishora qiladi.

Linked list massiv kabi xotiradan uzluksiz joy egallashi shart emas. Buning o'rniga har bir node keyingi node bilan bog'lanish uchun o'zining next reference'idan foydalanadi.

Python'da built-in linked list ma'lumotlar tuzilmasi yo'q. Biroq uni o'zingiz amalga oshirishingiz mumkin, odatda buning uchun o'zingiz yozgan sinflardan foydalaniladi.

Linked list va list'lar

Python'da linked list'larni yaratish usuliga o'tishdan oldin ularni an'anaviy list'lardan farqlab olish muhim.

Python'ning built-in list'i ham, linked list ham elementlarning tartiblangan to'plamlarini saqlash uchun ishlatiladi, lekin ichki tomondan ular juda boshqacha ishlaydi. Oddiy list'lar xotirada uzluksiz massivdan foydalanadi va index orqali elementlariga tez hamda oson murojaat qilish imkonini beradi. Biroq list'lar oldindan uzluksiz xotiraning qat'iy blokini ajratib olishi kerak, bu esa element qo'shilganda yoki o'chirilganda hajmni o'zgartirishga olib kelishi mumkin va bu unumdorlikka ta'sir qilishi mumkin. Shunga qaramay, bu faqat vaqti-vaqti bilan sodir bo'ladi, chunki Python'ning list'i ortiqcha sig'imni oldindan ajratib qo'yadi, shu sababli append() chaqiruvlarining ko'pchiligi hajm o'zgarishini keltirib chiqarmaydi

Linked list'lar esa, aksincha, pointer'lar bilan bog'langan node'lardan foydalanadi. Bu ularni massivlar kabi random access uchun yaroqsiz qiladi (ya'ni index'ini bilgan holda muayyan node'ga to'g'ridan-to'g'ri murojaat qila olmaysiz), ammo element qo'shish yoki elementlarni o'chirishda ular moslashuvchanroq va samaraliroq, chunki bu amallar faqat bir-ikkita pointer'ni qayta ulashni talab qiladi.

Quyidagi diagramma farqlarni ko'rsatib beradi:

Linked list yaratish uchun asosiy qismlar

Endi siz o'zingizning Python linked list'ingizni yaratishga tayyorsiz. Bu odatda ikkita asosiy sinf yordamida amalga oshiriladi:

• Node — har bir alohida node uchun

• LinkedList — umumiy ma'lumotlar tuzilmasi uchun

Bu sinflarni yaratish alohida node xatti-harakatini list darajasidagi xatti-harakatdan ajratishga yordam beradi, bu esa traverse qilish, yangi elementlar qo'shish, elementlarni o'chirish va qidirish uchun hal qiluvchi ahamiyatga ega.

Alohida node'lar

Node Python sinfi linked list'dagi bitta elementni ifodalaydi. Har bir node o'z ma'lumotini va ketma-ketlikdagi keyingi node'ga reference'ni saqlaydigan alohida obyektdir.

Mana Node'ning ta'rifi. def __init__(self, data) qatori constructor'ni aniqlaydi, u attribute'larni saqlashga yordam beradi:

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

next attribute'i zanjirdagi keyingi node'ga reference saqlaydi; biroq siz boshqa node bilan bog'lanish o'rnatmaguningizcha u None qiymati bilan initialize qilinadi.

Node obyektlarini yaratishni boshlash uchun initialize qilishda qiymat bering. So'ng node'lar o'rtasida bog'lanish hosil qilish uchun next property'sini o'rnating:

head = Node(100)
second_node = Node(200)

head.next = second_node

Bo'sh list'ni initialize qilish

Node tayyor bo'lgach, LinkedList sinfini yaratish vaqti keldi:

class LinkedList:
    def __init__(self):
        self.head = None

Shundan so'ng bo'sh linked list yaratishingiz mumkin:

linked_list = LinkedList()

print(linked_list.head)

# Expected result:
# None

Bu list'da hozircha birorta ham node yo'q, lekin ularni sinf method'i yordamida qo'shishingiz mumkin. Keyingi qadam — linked list'ning standart amallari doirasida node'larni qo'shish, o'chirish yoki ular orasidan qidirish uchun kod yozish.

Linked list'lar uchun asosiy method'lar

Sizda Python linked list'ining ikki sinfdan iborat skeleti allaqachon bor: alohida node'lar uchun Node va umumiy list tuzilmasi uchun LinkedList. Odatda siz method'lar, ya'ni sinf ichida joylashadigan va sinf bajara oladigan amallarni tavsiflaydigan maxsus funksiyalarni yozishni xohlaysiz.

Yangi node'lar qo'shish

Boshlash uchun Python linked list'ingiz oxiriga node'lar qo'shadigan append() nomli method yaratishingiz mumkin. Bu method yangi qiymatni qabul qilishi, yangi node yaratishi va uni list'ingiz oxiriga qo'shishi kerak. Agar list'ingiz bo'sh bo'lsa, yangi node head'ga aylanadi, agar list'ingizda allaqachon node'lar bo'lsa, bu method yangi node'ni joriy tail node'dan keyingi node sifatida o'rnatadi. E'tibor bering, bu funksiya LinkedList sinfining bir qismi bo'lishi kerak:

def append(self, value):
    new_node = Node(value)

    # Set as head if empty list
    if self.head is None:
        self.head = new_node
        return

    current = self.head

    # Traverse linked list looking for the tail node
    while current.next is not None:
        current = current.next

    # Append new_node at the end of the list
    current.next = new_node

Bu implementatsiya tail'ni alohida saqlamagani uchun append() oxirgi node'ni topish uchun head'dan boshlab butun list'ni traverse qilishi kerak. Tail'ga yetib borgach, uning next reference'ini yangi node'ga o'rnating.

Endi Python linked list'ingizga yangi node'larni quyidagicha qo'shishingiz mumkin:

linked_list.append(100)
linked_list.append(200)
linked_list.append(300)

Linked list'ni traverse qilish

Butun linked list'ni traverse qilish uchun maxsus method ham yaratishingiz mumkin. Bu traverse() method'i head'dan boshlab, list oxiriga yetguncha doimiy ravishda keyingi node'ga o'tib, list'ning har bir qiymatini chiqaradi:

def traverse(self):
    current = self.head

    while current is not None:    # Continue through the tail node
        print(current.data)
        current = current.next      # Move to the next node

linked_list.traverse()

# Expected result:
# 100
# 200
# 300

Node'ni qidirish

Oddiy Python list'laridan farqli o'laroq, linked list'lar index bo'yicha to'g'ridan-to'g'ri murojaatni qo'llab-quvvatlamaydi. Biroq linked list'da muayyan qiymatni qidiradigan method yaratishingiz mumkin. Bu search() method'i list'ning head'idan boshlaydi va har bir node qiymatini kiritilgan qiymat bilan solishtiradi. U ma'lumoti mos keladigan birinchi node'ni qaytaradi, agar qiymatni topa olmasa None qaytaradi:

def search(self, value):
    current = self.head

    while current is not None:
        if current.data == value:
            return current

        current = current.next

    return None

my_node = linked_list.search(200)

print(my_node.data)

# Expected result:
# 200

Node'larni o'chirish

Node'ni qiymati bo'yicha o'chirish uchun maqsadli node'ni chetlab o'tib, oldingi node'ni keyingisi bilan ulash kifoya. Bu remove() method'i kiritilgan qiymatga mos keladigan birinchi node'ni olib tashlashga yordam beradi. Agar birorta node mos kelmasa, u ValueError ko'taradi:

def remove(self, value):
    # Raise error if list is empty
    if self.head is None:
        raise ValueError(f"{value} not found in linked list")

    # Handle removing the head as a special case
    if self.head.data == value:
        self.head = self.head.next
        return

    current = self.head

    # Look for value, connect around it if found
    while current.next is not None:
        if current.next.data == value:
            current.next = current.next.next
            return

        current = current.next   # Move on if value doesn’t match

    # Raise error if value not found
    raise ValueError(f"{value} not found in linked list")

linked_list.remove(200)
linked_list.traverse()

# Expected result:
# 100
# 300

Yuqoridagi kodda joriy node'ning next attribute'ini yangilashni unutmang. Yangi node'lar qo'shishda yoki elementlarni o'chirishda node'laringiz pointer'larini o'zgartirishni unutib qo'yish juda keng tarqalgan xatodir.

Bu asosiy method'lar Python linked list'lari bilan ishlash uchun zarur vositalarni beradi; biroq ularning amalga oshirilishi siz tanlagan linked list turiga qarab farq qilishi mumkin.

Linked list'larni amalga oshirish: Python'da singly, doubly, circular

Hozircha oddiydek ko'rinsa-da, linked list'lar aslida bir nechta turda bo'ladi va ularning har biri o'z afzalliklari va kamchiliklariga ega. Ushbu maqola davomida siz singly linked list'lar ustida ishladingiz, lekin doubly yoki circular linked list'larga ham duch kelishingiz mumkin.

Singly linked list'lar bir node'dan keyingisiga chiziqli yo'l bo'ylab boradi. Har bir node zanjirdagi keyingi node'ga ishora qiluvchi aynan bitta reference'ga ega. Siz list'ni uning head'idan tail'igacha faqat bir yo'nalishda traverse qilasiz.

Oldingi bo'limlarda ko'rgan Python implementatsiyangiz singly linked list edi. Boshqa turdagi linked list'lar uchun kod ko'plab umumiy xususiyatlarga ega, lekin bir nechta muhim jihatlarda farq qiladi.

Doubly Linked Lists

Singly linked list va doubly linked list o'rtasidagi asosiy farq shundaki, doubly linked list'larda har bir node'da ikkita reference bo'ladi. Har bir node zanjirdagi ham oldingi, ham keyingi node'ga ishora qiladi. Bu shuni anglatadiki, faqat oldinga harakatlanish mumkin bo'lgan singly linked list'dan farqli o'laroq, list bo'ylab oldinga ham, orqaga ham harakatlanishingiz mumkin. List bo'ylab orqaga harakatlana olish ba'zi use case'lar uchun foydali bo'lishi mumkin bo'lsa-da, qo'shimcha reference'lar uchun ma'lumot saqlash xotira sarfini oshiradi.

Doubly linked list uchun Node Python sinfingiz quyidagicha o'zgaradi:

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

Yangi prev attribute'iga e'tibor bering. Bu attribute linked list'dagi oldingi node'ga ishora qiladi va list bo'ylab orqaga harakatlanishga yordam beradi.

Ushbu sinf yordamida node yaratganingizda next'ni ham, prev'ni ham o'rnatishingiz mumkin:

head = Node(100)
second = Node(200)

head.next = second
second.prev = head

Doubly linked list yaratishda LinkedList sinfi ham odatda bitta muhim yangilanishni oladi. head'ni kuzatishdan tashqari, endi unda tail reference'i ham bo'ladi, u orqaga traverse qilish uchun boshlang'ich nuqta vazifasini bajaradi:

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

Singly linked list uchun yozgan method'laringiz esa bir nechta muhim jihatlarda o'zgaradi:

• append(): Eski tail uchun next'ni va tail'dagi yangi node uchun prev'ni o'rnating

• traverse(): List bo'ylab oldinga yoki orqaga yurish imkoniyatini qo'shing

• search(): List'ning old yoki orqa tomonidan boshlab qidirish imkoniyatini qo'shing

• remove(): Qo'shni node'larning next va prev reference'larini yangilang

Circular Linked Lists

Circular linked list yaratganingizda list'ingizning tail'i None'ga ishora qilish o'rniga qaytib head'ga ulanadi. Shu sababli circular linked list'ni halqa deb tasavvur qilishingiz mumkin. Circular linked list'lar singly yoki doubly linked bo'lishi mumkin va ularning implementatsiyalari asosiy tuzilishining katta qismi bir xil.

Circular linked list uchun Node sinfi singly yoki doubly linked list'dagi bilan bir xil tuzilishga ega, faqat oxirgi node'ingiz aylanib list'ingizning birinchi node'iga ishora qilishiga ishonch hosil qiling. Singly linked misolni quyidagicha yaratishingiz mumkin:

head = Node(100)
second = Node(200)
third = Node(300)

head.next = second
second.next = third
third.next = head    # Tail points to head

LinkedList sinfining constructor'i o'zgarishsiz qoladi, lekin circular linked list'ni traverse qilish method'i o'zgaradi, chunki bu turdagi list'da tabiiy None tugash nuqtasi yo'q. Xususan, circular linked list bo'ylab yurish uchun sizga aniq to'xtash sharti kerak bo'ladi:

def traverse(self):
    # Detect empty list
    if self.head is None:
        return

    current = self.head

    while True:
        print(current.data)
        current = current.next

        # Stop when reaching head once more
        if current == self.head:
            break

Shundan so'ng o'zingizning circular linked list'ingizni yaratib, uni traverse qilishingiz mumkin:

circular_linked_list = LinkedList()
circular_linked_list.head = head

circular_linked_list.traverse()

# Expected result:
# 100
# 200
# 300

E'tibor bering, boshqa method'lar ham kichik o'zgarishlarni talab qilishi mumkin. Masalan, append() None'ga ishora qiladigan node'ni emas, balki qaytib head'ga ishora qiladigan node'ni qidirishi kerak. So'ngra yangi node'ning reference'ini head'ga o'rnatib, yangi node'ni tail'ga aylantirishingiz kerak.

Pirovardida singly linked list'lar eng oddiy tuzilmani taqdim etadi, doubly va circular linked list'lar esa qo'shimcha reference'lar yoki murakkabroq mantiq evaziga qo'shimcha moslashuvchanlik beradi.

Kod misollari bilan klassik intervyu savollari

Linked list'lar haqidagi savollar coding intervyularida tez-tez uchraydi. Ko'pincha traversal masalalari yoki list reference'larini o'zgartiradigan masalalar ustida bosh qotirishingizga to'g'ri keladi. Avval qaysi turdagi linked list bilan ishlayotganingizni aniqlab oling, so'ng javobingiz edge case'larni to'g'ri qamrab olishiga ishonch hosil qilish uchun ular haqida o'ylab ko'ring. Boshqa savollar ham ko'p bo'lsa-da, bu yerda linked list bo'yicha eng keng tarqalgan intervyu mavzularidan ba'zilarini ko'rib chiqamiz.

Linked list'ni qanday teskari aylantirasiz?

Linked list bo'yicha barcha intervyu savollari ichida bu, ehtimol, eng mashhuri. Intervyu oluvchilar bu savolni berganda odatda prev reference'lari bo'lmagan singly linked list'ni nazarda tutishadi, lekin boshlashdan oldin buni albatta aniqlashtirib oling.

Singly linked list'ni teskari aylantirish uchun list'ingizni traverse qiling va uchta elementni kuzatib boring: oldingi, joriy va keyingi node'lar. current.next'ni keyingi node o'rniga oldingi node'ga ishora qiladigan qilib o'zgartirishingiz kerak bo'ladi, lekin zanjirni uzib, list'ning qolgan qismiga murojaatni yo'qotib qo'ymaslik uchun current.next'ni qayta yozishdan oldin list'da qaysi node keyin kelishini vaqtincha saqlab qo'yishni unutmang.

Mana singly linked list uchun LinkedList sinfingizga qo'shishingiz mumkin bo'lgan method:

def reverse(self):
    previous = None
    current = self.head

    while current is not None:		# Continue through tail node
        next_node = current.next		# Save next node 
        current.next = previous		# Switch reference to previous
        previous = current			# Get ready for next iteration
        current = next_node

    self.head = previous			# Update head to be old tail

Barcha reference'larni teskari aylantirganingizdan so'ng eski tail yangi head'ga aylanadi, shuning uchun self.head'ni previous'ga o'rnating. Aytgancha, big-O notation bo'yicha bu yondashuv O(n) vaqt va O(1) qo'shimcha xotira oladi, chunki u list'ni bir marta traverse qiladi va faqat bir nechta reference'ni saqlab turadi.

Linked list'dagi cycle'ni qanday aniqlaysiz?

Agar linked list'ni teskari aylantirish 1-o'rinda bo'lsa, cycle'ni aniqlash, ehtimol, linked list'lar haqidagi 2-eng keng tarqalgan intervyu savolidir. Bu savolning kaliti — Floyd's cycle detection algorithm, u tortoise and hare algorithm deb ham ataladi.

Singly linked list deb faraz qilsak, cycle node oxir-oqibat None'ga yetib borish o'rniga qaytib oldingi node'lardan biriga ishora qilganda yuzaga keladi. Bu oddiy traversal uchun muammo tug'diradi, chunki u cheksiz davom etishi mumkin.

Cycle'ni ikkita pointer yordamida aniqlashingiz mumkin:

• slow — har bir iteratsiyada faqat bitta node oldinga siljiydi

• fast — har bir iteratsiyada ikkita node oldinga siljiydi

Agar fast list'ingiz oxiriga yetib borsa, linked list'ingizda cycle yo'q, lekin slow va fast oxir-oqibat bir xil node'ga reference qilsa, sizda cycle bor.

Ushbu method'ni LinkedList sinfingizga qo'shish cycle'ni aniqlash vazifasini bajaradi:

def has_cycle(self):
    slow = self.head
    fast = self.head

    # Continue while fast can advance
    while fast is not None and fast.next is not None:
        slow = slow.next		# Advance one node
        fast = fast.next.next	# Advance two nodes

        # Cycle detected if slow and fast meet
        if slow == fast:
            return True

    return False  # No cycle if fast reaches the end of the list

Yuqoridagi kodda avval tashrif buyurilgan har bir node uchun elementlarni saqlashingiz shart emas, chunki siz faqat cycle mavjudligini aniqlamoqchisiz. Complexity nuqtai nazaridan bu yechim node'lar bo'ylab yurish uchun O(n) vaqt va O(1) oraliq xotira oladi.

Linked list'ning o'rtasini qanday topasiz?

Yana singly linked list deb faraz qilsak, bu masala dastlab oddiy tuyulishi mumkin. List'ingizni traverse qilib, node'lar sonini sanab, so'ngra o'rtadagi nuqtagacha yana bir marta traverse qilishingiz mumkin. Bu yechim ishlasa-da, u eng samarali implementatsiya emas.

Buning o'rniga slow va fast pointer'laridan foydalanib, o'rtani bitta traversal bilan topishingiz mumkin. Cycle detection algoritmidagi asosiy usulning o'zidan foydalaning:

• slow har bir iteratsiyada bitta node oldinga siljiydi

• fast har bir iteratsiyada ikkita node oldinga siljiydi

Lekin eng zo'r jihati mana bu: fast list oxiriga yetganda slow o'rtada bo'ladi.

Ushbu LinkedList method'i sizga o'rtadagi node'ni beradi; e'tibor bering, bo'sh list'lar kabi edge case uchun u shunchaki None qaytaradi:

def find_middle(self):
    slow = self.head
    fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    # slow gives you the midpoint when fast reaches the end
    return slow  

Node'lar soni toq bo'lsa, bitta aniq o'rta nuqta bo'ladi; biroq node'lar soni juft bo'lsa, ikkita mumkin bo'lgan "o'rta" bor. Bu implementatsiya ikkalasidan ikkinchisini qaytaradi, lekin intervyu oluvchidan qaysi birini afzal ko'rishini so'rab bilishingiz kerak. Bu usul ham O(n) time complexity'ga ega va O(1) yordamchi xotiradan foydalanadi.

Boshqa keng tarqalgan savollar

Linked list bo'yicha bilimni tekshiradigan intervyuda yuqoridagi uchta savoldan kamida bittasiga duch kelishingiz ehtimoli katta, lekin boshqa mashhur savollar qatoriga quyidagilar kiradi:

• Ikkita sort qilingan linked list'ni qanday merge qilasiz?

• Linked list oxiridan k-node'ni qanday topish mumkin?

• Linked list'dan takrorlanuvchi qiymatlarni qanday olib tashlaysiz?

• Linked list palindrom ekanligini yoki yo'qligini aniqlay olasizmi?

• Linked list'dan muayyan pozitsiyadagi node'ni qanday o'chirasiz?

• Linked list'larni sort qilishda merge sort quick sort'dan samaraliroqmi?

• Linked list'ning turli amallari time complexity va space complexity'sini taqqoslang.

Real hayotdagi qo'llanilishi

Linked list'lar elementlar bo'ylab oldinga va orqaga traverse qilish uchun juda qulay, ayniqsa doubly linked list bo'lsa. Brauzeringizning sahifalar tarixini doubly linked list sifatida tashkil qilishingiz mumkin. Oldingi sahifalarga o'tish yangiroq sahifalarga oldinga o'tish kabi oson bo'lardi. Musiqa playlist'i uchun ham xuddi shunday. Tinglovchi oldingi qo'shiqni qayta tinglash uchun orqaga qaytishi yoki qo'shiq unga yoqmasa, list'da oldinga o'tib ketishi mumkin. Hatto playlist'ni uzluksiz takrorlash uchun circular linked list ham yaratishingiz mumkin.

Linked list'lar, shuningdek, tez-tez yangi node'lar qo'shish yoki elementlarni o'chirish kerak bo'lganda va tegishli node'larga allaqachon murojaatingiz bo'lganda foydali. Foydalanuvchining tahrirlarini linked list yordamida kuzatib borishni tasavvur qiling. U tarixga yangi amallar qo'shib borar ekan, oldingi tahrirlarni bekor qilish uchun bemalol orqaga yoki ularni qayta bajarish uchun oldinga o'tishi mumkin. Linked list'lar graph'lardagi adjacency list'larni ifodalashda yoki hash table'larni amalga oshirishda separate chaining deb ataladigan usul orqali collision'larni hal qilishda ham asqotadi. Linked list'lardan queue va deque'lar uchun foydalanishingiz mumkin, ammo Python'da bu use case uchun odatda standart kutubxonadagi collections.deque'dan foydalanasiz.

Linked list'ning built-in muqobillari

Python'da built-in linked list ma'lumotlar tuzilmasi yo'q, lekin shunga o'xshash asosiy xatti-harakatlarga erishish uchun bir nechta tayyor variantlar mavjud. Bu muqobillardan foydalansangiz, o'zingizning linked list'ingizni amalga oshirishingizga kamdan-kam ehtiyoj tug'iladi.

list

Python'ning umumiy list obyekti ma'lumotlar ketma-ketligini saqlashda sizga kerak bo'ladigan ishlarning ko'pini bajara oladi. list linked list emas, balki dinamik massivdir. Linked list'dan farqli o'laroq, elementlarni index bo'yicha O(1), ya'ni konstant vaqtda topishingiz mumkin. Oddiy list oxiriga element qo'shish yoki oxiridan element olib tashlashda ancha samarali: qo'shish amortized O(1) vaqt oladi, oxirgi elementni olib tashlash esa O(1) time complexity'ga ega. Biroq list'ning boshi yoki o'rta qismlariga element qo'shish yoki ulardan element olib tashlash O(n) vaqt oladi, chunki ketma-ketlikni buzmaslik uchun elementlarni list bo'ylab siljitishingizga to'g'ri keladi.

collections.deque

Standart kutubxonadagi collections moduli deque deb ataladigan yana bir ma'lumotlar tuzilmasini taklif qiladi. deque — double-ended queue bo'lib, boshidan yoki oxiridan elementlarni oson qo'shish yoki olib tashlash imkonini beradi. Har ikki uchidan qo'shish yoki o'chirish atigi O(1) time complexity'ga ega, shuning uchun deque queue va stack'larni amalga oshirish uchun ajoyib variant. Biroq u index bo'yicha elementni tez topish uchun mo'ljallanmagan, shuning uchun agar sizga aynan shu funksionallik kerak bo'lsa, oddiy list'da qolishni tanlashingiz mumkin.

Ma'lumotlar tuzilmalarining time complexity'si va unumdorligini taqqoslash

Standart amallar uchun linked list'larning time complexity'si list va deque bilan qanday taqqoslanishi quyida keltirilgan:

Amal	Linked list	list	deque
Index bo'yicha murojaat	O(n)	O(1)	O(n)*
Qiymat bo'yicha qidirish	O(n)	O(n)	O(n)
Boshiga qo'shish/boshidan o'chirish	O(1)	O(n)	O(1)
Oxiriga qo'shish	O(1)**	O(1) amortized	O(1)
Ma'lum node'da qo'shish/o'chirish	O(1)	–	–

*deque uchun index bo'yicha murojaat har ikki uchida O(1), o'rtaga tomon esa O(n)gacha sekinlashadi.
**Agar tail reference'ini saqlamasangiz, oxiriga qo'shish linked list'ni traverse qilish uchun O(n) talab qiladi.

Linked list'dan qachon foydalanmaslik kerak

Ba'zi vaziyatlarda linked list'dan foydalanish shunchaki ma'noga ega emas. Agar elementlarni index bo'yicha muntazam olish uchun random access kerak bo'lsa, standart Python list'idan foydalaning. Xuddi shunday, agar asosan oxiriga element qo'shib, to'plamingiz bo'ylab iteratsiya qiladigan bo'lsangiz ham list'dan foydalaning.

Queue va stack masalalari uchun, ehtimol, deque'ni tanlaysiz, chunki ular bunday holatlar uchun samarali va deque Python'da allaqachon amalga oshirilgan.

Linked list'lar xotira bilan bog'liq muammolarga ega, chunki ular node reference'lari uchun ma'lumot saqlashi kerak. Agar qaysi node'ni o'chirish yoki qaysi node yoniga qo'shish kerakligini oldindan bilmasangiz, ularning O(1) qayta ulash afzalligi O(n) traversal time complexity'si ortida yo'qolib ketadi.

Umuman olganda, Python linked list'ini shunchaki qila olganingiz uchungina amalga oshirmang. Ularni list bo'ylab tez-tez oldinga va orqaga yurish yoki ma'lum node'larda qo'shish/o'chirish kerak bo'ladigan maxsus holatlar uchun saqlab qo'ying. Python dasturchilari kundalik vazifalar uchun odatda list va deque'ni afzal ko'radi.

Xulosa

Python'da built-in linked list yo'q, lekin Node va LinkedList sinflari yordamida linked list'ni o'zingiz yaratishingiz mumkin. Ehtimol, LinkedList sinfida yangi node'lar qo'shish, list'ingizni traverse qilish, node'larni qidirish va eski node'larni o'chirish uchun method'lar yozishni xohlaysiz. Shuningdek, linked list'ni teskari aylantirish, cycle'ni aniqlash yoki o'rta nuqtani topish uchun method'lar ham qo'shishingiz mumkin, ayniqsa linked list bo'yicha eng keng tarqalgan intervyu savollarining ba'zilarini yechayotganda.

Singly linked list'lar sizga klassik, bir yo'nalishli node'lar zanjirini beradi, lekin keyingi va oldingi elementlarga reference'lari bo'lgan doubly linked list'larga ham duch kelishingiz mumkin. Tail node head'ga ishora qiladigan circular linked list ham bo'lishi mumkin. Faqat avvalo vaziyatingiz haqiqatan ham linked list'ni talab qilishiga ishonch hosil qiling. Python'da implementatsiyaga ketadigan vaqtingizni tejaydigan va use case'ingizga, ehtimol, yaxshiroq mos keladigan tayyor list va deque ma'lumotlar tuzilmalari mavjud.

Linked list bo'yicha mahoratingizni ko'rsatishga tayyormisiz? AI Tutor bilan bellashib ko'ring. Bilimlar zanjir reaksiyasini boshlash uchun ushbu prompt'dan foydalaning: