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