Module linked_list 

Linked List (bog’langan ro’yxat)

Darslik: 06-linked-list/

Bog’langan ro’yxat — elementlar (tugunlar) xotirada yonma-yon turmaydigan, har biri keyingisining manzilini saqlaydigan chiziqli struktura.

 HEAD → [10 | •] → [20 | •] → [30 | ✕]

Vec bilan solishtirish

Amal	Vec<T>	Linked List
Boshiga qo’shish	O(n)	O(1)
Oxiriga qo’shish	O(1)*	O(n) (yoki tail bilan O(1))
i -elementga murojaat	O(1)	O(n)
Ma’lum tugunni o’chirish	O(n)	O(1)
Kesh (cache) samaradorligi	Yuqori	Past

Rustda linked list — nega qiyin?

Rustda har bir qiymatning bitta egasi bo’ladi. Linked listda esa tugunlar bir-birini “ushlab” turadi. Shuning uchun:

• Bir tomonlama ro’yxat: Option<Box<Node<T>>> — egalik zanjiri, muammosiz.
• Ikki tomonlama ro’yxat: Rc<RefCell<Node<T>>> (oldinga) + Weak (orqaga) — Weak bo’lmasa sikl hosil bo’lib, xotira hech qachon bo’shamaydi.

Amaliy maslahat: Rustda 95% hollarda Vec yoki VecDeque linked listdan tezroq. Linked listni faqat “o’rtadan tez o’chirish” haqiqatan kerak bo’lganda ishlating. Bu modul — tushunish uchun.

Structs

DoublyLinkedList

Ikki tomonlama bog’langan ro’yxat: har bir tugun oldingi va keyingisini biladi.

SinglyLinkedList

Bir tomonlama bog’langan ro’yxat.