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