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