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