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