Endi Linked List qanday ishlashini bildik — append, traversal. Keling, uni List bilan solishtiramiz:
| List | Linked List | |
|---|---|---|
| Xotira | Pointerlar ketma-ket, ob'ektlar tarqoq | Har node alohida joyda |
| Indeks bilan olish | O(1) | O(n) |
| Oxiriga qo'shish | O(1) amortizatsiya | O(n) — oxirigacha yurish kerak |
| Boshiga qo'shish | O(n) | O(1) |
Indeks bilan olish: List pointerlarni ketma-ket saqlaydi, shuning uchun list[3] desangiz — to'g'ridan-to'g'ri 3-chi manzilga o'tadi (O(1)). Linked List da esa 3-chi elementga yetish uchun 1-chi → 2-chi → 3-chi nodeni birma-bir bosib o'tish kerak (O(n)).
Oxiriga qo'shish: List oxirida bo'sh joy zahira qilib qo'yadi. Ko'pincha append() shunchaki bo'sh joyga yozadi (O(1)). Joy tugaganda — yangi kattaroq massiv yaratib, hammasini ko'chiradi (O(n)), lekin bu kamdan-kam bo'ladi. O'rtacha hisobda — O(1). Linked List da esa oxirgi nodeni topish uchun boshidan oxirigacha yurish kerak (O(n)).
Boshiga qo'shish: List da insert(0, x) qilsangiz — barcha elementlar bitta o'ringa suriladi (O(n)). Linked List da esa yangi node yaratib, next ni eski head ga bog'laysiz — tamom (O(1)):
# List — barcha elementlar suriladi
nums = [10, 20, 30]
nums.insert(0, 5) # 10, 20, 30 hammasi o'ngga surildi → O(n)
# Linked List — faqat pointerlar o'zgaradi
yangi = Node(5)
yangi.next = head # yangi node eski boshga bog'landi
head = yangi # head endi yangi nodeni ko'rsatadi
# 5 → 10 → 20 → 30 → None — hech narsa surilmadi → O(1)Linked List qachon yaxshi:
List qachon yaxshi: