linked_list.rs - source
Description: Source of the Rust file `library/alloc/src/collections/linked_list.rs`.

#
alloc/collections/
linked_list.rs

    1//! A doubly-linked list with owned nodes.
    2//!
    3//! The `LinkedList` allows pushing and popping elements at either end
    4//! in constant time.
    5//!
    6//! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
    7//! array-based containers are generally faster,
    8//! more memory efficient, and make better use of CPU cache.
    9//!
    10//! [`Vec`]: crate::vec::Vec
    11//! [`VecDeque`]: super::vec_deque::VecDeque
    12
    13#![stable(feature = "rust1", since = "1.0.0")]
    14
    15use core::cmp::Ordering;
    16use core::hash::{Hash, Hasher};
    17use core::iter::FusedIterator;
    18use core::marker::PhantomData;
    19use core::ptr::NonNull;
    20use core::{fmt, mem};
    21
    22use super::SpecExtend;
    23use crate::alloc::{Allocator, Global};
    24use crate::boxed::Box;
    25
    26#[cfg(test)]
    27mod tests;
    28
    29/// A doubly-linked list with owned nodes.
    30///
    31/// The `LinkedList` allows pushing and popping elements at either end
    32/// in constant time.
    33///
    34/// A `LinkedList` with a known list of items can be initialized from an array:
    35/// ```
    36/// use std::collections::LinkedList;
    37///
    38/// let list = LinkedList::from([1, 2, 3]);
    39/// ```
    40///
    41/// NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
    42/// array-based containers are generally faster,
    43/// more memory efficient, and make better use of CPU cache.
    44///
    45/// [`Vec`]: crate::vec::Vec
    46/// [`VecDeque`]: super::vec_deque::VecDeque
    47#[stable(feature = "rust1", since = "1.0.0")]
    48#[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")]
    49#[rustc_insignificant_dtor]
    50pub struct LinkedList<
    51    T,
    52    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    53> {
    54    head: Option<NonNull<Node<T>>>,
    55    tail: Option<NonNull<Node<T>>>,
    56    len: usize,
    57    alloc: A,
    58    marker: PhantomData<Box<Node<T>, A>>,
    59}
    60
    61struct Node<T> {
    62    next: Option<NonNull<Node<T>>>,
    63    prev: Option<NonNull<Node<T>>>,
    64    element: T,
    65}
    66
    67/// An iterator over the elements of a `LinkedList`.
    68///
    69/// This `struct` is created by [`LinkedList::iter()`]. See its
    70/// documentation for more.
    71#[must_use = "iterators are lazy and do nothing unless consumed"]
    72#[stable(feature = "rust1", since = "1.0.0")]
    73pub struct Iter<'a, T: 'a> {
    74    head: Option<NonNull<Node<T>>>,
    75    tail: Option<NonNull<Node<T>>>,
    76    len: usize,
    77    marker: PhantomData<&'a Node<T>>,
    78}
    79
    80#[stable(feature = "collection_debug", since = "1.17.0")]
    81impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
    82    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    83        f.debug_tuple("Iter")
    84            .field(&*mem::ManuallyDrop::new(LinkedList {
    85                head: self.head,
    86                tail: self.tail,
    87                len: self.len,
    88                alloc: Global,
    89                marker: PhantomData,
    90            }))
    91            .field(&self.len)
    92            .finish()
    93    }
    94}
    95
    96// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    97#[stable(feature = "rust1", since = "1.0.0")]
    98impl<T> Clone for Iter<'_, T> {
    99    fn clone(&self) -> Self {
    100        Iter { ..*self }
    101    }
    102}
    103
    104/// A mutable iterator over the elements of a `LinkedList`.
    105///
    106/// This `struct` is created by [`LinkedList::iter_mut()`]. See its
    107/// documentation for more.
    108#[must_use = "iterators are lazy and do nothing unless consumed"]
    109#[stable(feature = "rust1", since = "1.0.0")]
    110pub struct IterMut<'a, T: 'a> {
    111    head: Option<NonNull<Node<T>>>,
    112    tail: Option<NonNull<Node<T>>>,
    113    len: usize,
    114    marker: PhantomData<&'a mut Node<T>>,
    115}
    116
    117#[stable(feature = "collection_debug", since = "1.17.0")]
    118impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
    119    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    120        f.debug_tuple("IterMut")
    121            .field(&*mem::ManuallyDrop::new(LinkedList {
    122                head: self.head,
    123                tail: self.tail,
    124                len: self.len,
    125                alloc: Global,
    126                marker: PhantomData,
    127            }))
    128            .field(&self.len)
    129            .finish()
    130    }
    131}
    132
    133/// An owning iterator over the elements of a `LinkedList`.
    134///
    135/// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
    136/// (provided by the [`IntoIterator`] trait). See its documentation for more.
    137///
    138/// [`into_iter`]: LinkedList::into_iter
    139#[derive(Clone)]
    140#[stable(feature = "rust1", since = "1.0.0")]
    141pub struct IntoIter<
    142    T,
    143    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    144> {
    145    list: LinkedList<T, A>,
    146}
    147
    148#[stable(feature = "collection_debug", since = "1.17.0")]
    149impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
    150    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    151        f.debug_tuple("IntoIter").field(&self.list).finish()
    152    }
    153}
    154
    155impl<T> Node<T> {
    156    fn new(element: T) -> Self {
    157        Node { next: None, prev: None, element }
    158    }
    159
    160    fn into_element<A: Allocator>(self: Box<Self, A>) -> T {
    161        self.element
    162    }
    163}
    164
    165// private methods
    166impl<T, A: Allocator> LinkedList<T, A> {
    167    /// Adds the given node to the front of the list.
    168    ///
    169    /// # Safety
    170    /// `node` must point to a valid node in the list's allocator.
    171    /// This method takes ownership of the node, so the pointer should not be used again.
    172    #[inline]
    173    unsafe fn push_front_node(&mut self, node: NonNull<Node<T>>) {
    174        // This method takes care not to create mutable references to whole nodes,
    175        // to maintain validity of aliasing pointers into `element`.
    176        unsafe {
    177            (*node.as_ptr()).next = self.head;
    178            (*node.as_ptr()).prev = None;
    179            let node = Some(node);
    180
    181            match self.head {
    182                None => self.tail = node,
    183                // Not creating new mutable (unique!) references overlapping `element`.
    184                Some(head) => (*head.as_ptr()).prev = node,
    185            }
    186
    187            self.head = node;
    188            self.len += 1;
    189        }
    190    }
    191
    192    /// Removes and returns the node at the front of the list.
    193    #[inline]
    194    fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>> {
    195        // This method takes care not to create mutable references to whole nodes,
    196        // to maintain validity of aliasing pointers into `element`.
    197        self.head.map(|node| unsafe {
    198            let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
    199            self.head = node.next;
    200
    201            match self.head {
    202                None => self.tail = None,
    203                // Not creating new mutable (unique!) references overlapping `element`.
    204                Some(head) => (*head.as_ptr()).prev = None,
    205            }
    206
    207            self.len -= 1;
    208            node
    209        })
    210    }
    211
    212    /// Adds the given node to the back of the list.
    213    ///
    214    /// # Safety
    215    /// `node` must point to a valid node in the list's allocator.
    216    /// This method takes ownership of the node, so the pointer should not be used again.
    217    #[inline]
    218    unsafe fn push_back_node(&mut self, node: NonNull<Node<T>>) {
    219        // This method takes care not to create mutable references to whole nodes,
    220        // to maintain validity of aliasing pointers into `element`.
    221        unsafe {
    222            (*node.as_ptr()).next = None;
    223            (*node.as_ptr()).prev = self.tail;
    224            let node = Some(node);
    225
    226            match self.tail {
    227                None => self.head = node,
    228                // Not creating new mutable (unique!) references overlapping `element`.
    229                Some(tail) => (*tail.as_ptr()).next = node,
    230            }
    231
    232            self.tail = node;
    233            self.len += 1;
    234        }
    235    }
    236
    237    /// Removes and returns the node at the back of the list.
    238    #[inline]
    239    fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>> {
    240        // This method takes care not to create mutable references to whole nodes,
    241        // to maintain validity of aliasing pointers into `element`.
    242        self.tail.map(|node| unsafe {
    243            let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
    244            self.tail = node.prev;
    245
    246            match self.tail {
    247                None => self.head = None,
    248                // Not creating new mutable (unique!) references overlapping `element`.
    249                Some(tail) => (*tail.as_ptr()).next = None,
    250            }
    251
    252            self.len -= 1;
    253            node
    254        })
    255    }
    256
    257    /// Unlinks the specified node from the current list.
    258    ///
    259    /// Warning: this will not check that the provided node belongs to the current list.
    260    ///
    261    /// This method takes care not to create mutable references to `element`, to
    262    /// maintain validity of aliasing pointers.
    263    #[inline]
    264    unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
    265        let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut.
    266
    267        // Not creating new mutable (unique!) references overlapping `element`.
    268        match node.prev {
    269            Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
    270            // this node is the head node
    271            None => self.head = node.next,
    272        };
    273
    274        match node.next {
    275            Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
    276            // this node is the tail node
    277            None => self.tail = node.prev,
    278        };
    279
    280        self.len -= 1;
    281    }
    282
    283    /// Splices a series of nodes between two existing nodes.
    284    ///
    285    /// Warning: this will not check that the provided node belongs to the two existing lists.
    286    #[inline]
    287    unsafe fn splice_nodes(
    288        &mut self,
    289        existing_prev: Option<NonNull<Node<T>>>,
    290        existing_next: Option<NonNull<Node<T>>>,
    291        mut splice_start: NonNull<Node<T>>,
    292        mut splice_end: NonNull<Node<T>>,
    293        splice_length: usize,
    294    ) {
    295        // This method takes care not to create multiple mutable references to whole nodes at the same time,
    296        // to maintain validity of aliasing pointers into `element`.
    297        if let Some(mut existing_prev) = existing_prev {
    298            unsafe {
    299                existing_prev.as_mut().next = Some(splice_start);
    300            }
    301        } else {
    302            self.head = Some(splice_start);
    303        }
    304        if let Some(mut existing_next) = existing_next {
    305            unsafe {
    306                existing_next.as_mut().prev = Some(splice_end);
    307            }
    308        } else {
    309            self.tail = Some(splice_end);
    310        }
    311        unsafe {
    312            splice_start.as_mut().prev = existing_prev;
    313            splice_end.as_mut().next = existing_next;
    314        }
    315
    316        self.len += splice_length;
    317    }
    318
    319    /// Detaches all nodes from a linked list as a series of nodes.
    320    #[inline]
    321    fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
    322        let head = self.head.take();
    323        let tail = self.tail.take();
    324        let len = mem::replace(&mut self.len, 0);
    325        if let Some(head) = head {
    326            // SAFETY: In a LinkedList, either both the head and tail are None because
    327            // the list is empty, or both head and tail are Some because the list is populated.
    328            // Since we have verified the head is Some, we are sure the tail is Some too.
    329            let tail = unsafe { tail.unwrap_unchecked() };
    330            Some((head, tail, len))
    331        } else {
    332            None
    333        }
    334    }
    335
    336    #[inline]
    337    unsafe fn split_off_before_node(
    338        &mut self,
    339        split_node: Option<NonNull<Node<T>>>,
    340        at: usize,
    341    ) -> Self
    342    where
    343        A: Clone,
    344    {
    345        // The split node is the new head node of the second part
    346        if let Some(mut split_node) = split_node {
    347            let first_part_head;
    348            let first_part_tail;
    349            unsafe {
    350                first_part_tail = split_node.as_mut().prev.take();
    351            }
    352            if let Some(mut tail) = first_part_tail {
    353                unsafe {
    354                    tail.as_mut().next = None;
    355                }
    356                first_part_head = self.head;
    357            } else {
    358                first_part_head = None;
    359            }
    360
    361            let first_part = LinkedList {
    362                head: first_part_head,
    363                tail: first_part_tail,
    364                len: at,
    365                alloc: self.alloc.clone(),
    366                marker: PhantomData,
    367            };
    368
    369            // Fix the head ptr of the second part
    370            self.head = Some(split_node);
    371            self.len = self.len - at;
    372
    373            first_part
    374        } else {
    375            mem::replace(self, LinkedList::new_in(self.alloc.clone()))
    376        }
    377    }
    378
    379    #[inline]
    380    unsafe fn split_off_after_node(
    381        &mut self,
    382        split_node: Option<NonNull<Node<T>>>,
    383        at: usize,
    384    ) -> Self
    385    where
    386        A: Clone,
    387    {
    388        // The split node is the new tail node of the first part and owns
    389        // the head of the second part.
    390        if let Some(mut split_node) = split_node {
    391            let second_part_head;
    392            let second_part_tail;
    393            unsafe {
    394                second_part_head = split_node.as_mut().next.take();
    395            }
    396            if let Some(mut head) = second_part_head {
    397                unsafe {
    398                    head.as_mut().prev = None;
    399                }
    400                second_part_tail = self.tail;
    401            } else {
    402                second_part_tail = None;
    403            }
    404
    405            let second_part = LinkedList {
    406                head: second_part_head,
    407                tail: second_part_tail,
    408                len: self.len - at,
    409                alloc: self.alloc.clone(),
    410                marker: PhantomData,
    411            };
    412
    413            // Fix the tail ptr of the first part
    414            self.tail = Some(split_node);
    415            self.len = at;
    416
    417            second_part
    418        } else {
    419            mem::replace(self, LinkedList::new_in(self.alloc.clone()))
    420        }
    421    }
    422}
    423
    424#[stable(feature = "rust1", since = "1.0.0")]
    425impl<T> Default for LinkedList<T> {
    426    /// Creates an empty `LinkedList<T>`.
    427    #[inline]
    428    fn default() -> Self {
    429        Self::new()
    430    }
    431}
    432
    433impl<T> LinkedList<T> {
    434    /// Creates an empty `LinkedList`.
    435    ///
    436    /// # Examples
    437    ///
    438    /// ```
    439    /// use std::collections::LinkedList;
    440    ///
    441    /// let list: LinkedList<u32> = LinkedList::new();
    442    /// ```
    443    #[inline]
    444    #[rustc_const_stable(feature = "const_linked_list_new", since = "1.39.0")]
    445    #[stable(feature = "rust1", since = "1.0.0")]
    446    #[must_use]
    447    pub const fn new() -> Self {
    448        LinkedList { head: None, tail: None, len: 0, alloc: Global, marker: PhantomData }
    449    }
    450
    451    /// Moves all elements from `other` to the end of the list.
    452    ///
    453    /// This reuses all the nodes from `other` and moves them into `self`. After
    454    /// this operation, `other` becomes empty.
    455    ///
    456    /// This operation should compute in *O*(1) time and *O*(1) memory.
    457    ///
    458    /// # Examples
    459    ///
    460    /// ```
    461    /// use std::collections::LinkedList;
    462    ///
    463    /// let mut list1 = LinkedList::new();
    464    /// list1.push_back('a');
    465    ///
    466    /// let mut list2 = LinkedList::new();
    467    /// list2.push_back('b');
    468    /// list2.push_back('c');
    469    ///
    470    /// list1.append(&mut list2);
    471    ///
    472    /// let mut iter = list1.iter();
    473    /// assert_eq!(iter.next(), Some(&'a'));
    474    /// assert_eq!(iter.next(), Some(&'b'));
    475    /// assert_eq!(iter.next(), Some(&'c'));
    476    /// assert!(iter.next().is_none());
    477    ///
    478    /// assert!(list2.is_empty());
    479    /// ```
    480    #[stable(feature = "rust1", since = "1.0.0")]
    481    pub fn append(&mut self, other: &mut Self) {
    482        match self.tail {
    483            None => mem::swap(self, other),
    484            Some(mut tail) => {
    485                // `as_mut` is okay here because we have exclusive access to the entirety
    486                // of both lists.
    487                if let Some(mut other_head) = other.head.take() {
    488                    unsafe {
    489                        tail.as_mut().next = Some(other_head);
    490                        other_head.as_mut().prev = Some(tail);
    491                    }
    492
    493                    self.tail = other.tail.take();
    494                    self.len += mem::replace(&mut other.len, 0);
    495                }
    496            }
    497        }
    498    }
    499}
    500
    501impl<T, A: Allocator> LinkedList<T, A> {
    502    /// Constructs an empty `LinkedList<T, A>`.
    503    ///
    504    /// # Examples
    505    ///
    506    /// ```
    507    /// #![feature(allocator_api)]
    508    ///
    509    /// use std::alloc::System;
    510    /// use std::collections::LinkedList;
    511    ///
    512    /// let list: LinkedList<u32, _> = LinkedList::new_in(System);
    513    /// ```
    514    #[inline]
    515    #[unstable(feature = "allocator_api", issue = "32838")]
    516    pub const fn new_in(alloc: A) -> Self {
    517        LinkedList { head: None, tail: None, len: 0, alloc, marker: PhantomData }
    518    }
    519    /// Provides a forward iterator.
    520    ///
    521    /// # Examples
    522    ///
    523    /// ```
    524    /// use std::collections::LinkedList;
    525    ///
    526    /// let mut list: LinkedList<u32> = LinkedList::new();
    527    ///
    528    /// list.push_back(0);
    529    /// list.push_back(1);
    530    /// list.push_back(2);
    531    ///
    532    /// let mut iter = list.iter();
    533    /// assert_eq!(iter.next(), Some(&0));
    534    /// assert_eq!(iter.next(), Some(&1));
    535    /// assert_eq!(iter.next(), Some(&2));
    536    /// assert_eq!(iter.next(), None);
    537    /// ```
    538    #[inline]
    539    #[stable(feature = "rust1", since = "1.0.0")]
    540    pub fn iter(&self) -> Iter<'_, T> {
    541        Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
    542    }
    543
    544    /// Provides a forward iterator with mutable references.
    545    ///
    546    /// # Examples
    547    ///
    548    /// ```
    549    /// use std::collections::LinkedList;
    550    ///
    551    /// let mut list: LinkedList<u32> = LinkedList::new();
    552    ///
    553    /// list.push_back(0);
    554    /// list.push_back(1);
    555    /// list.push_back(2);
    556    ///
    557    /// for element in list.iter_mut() {
    558    ///     *element += 10;
    559    /// }
    560    ///
    561    /// let mut iter = list.iter();
    562    /// assert_eq!(iter.next(), Some(&10));
    563    /// assert_eq!(iter.next(), Some(&11));
    564    /// assert_eq!(iter.next(), Some(&12));
    565    /// assert_eq!(iter.next(), None);
    566    /// ```
    567    #[inline]
    568    #[stable(feature = "rust1", since = "1.0.0")]
    569    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    570        IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
    571    }
    572
    573    /// Provides a cursor at the front element.
    574    ///
    575    /// The cursor is pointing to the "ghost" non-element if the list is empty.
    576    #[inline]
    577    #[must_use]
    578    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    579    pub fn cursor_front(&self) -> Cursor<'_, T, A> {
    580        Cursor { index: 0, current: self.head, list: self }
    581    }
    582
    583    /// Provides a cursor with editing operations at the front element.
    584    ///
    585    /// The cursor is pointing to the "ghost" non-element if the list is empty.
    586    #[inline]
    587    #[must_use]
    588    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    589    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A> {
    590        CursorMut { index: 0, current: self.head, list: self }
    591    }
    592
    593    /// Provides a cursor at the back element.
    594    ///
    595    /// The cursor is pointing to the "ghost" non-element if the list is empty.
    596    #[inline]
    597    #[must_use]
    598    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    599    pub fn cursor_back(&self) -> Cursor<'_, T, A> {
    600        Cursor { index: self.len.saturating_sub(1), current: self.tail, list: self }
    601    }
    602
    603    /// Provides a cursor with editing operations at the back element.
    604    ///
    605    /// The cursor is pointing to the "ghost" non-element if the list is empty.
    606    #[inline]
    607    #[must_use]
    608    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    609    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A> {
    610        CursorMut { index: self.len.saturating_sub(1), current: self.tail, list: self }
    611    }
    612
    613    /// Returns `true` if the `LinkedList` is empty.
    614    ///
    615    /// This operation should compute in *O*(1) time.
    616    ///
    617    /// # Examples
    618    ///
    619    /// ```
    620    /// use std::collections::LinkedList;
    621    ///
    622    /// let mut dl = LinkedList::new();
    623    /// assert!(dl.is_empty());
    624    ///
    625    /// dl.push_front("foo");
    626    /// assert!(!dl.is_empty());
    627    /// ```
    628    #[inline]
    629    #[must_use]
    630    #[stable(feature = "rust1", since = "1.0.0")]
    631    pub fn is_empty(&self) -> bool {
    632        self.head.is_none()
    633    }
    634
    635    /// Returns the length of the `LinkedList`.
    636    ///
    637    /// This operation should compute in *O*(1) time.
    638    ///
    639    /// # Examples
    640    ///
    641    /// ```
    642    /// use std::collections::LinkedList;
    643    ///
    644    /// let mut dl = LinkedList::new();
    645    ///
    646    /// dl.push_front(2);
    647    /// assert_eq!(dl.len(), 1);
    648    ///
    649    /// dl.push_front(1);
    650    /// assert_eq!(dl.len(), 2);
    651    ///
    652    /// dl.push_back(3);
    653    /// assert_eq!(dl.len(), 3);
    654    /// ```
    655    #[inline]
    656    #[must_use]
    657    #[stable(feature = "rust1", since = "1.0.0")]
    658    #[rustc_confusables("length", "size")]
    659    pub fn len(&self) -> usize {
    660        self.len
    661    }
    662
    663    /// Removes all elements from the `LinkedList`.
    664    ///
    665    /// This operation should compute in *O*(*n*) time.
    666    ///
    667    /// # Examples
    668    ///
    669    /// ```
    670    /// use std::collections::LinkedList;
    671    ///
    672    /// let mut dl = LinkedList::new();
    673    ///
    674    /// dl.push_front(2);
    675    /// dl.push_front(1);
    676    /// assert_eq!(dl.len(), 2);
    677    /// assert_eq!(dl.front(), Some(&1));
    678    ///
    679    /// dl.clear();
    680    /// assert_eq!(dl.len(), 0);
    681    /// assert_eq!(dl.front(), None);
    682    /// ```
    683    #[inline]
    684    #[stable(feature = "rust1", since = "1.0.0")]
    685    pub fn clear(&mut self) {
    686        // We need to drop the nodes while keeping self.alloc
    687        // We can do this by moving (head, tail, len) into a new list that borrows self.alloc
    688        drop(LinkedList {
    689            head: self.head.take(),
    690            tail: self.tail.take(),
    691            len: mem::take(&mut self.len),
    692            alloc: &self.alloc,
    693            marker: PhantomData,
    694        });
    695    }
    696
    697    /// Returns `true` if the `LinkedList` contains an element equal to the
    698    /// given value.
    699    ///
    700    /// This operation should compute linearly in *O*(*n*) time.
    701    ///
    702    /// # Examples
    703    ///
    704    /// ```
    705    /// use std::collections::LinkedList;
    706    ///
    707    /// let mut list: LinkedList<u32> = LinkedList::new();
    708    ///
    709    /// list.push_back(0);
    710    /// list.push_back(1);
    711    /// list.push_back(2);
    712    ///
    713    /// assert_eq!(list.contains(&0), true);
    714    /// assert_eq!(list.contains(&10), false);
    715    /// ```
    716    #[stable(feature = "linked_list_contains", since = "1.12.0")]
    717    pub fn contains(&self, x: &T) -> bool
    718    where
    719        T: PartialEq<T>,
    720    {
    721        self.iter().any(|e| e == x)
    722    }
    723
    724    /// Provides a reference to the front element, or `None` if the list is
    725    /// empty.
    726    ///
    727    /// This operation should compute in *O*(1) time.
    728    ///
    729    /// # Examples
    730    ///
    731    /// ```
    732    /// use std::collections::LinkedList;
    733    ///
    734    /// let mut dl = LinkedList::new();
    735    /// assert_eq!(dl.front(), None);
    736    ///
    737    /// dl.push_front(1);
    738    /// assert_eq!(dl.front(), Some(&1));
    739    /// ```
    740    #[inline]
    741    #[must_use]
    742    #[stable(feature = "rust1", since = "1.0.0")]
    743    #[rustc_confusables("first")]
    744    pub fn front(&self) -> Option<&T> {
    745        unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
    746    }
    747
    748    /// Provides a mutable reference to the front element, or `None` if the list
    749    /// is empty.
    750    ///
    751    /// This operation should compute in *O*(1) time.
    752    ///
    753    /// # Examples
    754    ///
    755    /// ```
    756    /// use std::collections::LinkedList;
    757    ///
    758    /// let mut dl = LinkedList::new();
    759    /// assert_eq!(dl.front(), None);
    760    ///
    761    /// dl.push_front(1);
    762    /// assert_eq!(dl.front(), Some(&1));
    763    ///
    764    /// match dl.front_mut() {
    765    ///     None => {},
    766    ///     Some(x) => *x = 5,
    767    /// }
    768    /// assert_eq!(dl.front(), Some(&5));
    769    /// ```
    770    #[inline]
    771    #[must_use]
    772    #[stable(feature = "rust1", since = "1.0.0")]
    773    pub fn front_mut(&mut self) -> Option<&mut T> {
    774        unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
    775    }
    776
    777    /// Provides a reference to the back element, or `None` if the list is
    778    /// empty.
    779    ///
    780    /// This operation should compute in *O*(1) time.
    781    ///
    782    /// # Examples
    783    ///
    784    /// ```
    785    /// use std::collections::LinkedList;
    786    ///
    787    /// let mut dl = LinkedList::new();
    788    /// assert_eq!(dl.back(), None);
    789    ///
    790    /// dl.push_back(1);
    791    /// assert_eq!(dl.back(), Some(&1));
    792    /// ```
    793    #[inline]
    794    #[must_use]
    795    #[stable(feature = "rust1", since = "1.0.0")]
    796    pub fn back(&self) -> Option<&T> {
    797        unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
    798    }
    799
    800    /// Provides a mutable reference to the back element, or `None` if the list
    801    /// is empty.
    802    ///
    803    /// This operation should compute in *O*(1) time.
    804    ///
    805    /// # Examples
    806    ///
    807    /// ```
    808    /// use std::collections::LinkedList;
    809    ///
    810    /// let mut dl = LinkedList::new();
    811    /// assert_eq!(dl.back(), None);
    812    ///
    813    /// dl.push_back(1);
    814    /// assert_eq!(dl.back(), Some(&1));
    815    ///
    816    /// match dl.back_mut() {
    817    ///     None => {},
    818    ///     Some(x) => *x = 5,
    819    /// }
    820    /// assert_eq!(dl.back(), Some(&5));
    821    /// ```
    822    #[inline]
    823    #[stable(feature = "rust1", since = "1.0.0")]
    824    pub fn back_mut(&mut self) -> Option<&mut T> {
    825        unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
    826    }
    827
    828    /// Adds an element to the front of the list.
    829    ///
    830    /// This operation should compute in *O*(1) time.
    831    ///
    832    /// # Examples
    833    ///
    834    /// ```
    835    /// use std::collections::LinkedList;
    836    ///
    837    /// let mut dl = LinkedList::new();
    838    ///
    839    /// dl.push_front(2);
    840    /// assert_eq!(dl.front().unwrap(), &2);
    841    ///
    842    /// dl.push_front(1);
    843    /// assert_eq!(dl.front().unwrap(), &1);
    844    /// ```
    845    #[stable(feature = "rust1", since = "1.0.0")]
    846    pub fn push_front(&mut self, elt: T) {
    847        let _ = self.push_front_mut(elt);
    848    }
    849
    850    /// Adds an element to the front of the list, returning a reference to it.
    851    ///
    852    /// This operation should compute in *O*(1) time.
    853    ///
    854    /// # Examples
    855    ///
    856    /// ```
    857    /// #![feature(push_mut)]
    858    /// use std::collections::LinkedList;
    859    ///
    860    /// let mut dl = LinkedList::from([1, 2, 3]);
    861    ///
    862    /// let ptr = dl.push_front_mut(2);
    863    /// *ptr += 4;
    864    /// assert_eq!(dl.front().unwrap(), &6);
    865    /// ```
    866    #[unstable(feature = "push_mut", issue = "135974")]
    867    #[must_use = "if you don't need a reference to the value, use `LinkedList::push_front` instead"]
    868    pub fn push_front_mut(&mut self, elt: T) -> &mut T {
    869        let mut node =
    870            Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
    871        // SAFETY: node is a unique pointer to a node in self.alloc
    872        unsafe {
    873            self.push_front_node(node);
    874            &mut node.as_mut().element
    875        }
    876    }
    877
    878    /// Removes the first element and returns it, or `None` if the list is
    879    /// empty.
    880    ///
    881    /// This operation should compute in *O*(1) time.
    882    ///
    883    /// # Examples
    884    ///
    885    /// ```
    886    /// use std::collections::LinkedList;
    887    ///
    888    /// let mut d = LinkedList::new();
    889    /// assert_eq!(d.pop_front(), None);
    890    ///
    891    /// d.push_front(1);
    892    /// d.push_front(3);
    893    /// assert_eq!(d.pop_front(), Some(3));
    894    /// assert_eq!(d.pop_front(), Some(1));
    895    /// assert_eq!(d.pop_front(), None);
    896    /// ```
    897    #[stable(feature = "rust1", since = "1.0.0")]
    898    pub fn pop_front(&mut self) -> Option<T> {
    899        self.pop_front_node().map(Node::into_element)
    900    }
    901
    902    /// Adds an element to the back of the list.
    903    ///
    904    /// This operation should compute in *O*(1) time.
    905    ///
    906    /// # Examples
    907    ///
    908    /// ```
    909    /// use std::collections::LinkedList;
    910    ///
    911    /// let mut d = LinkedList::new();
    912    /// d.push_back(1);
    913    /// d.push_back(3);
    914    /// assert_eq!(3, *d.back().unwrap());
    915    /// ```
    916    #[stable(feature = "rust1", since = "1.0.0")]
    917    #[rustc_confusables("push", "append")]
    918    pub fn push_back(&mut self, elt: T) {
    919        let _ = self.push_back_mut(elt);
    920    }
    921
    922    /// Adds an element to the back of the list, returning a reference to it.
    923    ///
    924    /// This operation should compute in *O*(1) time.
    925    ///
    926    /// # Examples
    927    ///
    928    /// ```
    929    /// #![feature(push_mut)]
    930    /// use std::collections::LinkedList;
    931    ///
    932    /// let mut dl = LinkedList::from([1, 2, 3]);
    933    ///
    934    /// let ptr = dl.push_back_mut(2);
    935    /// *ptr += 4;
    936    /// assert_eq!(dl.back().unwrap(), &6);
    937    /// ```
    938    #[unstable(feature = "push_mut", issue = "135974")]
    939    #[must_use = "if you don't need a reference to the value, use `LinkedList::push_back` instead"]
    940    pub fn push_back_mut(&mut self, elt: T) -> &mut T {
    941        let mut node =
    942            Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
    943        // SAFETY: node is a unique pointer to a node in self.alloc
    944        unsafe {
    945            self.push_back_node(node);
    946            &mut node.as_mut().element
    947        }
    948    }
    949
    950    /// Removes the last element from a list and returns it, or `None` if
    951    /// it is empty.
    952    ///
    953    /// This operation should compute in *O*(1) time.
    954    ///
    955    /// # Examples
    956    ///
    957    /// ```
    958    /// use std::collections::LinkedList;
    959    ///
    960    /// let mut d = LinkedList::new();
    961    /// assert_eq!(d.pop_back(), None);
    962    /// d.push_back(1);
    963    /// d.push_back(3);
    964    /// assert_eq!(d.pop_back(), Some(3));
    965    /// ```
    966    #[stable(feature = "rust1", since = "1.0.0")]
    967    pub fn pop_back(&mut self) -> Option<T> {
    968        self.pop_back_node().map(Node::into_element)
    969    }
    970
    971    /// Splits the list into two at the given index. Returns everything after the given index,
    972    /// including the index.
    973    ///
    974    /// This operation should compute in *O*(*n*) time.
    975    ///
    976    /// # Panics
    977    ///
    978    /// Panics if `at > len`.
    979    ///
    980    /// # Examples
    981    ///
    982    /// ```
    983    /// use std::collections::LinkedList;
    984    ///
    985    /// let mut d = LinkedList::new();
    986    ///
    987    /// d.push_front(1);
    988    /// d.push_front(2);
    989    /// d.push_front(3);
    990    ///
    991    /// let mut split = d.split_off(2);
    992    ///
    993    /// assert_eq!(split.pop_front(), Some(1));
    994    /// assert_eq!(split.pop_front(), None);
    995    /// ```
    996    #[stable(feature = "rust1", since = "1.0.0")]
    997    pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>
    998    where
    999        A: Clone,
    1000    {
    1001        let len = self.len();
    1002        assert!(at <= len, "Cannot split off at a nonexistent index");
    1003        if at == 0 {
    1004            return mem::replace(self, Self::new_in(self.alloc.clone()));
    1005        } else if at == len {
    1006            return Self::new_in(self.alloc.clone());
    1007        }
    1008
    1009        // Below, we iterate towards the `i-1`th node, either from the start or the end,
    1010        // depending on which would be faster.
    1011        let split_node = if at - 1 <= len - 1 - (at - 1) {
    1012            let mut iter = self.iter_mut();
    1013            // instead of skipping using .skip() (which creates a new struct),
    1014            // we skip manually so we can access the head field without
    1015            // depending on implementation details of Skip
    1016            for _ in 0..at - 1 {
    1017                iter.next();
    1018            }
    1019            iter.head
    1020        } else {
    1021            // better off starting from the end
    1022            let mut iter = self.iter_mut();
    1023            for _ in 0..len - 1 - (at - 1) {
    1024                iter.next_back();
    1025            }
    1026            iter.tail
    1027        };
    1028        unsafe { self.split_off_after_node(split_node, at) }
    1029    }
    1030
    1031    /// Removes the element at the given index and returns it.
    1032    ///
    1033    /// This operation should compute in *O*(*n*) time.
    1034    ///
    1035    /// # Panics
    1036    /// Panics if at >= len
    1037    ///
    1038    /// # Examples
    1039    ///
    1040    /// ```
    1041    /// #![feature(linked_list_remove)]
    1042    /// use std::collections::LinkedList;
    1043    ///
    1044    /// let mut d = LinkedList::new();
    1045    ///
    1046    /// d.push_front(1);
    1047    /// d.push_front(2);
    1048    /// d.push_front(3);
    1049    ///
    1050    /// assert_eq!(d.remove(1), 2);
    1051    /// assert_eq!(d.remove(0), 3);
    1052    /// assert_eq!(d.remove(0), 1);
    1053    /// ```
    1054    #[unstable(feature = "linked_list_remove", issue = "69210")]
    1055    #[rustc_confusables("delete", "take")]
    1056    pub fn remove(&mut self, at: usize) -> T {
    1057        let len = self.len();
    1058        assert!(at < len, "Cannot remove at an index outside of the list bounds");
    1059
    1060        // Below, we iterate towards the node at the given index, either from
    1061        // the start or the end, depending on which would be faster.
    1062        let offset_from_end = len - at - 1;
    1063        if at <= offset_from_end {
    1064            let mut cursor = self.cursor_front_mut();
    1065            for _ in 0..at {
    1066                cursor.move_next();
    1067            }
    1068            cursor.remove_current().unwrap()
    1069        } else {
    1070            let mut cursor = self.cursor_back_mut();
    1071            for _ in 0..offset_from_end {
    1072                cursor.move_prev();
    1073            }
    1074            cursor.remove_current().unwrap()
    1075        }
    1076    }
    1077
    1078    /// Retains only the elements specified by the predicate.
    1079    ///
    1080    /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
    1081    /// This method operates in place, visiting each element exactly once in the
    1082    /// original order, and preserves the order of the retained elements.
    1083    ///
    1084    /// # Examples
    1085    ///
    1086    /// ```
    1087    /// #![feature(linked_list_retain)]
    1088    /// use std::collections::LinkedList;
    1089    ///
    1090    /// let mut d = LinkedList::new();
    1091    ///
    1092    /// d.push_front(1);
    1093    /// d.push_front(2);
    1094    /// d.push_front(3);
    1095    ///
    1096    /// d.retain(|&mut x| x % 2 == 0);
    1097    ///
    1098    /// assert_eq!(d.pop_front(), Some(2));
    1099    /// assert_eq!(d.pop_front(), None);
    1100    /// ```
    1101    ///
    1102    /// Because the elements are visited exactly once in the original order,
    1103    /// external state may be used to decide which elements to keep.
    1104    ///
    1105    /// ```
    1106    /// #![feature(linked_list_retain)]
    1107    /// use std::collections::LinkedList;
    1108    ///
    1109    /// let mut d = LinkedList::new();
    1110    ///
    1111    /// d.push_front(1);
    1112    /// d.push_front(2);
    1113    /// d.push_front(3);
    1114    ///
    1115    /// let keep = [false, true, false];
    1116    /// let mut iter = keep.iter();
    1117    /// d.retain(|_| *iter.next().unwrap());
    1118    /// assert_eq!(d.pop_front(), Some(2));
    1119    /// assert_eq!(d.pop_front(), None);
    1120    /// ```
    1121    #[unstable(feature = "linked_list_retain", issue = "114135")]
    1122    pub fn retain<F>(&mut self, mut f: F)
    1123    where
    1124        F: FnMut(&mut T) -> bool,
    1125    {
    1126        let mut cursor = self.cursor_front_mut();
    1127        while let Some(node) = cursor.current() {
    1128            if !f(node) {
    1129                cursor.remove_current().unwrap();
    1130            } else {
    1131                cursor.move_next();
    1132            }
    1133        }
    1134    }
    1135
    1136    /// Creates an iterator which uses a closure to determine if an element should be removed.
    1137    ///
    1138    /// If the closure returns `true`, the element is removed from the list and
    1139    /// yielded. If the closure returns `false`, or panics, the element remains
    1140    /// in the list and will not be yielded.
    1141    ///
    1142    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
    1143    /// or the iteration short-circuits, then the remaining elements will be retained.
    1144    /// Use `extract_if().for_each(drop)` if you do not need the returned iterator.
    1145    ///
    1146    /// The iterator also lets you mutate the value of each element in the
    1147    /// closure, regardless of whether you choose to keep or remove it.
    1148    ///
    1149    /// # Examples
    1150    ///
    1151    /// Splitting a list into even and odd values, reusing the original list:
    1152    ///
    1153    /// ```
    1154    /// use std::collections::LinkedList;
    1155    ///
    1156    /// let mut numbers: LinkedList<u32> = LinkedList::new();
    1157    /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
    1158    ///
    1159    /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<LinkedList<_>>();
    1160    /// let odds = numbers;
    1161    ///
    1162    /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
    1163    /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
    1164    /// ```
    1165    #[stable(feature = "extract_if", since = "1.87.0")]
    1166    pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
    1167    where
    1168        F: FnMut(&mut T) -> bool,
    1169    {
    1170        // avoid borrow issues.
    1171        let it = self.head;
    1172        let old_len = self.len;
    1173
    1174        ExtractIf { list: self, it, pred: filter, idx: 0, old_len }
    1175    }
    1176}
    1177
    1178#[stable(feature = "rust1", since = "1.0.0")]
    1179unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> {
    1180    fn drop(&mut self) {
    1181        struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>);
    1182
    1183        impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
    1184            fn drop(&mut self) {
    1185                // Continue the same loop we do below. This only runs when a destructor has
    1186                // panicked. If another one panics this will abort.
    1187                while self.0.pop_front_node().is_some() {}
    1188            }
    1189        }
    1190
    1191        // Wrap self so that if a destructor panics, we can try to keep looping
    1192        let guard = DropGuard(self);
    1193        while guard.0.pop_front_node().is_some() {}
    1194        mem::forget(guard);
    1195    }
    1196}
    1197
    1198#[stable(feature = "rust1", since = "1.0.0")]
    1199impl<'a, T> Iterator for Iter<'a, T> {
    1200    type Item = &'a T;
    1201
    1202    #[inline]
    1203    fn next(&mut self) -> Option<&'a T> {
    1204        if self.len == 0 {
    1205            None
    1206        } else {
    1207            self.head.map(|node| unsafe {
    1208                // Need an unbound lifetime to get 'a
    1209                let node = &*node.as_ptr();
    1210                self.len -= 1;
    1211                self.head = node.next;
    1212                &node.element
    1213            })
    1214        }
    1215    }
    1216
    1217    #[inline]
    1218    fn size_hint(&self) -> (usize, Option<usize>) {
    1219        (self.len, Some(self.len))
    1220    }
    1221
    1222    #[inline]
    1223    fn last(mut self) -> Option<&'a T> {
    1224        self.next_back()
    1225    }
    1226}
    1227
    1228#[stable(feature = "rust1", since = "1.0.0")]
    1229impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    1230    #[inline]
    1231    fn next_back(&mut self) -> Option<&'a T> {
    1232        if self.len == 0 {
    1233            None
    1234        } else {
    1235            self.tail.map(|node| unsafe {
    1236                // Need an unbound lifetime to get 'a
    1237                let node = &*node.as_ptr();
    1238                self.len -= 1;
    1239                self.tail = node.prev;
    1240                &node.element
    1241            })
    1242        }
    1243    }
    1244}
    1245
    1246#[stable(feature = "rust1", since = "1.0.0")]
    1247impl<T> ExactSizeIterator for Iter<'_, T> {}
    1248
    1249#[stable(feature = "fused", since = "1.26.0")]
    1250impl<T> FusedIterator for Iter<'_, T> {}
    1251
    1252#[stable(feature = "default_iters", since = "1.70.0")]
    1253impl<T> Default for Iter<'_, T> {
    1254    /// Creates an empty `linked_list::Iter`.
    1255    ///
    1256    /// ```
    1257    /// # use std::collections::linked_list;
    1258    /// let iter: linked_list::Iter<'_, u8> = Default::default();
    1259    /// assert_eq!(iter.len(), 0);
    1260    /// ```
    1261    fn default() -> Self {
    1262        Iter { head: None, tail: None, len: 0, marker: Default::default() }
    1263    }
    1264}
    1265
    1266#[stable(feature = "rust1", since = "1.0.0")]
    1267impl<'a, T> Iterator for IterMut<'a, T> {
    1268    type Item = &'a mut T;
    1269
    1270    #[inline]
    1271    fn next(&mut self) -> Option<&'a mut T> {
    1272        if self.len == 0 {
    1273            None
    1274        } else {
    1275            self.head.map(|node| unsafe {
    1276                // Need an unbound lifetime to get 'a
    1277                let node = &mut *node.as_ptr();
    1278                self.len -= 1;
    1279                self.head = node.next;
    1280                &mut node.element
    1281            })
    1282        }
    1283    }
    1284
    1285    #[inline]
    1286    fn size_hint(&self) -> (usize, Option<usize>) {
    1287        (self.len, Some(self.len))
    1288    }
    1289
    1290    #[inline]
    1291    fn last(mut self) -> Option<&'a mut T> {
    1292        self.next_back()
    1293    }
    1294}
    1295
    1296#[stable(feature = "rust1", since = "1.0.0")]
    1297impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    1298    #[inline]
    1299    fn next_back(&mut self) -> Option<&'a mut T> {
    1300        if self.len == 0 {
    1301            None
    1302        } else {
    1303            self.tail.map(|node| unsafe {
    1304                // Need an unbound lifetime to get 'a
    1305                let node = &mut *node.as_ptr();
    1306                self.len -= 1;
    1307                self.tail = node.prev;
    1308                &mut node.element
    1309            })
    1310        }
    1311    }
    1312}
    1313
    1314#[stable(feature = "rust1", since = "1.0.0")]
    1315impl<T> ExactSizeIterator for IterMut<'_, T> {}
    1316
    1317#[stable(feature = "fused", since = "1.26.0")]
    1318impl<T> FusedIterator for IterMut<'_, T> {}
    1319
    1320#[stable(feature = "default_iters", since = "1.70.0")]
    1321impl<T> Default for IterMut<'_, T> {
    1322    fn default() -> Self {
    1323        IterMut { head: None, tail: None, len: 0, marker: Default::default() }
    1324    }
    1325}
    1326
    1327/// A cursor over a `LinkedList`.
    1328///
    1329/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
    1330///
    1331/// Cursors always rest between two elements in the list, and index in a logically circular way.
    1332/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
    1333/// tail of the list.
    1334///
    1335/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
    1336#[unstable(feature = "linked_list_cursors", issue = "58533")]
    1337pub struct Cursor<
    1338    'a,
    1339    T: 'a,
    1340    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    1341> {
    1342    index: usize,
    1343    current: Option<NonNull<Node<T>>>,
    1344    list: &'a LinkedList<T, A>,
    1345}
    1346
    1347#[unstable(feature = "linked_list_cursors", issue = "58533")]
    1348impl<T, A: Allocator> Clone for Cursor<'_, T, A> {
    1349    fn clone(&self) -> Self {
    1350        let Cursor { index, current, list } = *self;
    1351        Cursor { index, current, list }
    1352    }
    1353}
    1354
    1355#[unstable(feature = "linked_list_cursors", issue = "58533")]
    1356impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> {
    1357    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1358        f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
    1359    }
    1360}
    1361
    1362/// A cursor over a `LinkedList` with editing operations.
    1363///
    1364/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
    1365/// safely mutate the list during iteration. This is because the lifetime of its yielded
    1366/// references is tied to its own lifetime, instead of just the underlying list. This means
    1367/// cursors cannot yield multiple elements at once.
    1368///
    1369/// Cursors always rest between two elements in the list, and index in a logically circular way.
    1370/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
    1371/// tail of the list.
    1372#[unstable(feature = "linked_list_cursors", issue = "58533")]
    1373pub struct CursorMut<
    1374    'a,
    1375    T: 'a,
    1376    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    1377> {
    1378    index: usize,
    1379    current: Option<NonNull<Node<T>>>,
    1380    list: &'a mut LinkedList<T, A>,
    1381}
    1382
    1383#[unstable(feature = "linked_list_cursors", issue = "58533")]
    1384impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> {
    1385    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1386        f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
    1387    }
    1388}
    1389
    1390impl<'a, T, A: Allocator> Cursor<'a, T, A> {
    1391    /// Returns the cursor position index within the `LinkedList`.
    1392    ///
    1393    /// This returns `None` if the cursor is currently pointing to the
    1394    /// "ghost" non-element.
    1395    #[must_use]
    1396    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1397    pub fn index(&self) -> Option<usize> {
    1398        let _ = self.current?;
    1399        Some(self.index)
    1400    }
    1401
    1402    /// Moves the cursor to the next element of the `LinkedList`.
    1403    ///
    1404    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    1405    /// the first element of the `LinkedList`. If it is pointing to the last
    1406    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
    1407    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1408    pub fn move_next(&mut self) {
    1409        match self.current.take() {
    1410            // We had no current element; the cursor was sitting at the start position
    1411            // Next element should be the head of the list
    1412            None => {
    1413                self.current = self.list.head;
    1414                self.index = 0;
    1415            }
    1416            // We had a previous element, so let's go to its next
    1417            Some(current) => unsafe {
    1418                self.current = current.as_ref().next;
    1419                self.index += 1;
    1420            },
    1421        }
    1422    }
    1423
    1424    /// Moves the cursor to the previous element of the `LinkedList`.
    1425    ///
    1426    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    1427    /// the last element of the `LinkedList`. If it is pointing to the first
    1428    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
    1429    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1430    pub fn move_prev(&mut self) {
    1431        match self.current.take() {
    1432            // No current. We're at the start of the list. Yield None and jump to the end.
    1433            None => {
    1434                self.current = self.list.tail;
    1435                self.index = self.list.len().saturating_sub(1);
    1436            }
    1437            // Have a prev. Yield it and go to the previous element.
    1438            Some(current) => unsafe {
    1439                self.current = current.as_ref().prev;
    1440                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
    1441            },
    1442        }
    1443    }
    1444
    1445    /// Returns a reference to the element that the cursor is currently
    1446    /// pointing to.
    1447    ///
    1448    /// This returns `None` if the cursor is currently pointing to the
    1449    /// "ghost" non-element.
    1450    #[must_use]
    1451    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1452    pub fn current(&self) -> Option<&'a T> {
    1453        unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
    1454    }
    1455
    1456    /// Returns a reference to the next element.
    1457    ///
    1458    /// If the cursor is pointing to the "ghost" non-element then this returns
    1459    /// the first element of the `LinkedList`. If it is pointing to the last
    1460    /// element of the `LinkedList` then this returns `None`.
    1461    #[must_use]
    1462    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1463    pub fn peek_next(&self) -> Option<&'a T> {
    1464        unsafe {
    1465            let next = match self.current {
    1466                None => self.list.head,
    1467                Some(current) => current.as_ref().next,
    1468            };
    1469            next.map(|next| &(*next.as_ptr()).element)
    1470        }
    1471    }
    1472
    1473    /// Returns a reference to the previous element.
    1474    ///
    1475    /// If the cursor is pointing to the "ghost" non-element then this returns
    1476    /// the last element of the `LinkedList`. If it is pointing to the first
    1477    /// element of the `LinkedList` then this returns `None`.
    1478    #[must_use]
    1479    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1480    pub fn peek_prev(&self) -> Option<&'a T> {
    1481        unsafe {
    1482            let prev = match self.current {
    1483                None => self.list.tail,
    1484                Some(current) => current.as_ref().prev,
    1485            };
    1486            prev.map(|prev| &(*prev.as_ptr()).element)
    1487        }
    1488    }
    1489
    1490    /// Provides a reference to the front element of the cursor's parent list,
    1491    /// or None if the list is empty.
    1492    #[must_use]
    1493    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1494    #[rustc_confusables("first")]
    1495    pub fn front(&self) -> Option<&'a T> {
    1496        self.list.front()
    1497    }
    1498
    1499    /// Provides a reference to the back element of the cursor's parent list,
    1500    /// or None if the list is empty.
    1501    #[must_use]
    1502    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1503    #[rustc_confusables("last")]
    1504    pub fn back(&self) -> Option<&'a T> {
    1505        self.list.back()
    1506    }
    1507
    1508    /// Provides a reference to the cursor's parent list.
    1509    #[must_use]
    1510    #[inline(always)]
    1511    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1512    pub fn as_list(&self) -> &'a LinkedList<T, A> {
    1513        self.list
    1514    }
    1515}
    1516
    1517impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
    1518    /// Returns the cursor position index within the `LinkedList`.
    1519    ///
    1520    /// This returns `None` if the cursor is currently pointing to the
    1521    /// "ghost" non-element.
    1522    #[must_use]
    1523    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1524    pub fn index(&self) -> Option<usize> {
    1525        let _ = self.current?;
    1526        Some(self.index)
    1527    }
    1528
    1529    /// Moves the cursor to the next element of the `LinkedList`.
    1530    ///
    1531    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    1532    /// the first element of the `LinkedList`. If it is pointing to the last
    1533    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
    1534    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1535    pub fn move_next(&mut self) {
    1536        match self.current.take() {
    1537            // We had no current element; the cursor was sitting at the start position
    1538            // Next element should be the head of the list
    1539            None => {
    1540                self.current = self.list.head;
    1541                self.index = 0;
    1542            }
    1543            // We had a previous element, so let's go to its next
    1544            Some(current) => unsafe {
    1545                self.current = current.as_ref().next;
    1546                self.index += 1;
    1547            },
    1548        }
    1549    }
    1550
    1551    /// Moves the cursor to the previous element of the `LinkedList`.
    1552    ///
    1553    /// If the cursor is pointing to the "ghost" non-element then this will move it to
    1554    /// the last element of the `LinkedList`. If it is pointing to the first
    1555    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
    1556    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1557    pub fn move_prev(&mut self) {
    1558        match self.current.take() {
    1559            // No current. We're at the start of the list. Yield None and jump to the end.
    1560            None => {
    1561                self.current = self.list.tail;
    1562                self.index = self.list.len().saturating_sub(1);
    1563            }
    1564            // Have a prev. Yield it and go to the previous element.
    1565            Some(current) => unsafe {
    1566                self.current = current.as_ref().prev;
    1567                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
    1568            },
    1569        }
    1570    }
    1571
    1572    /// Returns a reference to the element that the cursor is currently
    1573    /// pointing to.
    1574    ///
    1575    /// This returns `None` if the cursor is currently pointing to the
    1576    /// "ghost" non-element.
    1577    #[must_use]
    1578    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1579    pub fn current(&mut self) -> Option<&mut T> {
    1580        unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
    1581    }
    1582
    1583    /// Returns a reference to the next element.
    1584    ///
    1585    /// If the cursor is pointing to the "ghost" non-element then this returns
    1586    /// the first element of the `LinkedList`. If it is pointing to the last
    1587    /// element of the `LinkedList` then this returns `None`.
    1588    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1589    pub fn peek_next(&mut self) -> Option<&mut T> {
    1590        unsafe {
    1591            let next = match self.current {
    1592                None => self.list.head,
    1593                Some(current) => current.as_ref().next,
    1594            };
    1595            next.map(|next| &mut (*next.as_ptr()).element)
    1596        }
    1597    }
    1598
    1599    /// Returns a reference to the previous element.
    1600    ///
    1601    /// If the cursor is pointing to the "ghost" non-element then this returns
    1602    /// the last element of the `LinkedList`. If it is pointing to the first
    1603    /// element of the `LinkedList` then this returns `None`.
    1604    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1605    pub fn peek_prev(&mut self) -> Option<&mut T> {
    1606        unsafe {
    1607            let prev = match self.current {
    1608                None => self.list.tail,
    1609                Some(current) => current.as_ref().prev,
    1610            };
    1611            prev.map(|prev| &mut (*prev.as_ptr()).element)
    1612        }
    1613    }
    1614
    1615    /// Returns a read-only cursor pointing to the current element.
    1616    ///
    1617    /// The lifetime of the returned `Cursor` is bound to that of the
    1618    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
    1619    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
    1620    #[must_use]
    1621    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1622    pub fn as_cursor(&self) -> Cursor<'_, T, A> {
    1623        Cursor { list: self.list, current: self.current, index: self.index }
    1624    }
    1625
    1626    /// Provides a read-only reference to the cursor's parent list.
    1627    ///
    1628    /// The lifetime of the returned reference is bound to that of the
    1629    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
    1630    /// `CursorMut` is frozen for the lifetime of the reference.
    1631    #[must_use]
    1632    #[inline(always)]
    1633    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1634    pub fn as_list(&self) -> &LinkedList<T, A> {
    1635        self.list
    1636    }
    1637}
    1638
    1639// Now the list editing operations
    1640
    1641impl<'a, T> CursorMut<'a, T> {
    1642    /// Inserts the elements from the given `LinkedList` after the current one.
    1643    ///
    1644    /// If the cursor is pointing at the "ghost" non-element then the new elements are
    1645    /// inserted at the start of the `LinkedList`.
    1646    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1647    pub fn splice_after(&mut self, list: LinkedList<T>) {
    1648        unsafe {
    1649            let Some((splice_head, splice_tail, splice_len)) = list.detach_all_nodes() else {
    1650                return;
    1651            };
    1652            let node_next = match self.current {
    1653                None => self.list.head,
    1654                Some(node) => node.as_ref().next,
    1655            };
    1656            self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
    1657            if self.current.is_none() {
    1658                // The "ghost" non-element's index has changed.
    1659                self.index = self.list.len;
    1660            }
    1661        }
    1662    }
    1663
    1664    /// Inserts the elements from the given `LinkedList` before the current one.
    1665    ///
    1666    /// If the cursor is pointing at the "ghost" non-element then the new elements are
    1667    /// inserted at the end of the `LinkedList`.
    1668    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1669    pub fn splice_before(&mut self, list: LinkedList<T>) {
    1670        unsafe {
    1671            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
    1672                Some(parts) => parts,
    1673                _ => return,
    1674            };
    1675            let node_prev = match self.current {
    1676                None => self.list.tail,
    1677                Some(node) => node.as_ref().prev,
    1678            };
    1679            self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
    1680            self.index += splice_len;
    1681        }
    1682    }
    1683}
    1684
    1685impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
    1686    /// Inserts a new element into the `LinkedList` after the current one.
    1687    ///
    1688    /// If the cursor is pointing at the "ghost" non-element then the new element is
    1689    /// inserted at the front of the `LinkedList`.
    1690    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1691    pub fn insert_after(&mut self, item: T) {
    1692        unsafe {
    1693            let spliced_node =
    1694                Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
    1695            let node_next = match self.current {
    1696                None => self.list.head,
    1697                Some(node) => node.as_ref().next,
    1698            };
    1699            self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
    1700            if self.current.is_none() {
    1701                // The "ghost" non-element's index has changed.
    1702                self.index = self.list.len;
    1703            }
    1704        }
    1705    }
    1706
    1707    /// Inserts a new element into the `LinkedList` before the current one.
    1708    ///
    1709    /// If the cursor is pointing at the "ghost" non-element then the new element is
    1710    /// inserted at the end of the `LinkedList`.
    1711    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1712    pub fn insert_before(&mut self, item: T) {
    1713        unsafe {
    1714            let spliced_node =
    1715                Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
    1716            let node_prev = match self.current {
    1717                None => self.list.tail,
    1718                Some(node) => node.as_ref().prev,
    1719            };
    1720            self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
    1721            self.index += 1;
    1722        }
    1723    }
    1724
    1725    /// Removes the current element from the `LinkedList`.
    1726    ///
    1727    /// The element that was removed is returned, and the cursor is
    1728    /// moved to point to the next element in the `LinkedList`.
    1729    ///
    1730    /// If the cursor is currently pointing to the "ghost" non-element then no element
    1731    /// is removed and `None` is returned.
    1732    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1733    pub fn remove_current(&mut self) -> Option<T> {
    1734        let unlinked_node = self.current?;
    1735        unsafe {
    1736            self.current = unlinked_node.as_ref().next;
    1737            self.list.unlink_node(unlinked_node);
    1738            let unlinked_node = Box::from_raw_in(unlinked_node.as_ptr(), &self.list.alloc);
    1739            Some(unlinked_node.element)
    1740        }
    1741    }
    1742
    1743    /// Removes the current element from the `LinkedList` without deallocating the list node.
    1744    ///
    1745    /// The node that was removed is returned as a new `LinkedList` containing only this node.
    1746    /// The cursor is moved to point to the next element in the current `LinkedList`.
    1747    ///
    1748    /// If the cursor is currently pointing to the "ghost" non-element then no element
    1749    /// is removed and `None` is returned.
    1750    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1751    pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>>
    1752    where
    1753        A: Clone,
    1754    {
    1755        let mut unlinked_node = self.current?;
    1756        unsafe {
    1757            self.current = unlinked_node.as_ref().next;
    1758            self.list.unlink_node(unlinked_node);
    1759
    1760            unlinked_node.as_mut().prev = None;
    1761            unlinked_node.as_mut().next = None;
    1762            Some(LinkedList {
    1763                head: Some(unlinked_node),
    1764                tail: Some(unlinked_node),
    1765                len: 1,
    1766                alloc: self.list.alloc.clone(),
    1767                marker: PhantomData,
    1768            })
    1769        }
    1770    }
    1771
    1772    /// Splits the list into two after the current element. This will return a
    1773    /// new list consisting of everything after the cursor, with the original
    1774    /// list retaining everything before.
    1775    ///
    1776    /// If the cursor is pointing at the "ghost" non-element then the entire contents
    1777    /// of the `LinkedList` are moved.
    1778    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1779    pub fn split_after(&mut self) -> LinkedList<T, A>
    1780    where
    1781        A: Clone,
    1782    {
    1783        let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
    1784        if self.index == self.list.len {
    1785            // The "ghost" non-element's index has changed to 0.
    1786            self.index = 0;
    1787        }
    1788        unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
    1789    }
    1790
    1791    /// Splits the list into two before the current element. This will return a
    1792    /// new list consisting of everything before the cursor, with the original
    1793    /// list retaining everything after.
    1794    ///
    1795    /// If the cursor is pointing at the "ghost" non-element then the entire contents
    1796    /// of the `LinkedList` are moved.
    1797    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1798    pub fn split_before(&mut self) -> LinkedList<T, A>
    1799    where
    1800        A: Clone,
    1801    {
    1802        let split_off_idx = self.index;
    1803        self.index = 0;
    1804        unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
    1805    }
    1806
    1807    /// Appends an element to the front of the cursor's parent list. The node
    1808    /// that the cursor points to is unchanged, even if it is the "ghost" node.
    1809    ///
    1810    /// This operation should compute in *O*(1) time.
    1811    // `push_front` continues to point to "ghost" when it adds a node to mimic
    1812    // the behavior of `insert_before` on an empty list.
    1813    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1814    pub fn push_front(&mut self, elt: T) {
    1815        // Safety: We know that `push_front` does not change the position in
    1816        // memory of other nodes. This ensures that `self.current` remains
    1817        // valid.
    1818        self.list.push_front(elt);
    1819        self.index += 1;
    1820    }
    1821
    1822    /// Appends an element to the back of the cursor's parent list. The node
    1823    /// that the cursor points to is unchanged, even if it is the "ghost" node.
    1824    ///
    1825    /// This operation should compute in *O*(1) time.
    1826    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1827    #[rustc_confusables("push", "append")]
    1828    pub fn push_back(&mut self, elt: T) {
    1829        // Safety: We know that `push_back` does not change the position in
    1830        // memory of other nodes. This ensures that `self.current` remains
    1831        // valid.
    1832        self.list.push_back(elt);
    1833        if self.current().is_none() {
    1834            // The index of "ghost" is the length of the list, so we just need
    1835            // to increment self.index to reflect the new length of the list.
    1836            self.index += 1;
    1837        }
    1838    }
    1839
    1840    /// Removes the first element from the cursor's parent list and returns it,
    1841    /// or None if the list is empty. The element the cursor points to remains
    1842    /// unchanged, unless it was pointing to the front element. In that case, it
    1843    /// points to the new front element.
    1844    ///
    1845    /// This operation should compute in *O*(1) time.
    1846    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1847    pub fn pop_front(&mut self) -> Option<T> {
    1848        // We can't check if current is empty, we must check the list directly.
    1849        // It is possible for `self.current == None` and the list to be
    1850        // non-empty.
    1851        if self.list.is_empty() {
    1852            None
    1853        } else {
    1854            // We can't point to the node that we pop. Copying the behavior of
    1855            // `remove_current`, we move on to the next node in the sequence.
    1856            // If the list is of length 1 then we end pointing to the "ghost"
    1857            // node at index 0, which is expected.
    1858            if self.list.head == self.current {
    1859                self.move_next();
    1860            }
    1861            // An element was removed before (or at) our current position, so
    1862            // the index must be decremented. `saturating_sub` handles the
    1863            // ghost node case where index could be 0.
    1864            self.index = self.index.saturating_sub(1);
    1865            self.list.pop_front()
    1866        }
    1867    }
    1868
    1869    /// Removes the last element from the cursor's parent list and returns it,
    1870    /// or None if the list is empty. The element the cursor points to remains
    1871    /// unchanged, unless it was pointing to the back element. In that case, it
    1872    /// points to the "ghost" element.
    1873    ///
    1874    /// This operation should compute in *O*(1) time.
    1875    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1876    #[rustc_confusables("pop")]
    1877    pub fn pop_back(&mut self) -> Option<T> {
    1878        if self.list.is_empty() {
    1879            None
    1880        } else {
    1881            if self.list.tail == self.current {
    1882                // The index now reflects the length of the list. It was the
    1883                // length of the list minus 1, but now the list is 1 smaller. No
    1884                // change is needed for `index`.
    1885                self.current = None;
    1886            } else if self.current.is_none() {
    1887                self.index = self.list.len - 1;
    1888            }
    1889            self.list.pop_back()
    1890        }
    1891    }
    1892
    1893    /// Provides a reference to the front element of the cursor's parent list,
    1894    /// or None if the list is empty.
    1895    #[must_use]
    1896    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1897    #[rustc_confusables("first")]
    1898    pub fn front(&self) -> Option<&T> {
    1899        self.list.front()
    1900    }
    1901
    1902    /// Provides a mutable reference to the front element of the cursor's
    1903    /// parent list, or None if the list is empty.
    1904    #[must_use]
    1905    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1906    pub fn front_mut(&mut self) -> Option<&mut T> {
    1907        self.list.front_mut()
    1908    }
    1909
    1910    /// Provides a reference to the back element of the cursor's parent list,
    1911    /// or None if the list is empty.
    1912    #[must_use]
    1913    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1914    #[rustc_confusables("last")]
    1915    pub fn back(&self) -> Option<&T> {
    1916        self.list.back()
    1917    }
    1918
    1919    /// Provides a mutable reference to back element of the cursor's parent
    1920    /// list, or `None` if the list is empty.
    1921    ///
    1922    /// # Examples
    1923    /// Building and mutating a list with a cursor, then getting the back element:
    1924    /// ```
    1925    /// #![feature(linked_list_cursors)]
    1926    /// use std::collections::LinkedList;
    1927    /// let mut dl = LinkedList::new();
    1928    /// dl.push_front(3);
    1929    /// dl.push_front(2);
    1930    /// dl.push_front(1);
    1931    /// let mut cursor = dl.cursor_front_mut();
    1932    /// *cursor.current().unwrap() = 99;
    1933    /// *cursor.back_mut().unwrap() = 0;
    1934    /// let mut contents = dl.into_iter();
    1935    /// assert_eq!(contents.next(), Some(99));
    1936    /// assert_eq!(contents.next(), Some(2));
    1937    /// assert_eq!(contents.next(), Some(0));
    1938    /// assert_eq!(contents.next(), None);
    1939    /// ```
    1940    #[must_use]
    1941    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    1942    pub fn back_mut(&mut self) -> Option<&mut T> {
    1943        self.list.back_mut()
    1944    }
    1945}
    1946
    1947/// An iterator produced by calling `extract_if` on LinkedList.
    1948#[stable(feature = "extract_if", since = "1.87.0")]
    1949#[must_use = "iterators are lazy and do nothing unless consumed; \
    1950    use `extract_if().for_each(drop)` to remove and discard elements"]
    1951pub struct ExtractIf<
    1952    'a,
    1953    T: 'a,
    1954    F: 'a,
    1955    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    1956> {
    1957    list: &'a mut LinkedList<T, A>,
    1958    it: Option<NonNull<Node<T>>>,
    1959    pred: F,
    1960    idx: usize,
    1961    old_len: usize,
    1962}
    1963
    1964#[stable(feature = "extract_if", since = "1.87.0")]
    1965impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
    1966where
    1967    F: FnMut(&mut T) -> bool,
    1968{
    1969    type Item = T;
    1970
    1971    fn next(&mut self) -> Option<T> {
    1972        while let Some(mut node) = self.it {
    1973            unsafe {
    1974                self.it = node.as_ref().next;
    1975                self.idx += 1;
    1976
    1977                if (self.pred)(&mut node.as_mut().element) {
    1978                    // `unlink_node` is okay with aliasing `element` references.
    1979                    self.list.unlink_node(node);
    1980                    return Some(Box::from_raw_in(node.as_ptr(), &self.list.alloc).element);
    1981                }
    1982            }
    1983        }
    1984
    1985        None
    1986    }
    1987
    1988    fn size_hint(&self) -> (usize, Option<usize>) {
    1989        (0, Some(self.old_len - self.idx))
    1990    }
    1991}
    1992
    1993#[stable(feature = "extract_if", since = "1.87.0")]
    1994impl<T, F, A> fmt::Debug for ExtractIf<'_, T, F, A>
    1995where
    1996    T: fmt::Debug,
    1997    A: Allocator,
    1998{
    1999    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    2000        let peek = self.it.map(|node| unsafe { &node.as_ref().element });
    2001        f.debug_struct("ExtractIf").field("peek", &peek).finish_non_exhaustive()
    2002    }
    2003}
    2004
    2005#[stable(feature = "rust1", since = "1.0.0")]
    2006impl<T, A: Allocator> Iterator for IntoIter<T, A> {
    2007    type Item = T;
    2008
    2009    #[inline]
    2010    fn next(&mut self) -> Option<T> {
    2011        self.list.pop_front()
    2012    }
    2013
    2014    #[inline]
    2015    fn size_hint(&self) -> (usize, Option<usize>) {
    2016        (self.list.len, Some(self.list.len))
    2017    }
    2018}
    2019
    2020#[stable(feature = "rust1", since = "1.0.0")]
    2021impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
    2022    #[inline]
    2023    fn next_back(&mut self) -> Option<T> {
    2024        self.list.pop_back()
    2025    }
    2026}
    2027
    2028#[stable(feature = "rust1", since = "1.0.0")]
    2029impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {}
    2030
    2031#[stable(feature = "fused", since = "1.26.0")]
    2032impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
    2033
    2034#[stable(feature = "default_iters", since = "1.70.0")]
    2035impl<T> Default for IntoIter<T> {
    2036    /// Creates an empty `linked_list::IntoIter`.
    2037    ///
    2038    /// ```
    2039    /// # use std::collections::linked_list;
    2040    /// let iter: linked_list::IntoIter<u8> = Default::default();
    2041    /// assert_eq!(iter.len(), 0);
    2042    /// ```
    2043    fn default() -> Self {
    2044        LinkedList::new().into_iter()
    2045    }
    2046}
    2047
    2048#[stable(feature = "rust1", since = "1.0.0")]
    2049impl<T> FromIterator<T> for LinkedList<T> {
    2050    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
    2051        let mut list = Self::new();
    2052        list.extend(iter);
    2053        list
    2054    }
    2055}
    2056
    2057#[stable(feature = "rust1", since = "1.0.0")]
    2058impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
    2059    type Item = T;
    2060    type IntoIter = IntoIter<T, A>;
    2061
    2062    /// Consumes the list into an iterator yielding elements by value.
    2063    #[inline]
    2064    fn into_iter(self) -> IntoIter<T, A> {
    2065        IntoIter { list: self }
    2066    }
    2067}
    2068
    2069#[stable(feature = "rust1", since = "1.0.0")]
    2070impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
    2071    type Item = &'a T;
    2072    type IntoIter = Iter<'a, T>;
    2073
    2074    fn into_iter(self) -> Iter<'a, T> {
    2075        self.iter()
    2076    }
    2077}
    2078
    2079#[stable(feature = "rust1", since = "1.0.0")]
    2080impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
    2081    type Item = &'a mut T;
    2082    type IntoIter = IterMut<'a, T>;
    2083
    2084    fn into_iter(self) -> IterMut<'a, T> {
    2085        self.iter_mut()
    2086    }
    2087}
    2088
    2089#[stable(feature = "rust1", since = "1.0.0")]
    2090impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
    2091    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    2092        <Self as SpecExtend<I>>::spec_extend(self, iter);
    2093    }
    2094
    2095    #[inline]
    2096    fn extend_one(&mut self, elem: T) {
    2097        self.push_back(elem);
    2098    }
    2099}
    2100
    2101impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> {
    2102    default fn spec_extend(&mut self, iter: I) {
    2103        iter.into_iter().for_each(move |elt| self.push_back(elt));
    2104    }
    2105}
    2106
    2107impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
    2108    fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
    2109        self.append(other);
    2110    }
    2111}
    2112
    2113#[stable(feature = "extend_ref", since = "1.2.0")]
    2114impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> {
    2115    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
    2116        self.extend(iter.into_iter().cloned());
    2117    }
    2118
    2119    #[inline]
    2120    fn extend_one(&mut self, &elem: &'a T) {
    2121        self.push_back(elem);
    2122    }
    2123}
    2124
    2125#[stable(feature = "rust1", since = "1.0.0")]
    2126impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> {
    2127    fn eq(&self, other: &Self) -> bool {
    2128        self.len() == other.len() && self.iter().eq(other)
    2129    }
    2130
    2131    fn ne(&self, other: &Self) -> bool {
    2132        self.len() != other.len() || self.iter().ne(other)
    2133    }
    2134}
    2135
    2136#[stable(feature = "rust1", since = "1.0.0")]
    2137impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}
    2138
    2139#[stable(feature = "rust1", since = "1.0.0")]
    2140impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> {
    2141    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    2142        self.iter().partial_cmp(other)
    2143    }
    2144}
    2145
    2146#[stable(feature = "rust1", since = "1.0.0")]
    2147impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
    2148    #[inline]
    2149    fn cmp(&self, other: &Self) -> Ordering {
    2150        self.iter().cmp(other)
    2151    }
    2152}
    2153
    2154#[stable(feature = "rust1", since = "1.0.0")]
    2155impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
    2156    fn clone(&self) -> Self {
    2157        let mut list = Self::new_in(self.alloc.clone());
    2158        list.extend(self.iter().cloned());
    2159        list
    2160    }
    2161
    2162    /// Overwrites the contents of `self` with a clone of the contents of `source`.
    2163    ///
    2164    /// This method is preferred over simply assigning `source.clone()` to `self`,
    2165    /// as it avoids reallocation of the nodes of the linked list. Additionally,
    2166    /// if the element type `T` overrides `clone_from()`, this will reuse the
    2167    /// resources of `self`'s elements as well.
    2168    fn clone_from(&mut self, source: &Self) {
    2169        let mut source_iter = source.iter();
    2170        if self.len() > source.len() {
    2171            self.split_off(source.len());
    2172        }
    2173        for (elem, source_elem) in self.iter_mut().zip(&mut source_iter) {
    2174            elem.clone_from(source_elem);
    2175        }
    2176        if !source_iter.is_empty() {
    2177            self.extend(source_iter.cloned());
    2178        }
    2179    }
    2180}
    2181
    2182#[stable(feature = "rust1", since = "1.0.0")]
    2183impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> {
    2184    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    2185        f.debug_list().entries(self).finish()
    2186    }
    2187}
    2188
    2189#[stable(feature = "rust1", since = "1.0.0")]
    2190impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
    2191    fn hash<H: Hasher>(&self, state: &mut H) {
    2192        state.write_length_prefix(self.len());
    2193        for elt in self {
    2194            elt.hash(state);
    2195        }
    2196    }
    2197}
    2198
    2199#[stable(feature = "std_collections_from_array", since = "1.56.0")]
    2200impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
    2201    /// Converts a `[T; N]` into a `LinkedList<T>`.
    2202    ///
    2203    /// ```
    2204    /// use std::collections::LinkedList;
    2205    ///
    2206    /// let list1 = LinkedList::from([1, 2, 3, 4]);
    2207    /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
    2208    /// assert_eq!(list1, list2);
    2209    /// ```
    2210    fn from(arr: [T; N]) -> Self {
    2211        Self::from_iter(arr)
    2212    }
    2213}
    2214
    2215// Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
    2216#[allow(dead_code)]
    2217fn assert_covariance() {
    2218    fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
    2219        x
    2220    }
    2221    fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
    2222        x
    2223    }
    2224    fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
    2225        x
    2226    }
    2227}
    2228
    2229#[stable(feature = "rust1", since = "1.0.0")]
    2230unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {}
    2231
    2232#[stable(feature = "rust1", since = "1.0.0")]
    2233unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {}
    2234
    2235#[stable(feature = "rust1", since = "1.0.0")]
    2236unsafe impl<T: Sync> Send for Iter<'_, T> {}
    2237
    2238#[stable(feature = "rust1", since = "1.0.0")]
    2239unsafe impl<T: Sync> Sync for Iter<'_, T> {}
    2240
    2241#[stable(feature = "rust1", since = "1.0.0")]
    2242unsafe impl<T: Send> Send for IterMut<'_, T> {}
    2243
    2244#[stable(feature = "rust1", since = "1.0.0")]
    2245unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
    2246
    2247#[unstable(feature = "linked_list_cursors", issue = "58533")]
    2248unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {}
    2249
    2250#[unstable(feature = "linked_list_cursors", issue = "58533")]
    2251unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {}
    2252
    2253#[unstable(feature = "linked_list_cursors", issue = "58533")]
    2254unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {}
    2255
    2256#[unstable(feature = "linked_list_cursors", issue = "58533")]
    2257unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {}