rust_algorithms/linked_list/

singly.rs

//! Bir tomonlama bog'langan ro'yxat — `Option<Box<Node<T>>>` asosida.

/// Ro'yxatning bitta tuguni: qiymat + keyingi tugunga egalik.
#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

/// Bir tomonlama bog'langan ro'yxat.
///
/// `Option<Box<Node<T>>>` — Rustdagi eng tabiiy ko'rinish:
/// - `None` — ro'yxat/quyruq tugadi (`NULL` ning xavfsiz muqobili);
/// - `Box` — tugun heapda yashaydi, chunki uning o'lchami rekursiv.
///
/// # Misol
/// ```
/// use rust_algorithms::linked_list::SinglyLinkedList;
///
/// let mut list = SinglyLinkedList::new();
/// list.push_front(2);
/// list.push_front(1);
/// list.push_back(3);
/// assert_eq!(list.to_vec(), vec![1, 2, 3]);
///
/// list.reverse();
/// assert_eq!(list.to_vec(), vec![3, 2, 1]);
/// assert_eq!(list.pop_front(), Some(3));
/// assert_eq!(list.len(), 2);
/// ```
#[derive(Debug)]
pub struct SinglyLinkedList<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

impl<T> Default for SinglyLinkedList<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> SinglyLinkedList<T> {
    /// Bo'sh ro'yxat.
    pub fn new() -> Self {
        Self { head: None, len: 0 }
    }

    /// Boshiga qo'shadi — **O(1)**, linked listning asosiy afzalligi.
    pub fn push_front(&mut self, value: T) {
        let yangi = Box::new(Node {
            value,
            next: self.head.take(), // eski boshni yangi tugunga ulaymiz
        });
        self.head = Some(yangi);
        self.len += 1;
    }

    /// Boshidan oladi — **O(1)**.
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.value
        })
    }

    /// Oxiriga qo'shadi — O(n), chunki oxirigacha yurish kerak.
    pub fn push_back(&mut self, value: T) {
        let yangi = Box::new(Node { value, next: None });
        let mut kursor = &mut self.head;
        while let Some(node) = kursor {
            kursor = &mut node.next;
        }
        *kursor = Some(yangi);
        self.len += 1;
    }

    /// Oxirgi elementni oladi — O(n).
    pub fn pop_back(&mut self) -> Option<T> {
        self.head.as_ref()?;
        if self.head.as_ref()?.next.is_none() {
            return self.pop_front();
        }
        let mut kursor = &mut self.head;
        // oxirgidan oldingi tugungacha boramiz
        loop {
            let hozir = kursor.as_mut()?;
            if hozir.next.as_ref()?.next.is_none() {
                self.len -= 1;
                return hozir.next.take().map(|n| n.value);
            }
            kursor = &mut kursor.as_mut()?.next;
        }
    }

    /// Birinchi qiymatga qaraydi.
    pub fn front(&self) -> Option<&T> {
        self.head.as_ref().map(|n| &n.value)
    }

    /// `index` -qiymat (0 dan boshlab) — O(n).
    pub fn get(&self, index: usize) -> Option<&T> {
        let mut kursor = self.head.as_deref();
        for _ in 0..index {
            kursor = kursor?.next.as_deref();
        }
        kursor.map(|n| &n.value)
    }

    /// Ro'yxatni **joyida** teskari o'giradi — O(n), qo'shimcha xotirasiz.
    ///
    /// Klassik "uch ko'rsatkich" usuli: `prev`, `curr`, `next`.
    /// Har qadamda joriy tugunning strelkasini orqaga qaratamiz.
    ///
    /// ```text
    ///  boshida:  1 → 2 → 3 → ✕
    ///  1-qadam:  ✕ ← 1   2 → 3 → ✕
    ///  oxirida:  ✕ ← 1 ← 2 ← 3
    /// ```
    pub fn reverse(&mut self) {
        let mut prev: Option<Box<Node<T>>> = None;
        let mut curr = self.head.take();
        while let Some(mut node) = curr {
            curr = node.next.take(); // keyingisini saqlab qolamiz
            node.next = prev; // strelkani orqaga buramiz
            prev = Some(node);
        }
        self.head = prev;
    }

    /// O'rtadagi element (ikkita "ko'rsatkich" usuli: tez va sekin).
    ///
    /// **G'oya:** sekin ko'rsatkich 1 qadam, tez ko'rsatkich 2 qadam yuradi.
    /// Tez ko'rsatkich oxiriga yetganda sekini roppa-rosa o'rtada bo'ladi —
    /// ro'yxat uzunligini oldindan bilmasdan, **bitta** yurishda.
    ///
    /// # Misol
    /// ```
    /// use rust_algorithms::linked_list::SinglyLinkedList;
    ///
    /// let list: SinglyLinkedList<i32> = (1..=5).collect();
    /// assert_eq!(list.middle(), Some(&3));
    /// ```
    pub fn middle(&self) -> Option<&T> {
        let mut sekin = self.head.as_deref()?;
        let mut tez = self.head.as_deref();

        while let Some(t) = tez {
            match t.next.as_deref() {
                Some(keyingi) => {
                    tez = keyingi.next.as_deref();
                    sekin = sekin.next.as_deref()?;
                }
                None => break,
            }
        }
        Some(&sekin.value)
    }

    /// Elementlar soni — O(1) (hisoblab boriladi).
    pub fn len(&self) -> usize {
        self.len
    }

    /// Bo'shmi?
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Boshidan oxirigacha iterator.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            kursor: self.head.as_deref(),
        }
    }

    /// Vektorga aylantiradi (nusxa olmasdan — havolalar orqali yig'adi).
    pub fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        self.iter().cloned().collect()
    }
}

impl<T: PartialEq> SinglyLinkedList<T> {
    /// Qiymat ro'yxatda bormi? — O(n).
    pub fn contains(&self, value: &T) -> bool {
        self.iter().any(|x| x == value)
    }
}

/// [`SinglyLinkedList::iter`] qaytaradigan iterator.
pub struct Iter<'a, T> {
    kursor: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let node = self.kursor?;
        self.kursor = node.next.as_deref();
        Some(&node.value)
    }
}

impl<T> FromIterator<T> for SinglyLinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = Self::new();
        // Avval boshiga qo'shib, keyin teskari o'girish — O(n),
        // har safar oxirigacha yurishdan (O(n²)) ko'ra tezroq.
        for x in iter {
            list.push_front(x);
        }
        list.reverse();
        list
    }
}

/// Rekursiv `Drop` stack overflow bermasligi uchun qo'lda bo'shatamiz.
///
/// Standart `drop` millionta tugunli ro'yxatda rekursiv chaqiriladi va stack
/// tugab qoladi. Bu yerda tugunlarni tsikl bilan birma-bir ozod qilamiz.
impl<T> Drop for SinglyLinkedList<T> {
    fn drop(&mut self) {
        let mut kursor = self.head.take();
        while let Some(mut node) = kursor {
            kursor = node.next.take();
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn push_pop_front() {
        let mut l = SinglyLinkedList::new();
        assert_eq!(l.pop_front(), None);
        l.push_front(1);
        l.push_front(2);
        assert_eq!(l.front(), Some(&2));
        assert_eq!(l.pop_front(), Some(2));
        assert_eq!(l.pop_front(), Some(1));
        assert!(l.is_empty());
    }

    #[test]
    fn push_back_va_pop_back() {
        let mut l = SinglyLinkedList::new();
        assert_eq!(l.pop_back(), None);
        for i in 1..=4 {
            l.push_back(i);
        }
        assert_eq!(l.to_vec(), vec![1, 2, 3, 4]);
        assert_eq!(l.pop_back(), Some(4));
        assert_eq!(l.pop_back(), Some(3));
        assert_eq!(l.len(), 2);
        assert_eq!(l.to_vec(), vec![1, 2]);
    }

    #[test]
    fn teskari_ogirish() {
        let mut bosh: SinglyLinkedList<i32> = SinglyLinkedList::new();
        bosh.reverse();
        assert!(bosh.is_empty());

        let mut l: SinglyLinkedList<i32> = (1..=5).collect();
        l.reverse();
        assert_eq!(l.to_vec(), vec![5, 4, 3, 2, 1]);
        assert_eq!(l.len(), 5);
    }

    #[test]
    fn ortasini_topish() {
        let bosh: SinglyLinkedList<i32> = SinglyLinkedList::new();
        assert_eq!(bosh.middle(), None);

        let toq: SinglyLinkedList<i32> = (1..=5).collect();
        assert_eq!(toq.middle(), Some(&3));

        let juft: SinglyLinkedList<i32> = (1..=4).collect();
        assert_eq!(juft.middle(), Some(&3)); // ikkinchi o'rta

        let bitta: SinglyLinkedList<i32> = (1..=1).collect();
        assert_eq!(bitta.middle(), Some(&1));
    }

    #[test]
    fn get_va_contains() {
        let l: SinglyLinkedList<i32> = (10..15).collect();
        assert_eq!(l.get(0), Some(&10));
        assert_eq!(l.get(4), Some(&14));
        assert_eq!(l.get(5), None);
        assert!(l.contains(&12));
        assert!(!l.contains(&99));
    }

    #[test]
    fn katta_royxat_stack_overflow_bermaydi() {
        let l: SinglyLinkedList<usize> = (0..200_000).collect();
        assert_eq!(l.len(), 200_000);
        drop(l); // Drop implementatsiyasi tufayli panic bo'lmaydi
    }
}