Skip to main content

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