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