rust_algorithms/linked_list/
doubly.rs

1//! Ikki tomonlama bog'langan ro'yxat — `Rc<RefCell<..>>` + `Weak` asosida.
2
3use std::cell::RefCell;
4use std::rc::{Rc, Weak};
5
6type Link<T> = Option<Rc<RefCell<Node<T>>>>;
7
8struct Node<T> {
9    value: T,
10    next: Link<T>,
11    /// Orqaga havola **Weak** — aks holda ikki tugun bir-birini abadiy ushlab turadi
12    /// (reference cycle) va xotira hech qachon bo'shamaydi.
13    prev: Option<Weak<RefCell<Node<T>>>>,
14}
15
16/// Ikki tomonlama bog'langan ro'yxat: har bir tugun oldingi va keyingisini biladi.
17///
18/// ```text
19///  ✕ ⇄ [10] ⇄ [20] ⇄ [30] ⇄ ✕
20///       ^head            ^tail
21/// ```
22///
23/// Ikkala uchdan ham qo'shish/olish **O(1)** — shuning uchun u deque sifatida ishlaydi.
24///
25/// ## Rust darsi: `Rc`, `RefCell`, `Weak`
26///
27/// - `Rc<T>` — bitta qiymatga **bir nechta egalik** (havolalar sanoqchisi bilan);
28/// - `RefCell<T>` — o'zgartirishni **ish vaqtida** tekshirish (`Rc` ichida `&mut` olib
29///   bo'lmaydi, `RefCell` shu cheklovni "ichkariga" ko'chiradi);
30/// - `Weak<T>` — sanoqchini oshirmaydigan havola; sikllarni oldini oladi.
31///
32/// Bu narx bilan keladi: har murojaatda `borrow()` tekshiruvi. Shuning uchun
33/// Rustda odatda `VecDeque` afzal.
34///
35/// # Misol
36/// ```
37/// use rust_algorithms::linked_list::DoublyLinkedList;
38///
39/// let mut l = DoublyLinkedList::new();
40/// l.push_back(2);
41/// l.push_back(3);
42/// l.push_front(1);
43/// assert_eq!(l.to_vec(), vec![1, 2, 3]);
44/// assert_eq!(l.to_vec_rev(), vec![3, 2, 1]);
45///
46/// assert_eq!(l.pop_back(), Some(3));
47/// assert_eq!(l.pop_front(), Some(1));
48/// assert_eq!(l.len(), 1);
49/// ```
50pub struct DoublyLinkedList<T> {
51    head: Link<T>,
52    tail: Link<T>,
53    len: usize,
54}
55
56impl<T> Default for DoublyLinkedList<T> {
57    fn default() -> Self {
58        Self::new()
59    }
60}
61
62impl<T> DoublyLinkedList<T> {
63    /// Bo'sh ro'yxat.
64    pub fn new() -> Self {
65        Self {
66            head: None,
67            tail: None,
68            len: 0,
69        }
70    }
71
72    /// Boshiga qo'shadi — O(1).
73    pub fn push_front(&mut self, value: T) {
74        let yangi = Rc::new(RefCell::new(Node {
75            value,
76            next: None,
77            prev: None,
78        }));
79        match self.head.take() {
80            Some(eski) => {
81                eski.borrow_mut().prev = Some(Rc::downgrade(&yangi));
82                yangi.borrow_mut().next = Some(eski);
83                self.head = Some(yangi);
84            }
85            None => {
86                self.tail = Some(Rc::clone(&yangi));
87                self.head = Some(yangi);
88            }
89        }
90        self.len += 1;
91    }
92
93    /// Oxiriga qo'shadi — O(1) (bir tomonlama ro'yxatdan farqi shu!).
94    pub fn push_back(&mut self, value: T) {
95        let yangi = Rc::new(RefCell::new(Node {
96            value,
97            next: None,
98            prev: None,
99        }));
100        match self.tail.take() {
101            Some(eski) => {
102                yangi.borrow_mut().prev = Some(Rc::downgrade(&eski));
103                eski.borrow_mut().next = Some(Rc::clone(&yangi));
104                self.tail = Some(yangi);
105            }
106            None => {
107                self.head = Some(Rc::clone(&yangi));
108                self.tail = Some(yangi);
109            }
110        }
111        self.len += 1;
112    }
113
114    /// Boshidan oladi — O(1).
115    pub fn pop_front(&mut self) -> Option<T> {
116        self.head.take().map(|eski| {
117            match eski.borrow_mut().next.take() {
118                Some(yangi_head) => {
119                    yangi_head.borrow_mut().prev = None;
120                    self.head = Some(yangi_head);
121                }
122                None => self.tail = None, // ro'yxat bo'shab qoldi
123            }
124            self.len -= 1;
125            Rc::try_unwrap(eski)
126                .ok()
127                .expect("boshqa egasi qolmagan bo'lishi kerak")
128                .into_inner()
129                .value
130        })
131    }
132
133    /// Oxiridan oladi — O(1).
134    pub fn pop_back(&mut self) -> Option<T> {
135        self.tail.take().map(|eski| {
136            match eski.borrow_mut().prev.take() {
137                Some(weak_prev) => {
138                    let prev = weak_prev.upgrade().expect("prev tirik bo'lishi kerak");
139                    prev.borrow_mut().next = None;
140                    self.tail = Some(prev);
141                }
142                None => self.head = None,
143            }
144            self.len -= 1;
145            Rc::try_unwrap(eski)
146                .ok()
147                .expect("boshqa egasi qolmagan bo'lishi kerak")
148                .into_inner()
149                .value
150        })
151    }
152
153    /// Elementlar soni.
154    pub fn len(&self) -> usize {
155        self.len
156    }
157
158    /// Bo'shmi?
159    pub fn is_empty(&self) -> bool {
160        self.len == 0
161    }
162}
163
164impl<T: Clone> DoublyLinkedList<T> {
165    /// Birinchi qiymatning nusxasi.
166    pub fn front(&self) -> Option<T> {
167        self.head.as_ref().map(|n| n.borrow().value.clone())
168    }
169
170    /// Oxirgi qiymatning nusxasi.
171    pub fn back(&self) -> Option<T> {
172        self.tail.as_ref().map(|n| n.borrow().value.clone())
173    }
174
175    /// Boshidan oxirigacha vektor.
176    pub fn to_vec(&self) -> Vec<T> {
177        let mut out = Vec::with_capacity(self.len);
178        let mut kursor = self.head.clone();
179        while let Some(node) = kursor {
180            out.push(node.borrow().value.clone());
181            kursor = node.borrow().next.clone();
182        }
183        out
184    }
185
186    /// Oxiridan boshigacha vektor — `prev` havolalari ishlayotganini ko'rsatadi.
187    pub fn to_vec_rev(&self) -> Vec<T> {
188        let mut out = Vec::with_capacity(self.len);
189        let mut kursor = self.tail.clone();
190        while let Some(node) = kursor {
191            out.push(node.borrow().value.clone());
192            kursor = node.borrow().prev.as_ref().and_then(|w| w.upgrade());
193        }
194        out
195    }
196}
197
198impl<T> FromIterator<T> for DoublyLinkedList<T> {
199    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
200        let mut l = Self::new();
201        for x in iter {
202            l.push_back(x);
203        }
204        l
205    }
206}
207
208/// Rekursiv `Drop` dan qochish uchun tugunlarni tsiklda bo'shatamiz.
209impl<T> Drop for DoublyLinkedList<T> {
210    fn drop(&mut self) {
211        while self.pop_front().is_some() {}
212    }
213}
214
215#[cfg(test)]
216mod tests {
217    use super::*;
218
219    #[test]
220    fn ikki_uchdan_ham_ishlaydi() {
221        let mut l = DoublyLinkedList::new();
222        l.push_back(1);
223        l.push_back(2);
224        l.push_front(0);
225        assert_eq!(l.to_vec(), vec![0, 1, 2]);
226        assert_eq!(l.front(), Some(0));
227        assert_eq!(l.back(), Some(2));
228        assert_eq!(l.len(), 3);
229    }
230
231    #[test]
232    fn teskari_yurish_mos_keladi() {
233        let l: DoublyLinkedList<i32> = (1..=6).collect();
234        let mut teskari = l.to_vec();
235        teskari.reverse();
236        assert_eq!(l.to_vec_rev(), teskari);
237    }
238
239    #[test]
240    fn bosh_royxat() {
241        let mut l: DoublyLinkedList<i32> = DoublyLinkedList::new();
242        assert!(l.is_empty());
243        assert_eq!(l.pop_front(), None);
244        assert_eq!(l.pop_back(), None);
245        assert_eq!(l.front(), None);
246        assert_eq!(l.back(), None);
247    }
248
249    #[test]
250    fn bitta_element() {
251        let mut l = DoublyLinkedList::new();
252        l.push_back(42);
253        assert_eq!(l.pop_back(), Some(42));
254        assert!(l.is_empty());
255
256        l.push_front(7);
257        assert_eq!(l.pop_front(), Some(7));
258        assert!(l.is_empty());
259        assert_eq!(l.to_vec(), Vec::<i32>::new());
260    }
261
262    #[test]
263    fn deque_kabi_ishlatish() {
264        let mut l: DoublyLinkedList<i32> = (1..=5).collect();
265        assert_eq!(l.pop_front(), Some(1));
266        assert_eq!(l.pop_back(), Some(5));
267        assert_eq!(l.pop_front(), Some(2));
268        assert_eq!(l.pop_back(), Some(4));
269        assert_eq!(l.to_vec(), vec![3]);
270    }
271
272    #[test]
273    fn katta_royxat_bosh_boladi() {
274        let l: DoublyLinkedList<usize> = (0..100_000).collect();
275        assert_eq!(l.len(), 100_000);
276        drop(l);
277    }
278}
rust_algorithms/linked_list/doubly.rs

rust_algorithms/linked_list/
doubly.rs
