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 split = d.split_off(2);
 845     ///
 846     /// assert_eq!(split.pop_front(), Some(1));
 847     /// assert_eq!(split.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     /// Removes the element at the given index and returns it.
 882     ///
 883     /// This operation should compute in O(n) time.
 884     ///
 885     /// # Panics
 886     /// Panics if at >= len
 887     ///
 888     /// # Examples
 889     ///
 890     /// ```
 891     /// #![feature(linked_list_remove)]
 892     /// use std::collections::LinkedList;
 893     ///
 894     /// let mut d = LinkedList::new();
 895     ///
 896     /// d.push_front(1);
 897     /// d.push_front(2);
 898     /// d.push_front(3);
 899     ///
 900     /// assert_eq!(d.remove(1), 2);
 901     /// assert_eq!(d.remove(0), 3);
 902     /// assert_eq!(d.remove(0), 1);
 903     /// ```
 904     #[unstable(feature = "linked_list_remove", issue = "69210")]
 905     pub fn remove(&mut self, at: usize) -> T {
 906         let len = self.len();
 907         assert!(at < len, "Cannot remove at an index outside of the list bounds");
 908
 909         // Below, we iterate towards the node at the given index, either from
 910         // the start or the end, depending on which would be faster.
 911         let offset_from_end = len - at - 1;
 912         if at <= offset_from_end {
 913             let mut cursor = self.cursor_front_mut();
 914             for _ in 0..at {
 915                 cursor.move_next();
 916             }
 917             cursor.remove_current().unwrap()
 918         } else {
 919             let mut cursor = self.cursor_back_mut();
 920             for _ in 0..offset_from_end {
 921                 cursor.move_prev();
 922             }
 923             cursor.remove_current().unwrap()
 924         }
 925     }
 926
 927     /// Creates an iterator which uses a closure to determine if an element should be removed.
 928     ///
 929     /// If the closure returns true, then the element is removed and yielded.
 930     /// If the closure returns false, the element will remain in the list and will not be yielded
 931     /// by the iterator.
 932     ///
 933     /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of
 934     /// whether you choose to keep or remove it.
 935     ///
 936     /// # Examples
 937     ///
 938     /// Splitting a list into evens and odds, reusing the original list:
 939     ///
 940     /// ```
 941     /// #![feature(drain_filter)]
 942     /// use std::collections::LinkedList;
 943     ///
 944     /// let mut numbers: LinkedList<u32> = LinkedList::new();
 945     /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
 946     ///
 947     /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
 948     /// let odds = numbers;
 949     ///
 950     /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
 951     /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
 952     /// ```
 953     #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 954     pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
 955     where
 956         F: FnMut(&mut T) -> bool,
 957     {
 958         // avoid borrow issues.
 959         let it = self.head;
 960         let old_len = self.len;
 961
 962         DrainFilter { list: self, it, pred: filter, idx: 0, old_len }
 963     }
 964 }
 965
 966 #[stable(feature = "rust1", since = "1.0.0")]
 967 unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
 968     fn drop(&mut self) {
 969         struct DropGuard<'a, T>(&'a mut LinkedList<T>);
 970
 971         impl<'a, T> Drop for DropGuard<'a, T> {
 972             fn drop(&mut self) {
 973                 // Continue the same loop we do below. This only runs when a destructor has
 974                 // panicked. If another one panics this will abort.
 975                 while let Some(_) = self.0.pop_front_node() {}
 976             }
 977         }
 978
 979         while let Some(node) = self.pop_front_node() {
 980             let guard = DropGuard(self);
 981             drop(node);
 982             mem::forget(guard);
 983         }
 984     }
 985 }
 986
 987 #[stable(feature = "rust1", since = "1.0.0")]
 988 impl<'a, T> Iterator for Iter<'a, T> {
 989     type Item = &'a T;
 990
 991     #[inline]
 992     fn next(&mut self) -> Option<&'a T> {
 993         if self.len == 0 {
 994             None
 995         } else {
 996             self.head.map(|node| unsafe {
 997                 // Need an unbound lifetime to get 'a
 998                 let node = &*node.as_ptr();
 999                 self.len -= 1;
1000                 self.head = node.next;
1001                 &node.element
1002             })
1003         }
1004     }
1005
1006     #[inline]
1007     fn size_hint(&self) -> (usize, Option<usize>) {
1008         (self.len, Some(self.len))
1009     }
1010
1011     #[inline]
1012     fn last(mut self) -> Option<&'a T> {
1013         self.next_back()
1014     }
1015 }
1016
1017 #[stable(feature = "rust1", since = "1.0.0")]
1018 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1019     #[inline]
1020     fn next_back(&mut self) -> Option<&'a T> {
1021         if self.len == 0 {
1022             None
1023         } else {
1024             self.tail.map(|node| unsafe {
1025                 // Need an unbound lifetime to get 'a
1026                 let node = &*node.as_ptr();
1027                 self.len -= 1;
1028                 self.tail = node.prev;
1029                 &node.element
1030             })
1031         }
1032     }
1033 }
1034
1035 #[stable(feature = "rust1", since = "1.0.0")]
1036 impl<T> ExactSizeIterator for Iter<'_, T> {}
1037
1038 #[stable(feature = "fused", since = "1.26.0")]
1039 impl<T> FusedIterator for Iter<'_, T> {}
1040
1041 #[stable(feature = "rust1", since = "1.0.0")]
1042 impl<'a, T> Iterator for IterMut<'a, T> {
1043     type Item = &'a mut T;
1044
1045     #[inline]
1046     fn next(&mut self) -> Option<&'a mut T> {
1047         if self.len == 0 {
1048             None
1049         } else {
1050             self.head.map(|node| unsafe {
1051                 // Need an unbound lifetime to get 'a
1052                 let node = &mut *node.as_ptr();
1053                 self.len -= 1;
1054                 self.head = node.next;
1055                 &mut node.element
1056             })
1057         }
1058     }
1059
1060     #[inline]
1061     fn size_hint(&self) -> (usize, Option<usize>) {
1062         (self.len, Some(self.len))
1063     }
1064
1065     #[inline]
1066     fn last(mut self) -> Option<&'a mut T> {
1067         self.next_back()
1068     }
1069 }
1070
1071 #[stable(feature = "rust1", since = "1.0.0")]
1072 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1073     #[inline]
1074     fn next_back(&mut self) -> Option<&'a mut T> {
1075         if self.len == 0 {
1076             None
1077         } else {
1078             self.tail.map(|node| unsafe {
1079                 // Need an unbound lifetime to get 'a
1080                 let node = &mut *node.as_ptr();
1081                 self.len -= 1;
1082                 self.tail = node.prev;
1083                 &mut node.element
1084             })
1085         }
1086     }
1087 }
1088
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 impl<T> ExactSizeIterator for IterMut<'_, T> {}
1091
1092 #[stable(feature = "fused", since = "1.26.0")]
1093 impl<T> FusedIterator for IterMut<'_, T> {}
1094
1095 impl<T> IterMut<'_, T> {
1096     /// Inserts the given element just after the element most recently returned by `.next()`.
1097     /// The inserted element does not appear in the iteration.
1098     ///
1099     /// # Examples
1100     ///
1101     /// ```
1102     /// #![feature(linked_list_extras)]
1103     ///
1104     /// use std::collections::LinkedList;
1105     ///
1106     /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
1107     ///
1108     /// {
1109     ///     let mut it = list.iter_mut();
1110     ///     assert_eq!(it.next().unwrap(), &1);
1111     ///     // insert `2` after `1`
1112     ///     it.insert_next(2);
1113     /// }
1114     /// {
1115     ///     let vec: Vec<_> = list.into_iter().collect();
1116     ///     assert_eq!(vec, [1, 2, 3, 4]);
1117     /// }
1118     /// ```
1119     #[inline]
1120     #[unstable(
1121         feature = "linked_list_extras",
1122         reason = "this is probably better handled by a cursor type -- we'll see",
1123         issue = "27794"
1124     )]
1125     pub fn insert_next(&mut self, element: T) {
1126         match self.head {
1127             // `push_back` is okay with aliasing `element` references
1128             None => self.list.push_back(element),
1129             Some(head) => unsafe {
1130                 let prev = match head.as_ref().prev {
1131                     // `push_front` is okay with aliasing nodes
1132                     None => return self.list.push_front(element),
1133                     Some(prev) => prev,
1134                 };
1135
1136                 let node = Some(Box::into_raw_non_null(box Node {
1137                     next: Some(head),
1138                     prev: Some(prev),
1139                     element,
1140                 }));
1141
1142                 // Not creating references to entire nodes to not invalidate the
1143                 // reference to `element` we handed to the user.
1144                 (*prev.as_ptr()).next = node;
1145                 (*head.as_ptr()).prev = node;
1146
1147                 self.list.len += 1;
1148             },
1149         }
1150     }
1151
1152     /// Provides a reference to the next element, without changing the iterator.
1153     ///
1154     /// # Examples
1155     ///
1156     /// ```
1157     /// #![feature(linked_list_extras)]
1158     ///
1159     /// use std::collections::LinkedList;
1160     ///
1161     /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
1162     ///
1163     /// let mut it = list.iter_mut();
1164     /// assert_eq!(it.next().unwrap(), &1);
1165     /// assert_eq!(it.peek_next().unwrap(), &2);
1166     /// // We just peeked at 2, so it was not consumed from the iterator.
1167     /// assert_eq!(it.next().unwrap(), &2);
1168     /// ```
1169     #[inline]
1170     #[unstable(
1171         feature = "linked_list_extras",
1172         reason = "this is probably better handled by a cursor type -- we'll see",
1173         issue = "27794"
1174     )]
1175     pub fn peek_next(&mut self) -> Option<&mut T> {
1176         if self.len == 0 {
1177             None
1178         } else {
1179             unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
1180         }
1181     }
1182 }
1183
1184 /// A cursor over a `LinkedList`.
1185 ///
1186 /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
1187 ///
1188 /// Cursors always rest between two elements in the list, and index in a logically circular way.
1189 /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1190 /// tail of the list.
1191 ///
1192 /// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
1193 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1194 pub struct Cursor<'a, T: 'a> {
1195     index: usize,
1196     current: Option<NonNull<Node<T>>>,
1197     list: &'a LinkedList<T>,
1198 }
1199
1200 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1201 impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> {
1202     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1203         f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
1204     }
1205 }
1206
1207 /// A cursor over a `LinkedList` with editing operations.
1208 ///
1209 /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
1210 /// safely mutate the list during iteration. This is because the lifetime of its yielded
1211 /// references is tied to its own lifetime, instead of just the underlying list. This means
1212 /// cursors cannot yield multiple elements at once.
1213 ///
1214 /// Cursors always rest between two elements in the list, and index in a logically circular way.
1215 /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1216 /// tail of the list.
1217 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1218 pub struct CursorMut<'a, T: 'a> {
1219     index: usize,
1220     current: Option<NonNull<Node<T>>>,
1221     list: &'a mut LinkedList<T>,
1222 }
1223
1224 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1225 impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> {
1226     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1227         f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
1228     }
1229 }
1230
1231 impl<'a, T> Cursor<'a, T> {
1232     /// Returns the cursor position index within the `LinkedList`.
1233     ///
1234     /// This returns `None` if the cursor is currently pointing to the
1235     /// "ghost" non-element.
1236     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1237     pub fn index(&self) -> Option<usize> {
1238         let _ = self.current?;
1239         Some(self.index)
1240     }
1241
1242     /// Moves the cursor to the next element of the `LinkedList`.
1243     ///
1244     /// If the cursor is pointing to the "ghost" non-element then this will move it to
1245     /// the first element of the `LinkedList`. If it is pointing to the last
1246     /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1247     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1248     pub fn move_next(&mut self) {
1249         match self.current.take() {
1250             // We had no current element; the cursor was sitting at the start position
1251             // Next element should be the head of the list
1252             None => {
1253                 self.current = self.list.head;
1254                 self.index = 0;
1255             }
1256             // We had a previous element, so let's go to its next
1257             Some(current) => unsafe {
1258                 self.current = current.as_ref().next;
1259                 self.index += 1;
1260             },
1261         }
1262     }
1263
1264     /// Moves the cursor to the previous element of the `LinkedList`.
1265     ///
1266     /// If the cursor is pointing to the "ghost" non-element then this will move it to
1267     /// the last element of the `LinkedList`. If it is pointing to the first
1268     /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1269     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1270     pub fn move_prev(&mut self) {
1271         match self.current.take() {
1272             // No current. We're at the start of the list. Yield None and jump to the end.
1273             None => {
1274                 self.current = self.list.tail;
1275                 self.index = self.list.len().checked_sub(1).unwrap_or(0);
1276             }
1277             // Have a prev. Yield it and go to the previous element.
1278             Some(current) => unsafe {
1279                 self.current = current.as_ref().prev;
1280                 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1281             },
1282         }
1283     }
1284
1285     /// Returns a reference to the element that the cursor is currently
1286     /// pointing to.
1287     ///
1288     /// This returns `None` if the cursor is currently pointing to the
1289     /// "ghost" non-element.
1290     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1291     pub fn current(&self) -> Option<&'a T> {
1292         unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
1293     }
1294
1295     /// Returns a reference to the next element.
1296     ///
1297     /// If the cursor is pointing to the "ghost" non-element then this returns
1298     /// the first element of the `LinkedList`. If it is pointing to the last
1299     /// element of the `LinkedList` then this returns `None`.
1300     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1301     pub fn peek_next(&self) -> Option<&'a T> {
1302         unsafe {
1303             let next = match self.current {
1304                 None => self.list.head,
1305                 Some(current) => current.as_ref().next,
1306             };
1307             next.map(|next| &(*next.as_ptr()).element)
1308         }
1309     }
1310
1311     /// Returns a reference to the previous element.
1312     ///
1313     /// If the cursor is pointing to the "ghost" non-element then this returns
1314     /// the last element of the `LinkedList`. If it is pointing to the first
1315     /// element of the `LinkedList` then this returns `None`.
1316     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1317     pub fn peek_prev(&self) -> Option<&'a T> {
1318         unsafe {
1319             let prev = match self.current {
1320                 None => self.list.tail,
1321                 Some(current) => current.as_ref().prev,
1322             };
1323             prev.map(|prev| &(*prev.as_ptr()).element)
1324         }
1325     }
1326 }
1327
1328 impl<'a, T> CursorMut<'a, T> {
1329     /// Returns the cursor position index within the `LinkedList`.
1330     ///
1331     /// This returns `None` if the cursor is currently pointing to the
1332     /// "ghost" non-element.
1333     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1334     pub fn index(&self) -> Option<usize> {
1335         let _ = self.current?;
1336         Some(self.index)
1337     }
1338
1339     /// Moves the cursor to the next element of the `LinkedList`.
1340     ///
1341     /// If the cursor is pointing to the "ghost" non-element then this will move it to
1342     /// the first element of the `LinkedList`. If it is pointing to the last
1343     /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1344     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1345     pub fn move_next(&mut self) {
1346         match self.current.take() {
1347             // We had no current element; the cursor was sitting at the start position
1348             // Next element should be the head of the list
1349             None => {
1350                 self.current = self.list.head;
1351                 self.index = 0;
1352             }
1353             // We had a previous element, so let's go to its next
1354             Some(current) => unsafe {
1355                 self.current = current.as_ref().next;
1356                 self.index += 1;
1357             },
1358         }
1359     }
1360
1361     /// Moves the cursor to the previous element of the `LinkedList`.
1362     ///
1363     /// If the cursor is pointing to the "ghost" non-element then this will move it to
1364     /// the last element of the `LinkedList`. If it is pointing to the first
1365     /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1366     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1367     pub fn move_prev(&mut self) {
1368         match self.current.take() {
1369             // No current. We're at the start of the list. Yield None and jump to the end.
1370             None => {
1371                 self.current = self.list.tail;
1372                 self.index = self.list.len().checked_sub(1).unwrap_or(0);
1373             }
1374             // Have a prev. Yield it and go to the previous element.
1375             Some(current) => unsafe {
1376                 self.current = current.as_ref().prev;
1377                 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1378             },
1379         }
1380     }
1381
1382     /// Returns a reference to the element that the cursor is currently
1383     /// pointing to.
1384     ///
1385     /// This returns `None` if the cursor is currently pointing to the
1386     /// "ghost" non-element.
1387     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1388     pub fn current(&mut self) -> Option<&mut T> {
1389         unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
1390     }
1391
1392     /// Returns a reference to the next element.
1393     ///
1394     /// If the cursor is pointing to the "ghost" non-element then this returns
1395     /// the first element of the `LinkedList`. If it is pointing to the last
1396     /// element of the `LinkedList` then this returns `None`.
1397     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1398     pub fn peek_next(&mut self) -> Option<&mut T> {
1399         unsafe {
1400             let next = match self.current {
1401                 None => self.list.head,
1402                 Some(current) => current.as_ref().next,
1403             };
1404             next.map(|next| &mut (*next.as_ptr()).element)
1405         }
1406     }
1407
1408     /// Returns a reference to the previous element.
1409     ///
1410     /// If the cursor is pointing to the "ghost" non-element then this returns
1411     /// the last element of the `LinkedList`. If it is pointing to the first
1412     /// element of the `LinkedList` then this returns `None`.
1413     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1414     pub fn peek_prev(&mut self) -> Option<&mut T> {
1415         unsafe {
1416             let prev = match self.current {
1417                 None => self.list.tail,
1418                 Some(current) => current.as_ref().prev,
1419             };
1420             prev.map(|prev| &mut (*prev.as_ptr()).element)
1421         }
1422     }
1423
1424     /// Returns a read-only cursor pointing to the current element.
1425     ///
1426     /// The lifetime of the returned `Cursor` is bound to that of the
1427     /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1428     /// `CursorMut` is frozen for the lifetime of the `Cursor`.
1429     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1430     pub fn as_cursor(&self) -> Cursor<'_, T> {
1431         Cursor { list: self.list, current: self.current, index: self.index }
1432     }
1433 }
1434
1435 // Now the list editing operations
1436
1437 impl<'a, T> CursorMut<'a, T> {
1438     /// Inserts a new element into the `LinkedList` after the current one.
1439     ///
1440     /// If the cursor is pointing at the "ghost" non-element then the new element is
1441     /// inserted at the front of the `LinkedList`.
1442     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1443     pub fn insert_after(&mut self, item: T) {
1444         unsafe {
1445             let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
1446             let node_next = match self.current {
1447                 None => self.list.head,
1448                 Some(node) => node.as_ref().next,
1449             };
1450             self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
1451             if self.current.is_none() {
1452                 // The "ghost" non-element's index has changed.
1453                 self.index = self.list.len;
1454             }
1455         }
1456     }
1457
1458     /// Inserts a new element into the `LinkedList` before the current one.
1459     ///
1460     /// If the cursor is pointing at the "ghost" non-element then the new element is
1461     /// inserted at the end of the `LinkedList`.
1462     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1463     pub fn insert_before(&mut self, item: T) {
1464         unsafe {
1465             let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
1466             let node_prev = match self.current {
1467                 None => self.list.tail,
1468                 Some(node) => node.as_ref().prev,
1469             };
1470             self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
1471             self.index += 1;
1472         }
1473     }
1474
1475     /// Removes the current element from the `LinkedList`.
1476     ///
1477     /// The element that was removed is returned, and the cursor is
1478     /// moved to point to the next element in the `LinkedList`.
1479     ///
1480     /// If the cursor is currently pointing to the "ghost" non-element then no element
1481     /// is removed and `None` is returned.
1482     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1483     pub fn remove_current(&mut self) -> Option<T> {
1484         let unlinked_node = self.current?;
1485         unsafe {
1486             self.current = unlinked_node.as_ref().next;
1487             self.list.unlink_node(unlinked_node);
1488             let unlinked_node = Box::from_raw(unlinked_node.as_ptr());
1489             Some(unlinked_node.element)
1490         }
1491     }
1492
1493     /// Inserts the elements from the given `LinkedList` after the current one.
1494     ///
1495     /// If the cursor is pointing at the "ghost" non-element then the new elements are
1496     /// inserted at the start of the `LinkedList`.
1497     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1498     pub fn splice_after(&mut self, list: LinkedList<T>) {
1499         unsafe {
1500             let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1501                 Some(parts) => parts,
1502                 _ => return,
1503             };
1504             let node_next = match self.current {
1505                 None => self.list.head,
1506                 Some(node) => node.as_ref().next,
1507             };
1508             self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
1509             if self.current.is_none() {
1510                 // The "ghost" non-element's index has changed.
1511                 self.index = self.list.len;
1512             }
1513         }
1514     }
1515
1516     /// Inserts the elements from the given `LinkedList` before the current one.
1517     ///
1518     /// If the cursor is pointing at the "ghost" non-element then the new elements are
1519     /// inserted at the end of the `LinkedList`.
1520     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1521     pub fn splice_before(&mut self, list: LinkedList<T>) {
1522         unsafe {
1523             let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1524                 Some(parts) => parts,
1525                 _ => return,
1526             };
1527             let node_prev = match self.current {
1528                 None => self.list.tail,
1529                 Some(node) => node.as_ref().prev,
1530             };
1531             self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
1532             self.index += splice_len;
1533         }
1534     }
1535
1536     /// Splits the list into two after the current element. This will return a
1537     /// new list consisting of everything after the cursor, with the original
1538     /// list retaining everything before.
1539     ///
1540     /// If the cursor is pointing at the "ghost" non-element then the entire contents
1541     /// of the `LinkedList` are moved.
1542     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1543     pub fn split_after(&mut self) -> LinkedList<T> {
1544         let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
1545         if self.index == self.list.len {
1546             // The "ghost" non-element's index has changed to 0.
1547             self.index = 0;
1548         }
1549         unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
1550     }
1551
1552     /// Splits the list into two before the current element. This will return a
1553     /// new list consisting of everything before the cursor, with the original
1554     /// list retaining everything after.
1555     ///
1556     /// If the cursor is pointing at the "ghost" non-element then the entire contents
1557     /// of the `LinkedList` are moved.
1558     #[unstable(feature = "linked_list_cursors", issue = "58533")]
1559     pub fn split_before(&mut self) -> LinkedList<T> {
1560         let split_off_idx = self.index;
1561         self.index = 0;
1562         unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
1563     }
1564 }
1565
1566 /// An iterator produced by calling `drain_filter` on LinkedList.
1567 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1568 pub struct DrainFilter<'a, T: 'a, F: 'a>
1569 where
1570     F: FnMut(&mut T) -> bool,
1571 {
1572     list: &'a mut LinkedList<T>,
1573     it: Option<NonNull<Node<T>>>,
1574     pred: F,
1575     idx: usize,
1576     old_len: usize,
1577 }
1578
1579 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1580 impl<T, F> Iterator for DrainFilter<'_, T, F>
1581 where
1582     F: FnMut(&mut T) -> bool,
1583 {
1584     type Item = T;
1585
1586     fn next(&mut self) -> Option<T> {
1587         while let Some(mut node) = self.it {
1588             unsafe {
1589                 self.it = node.as_ref().next;
1590                 self.idx += 1;
1591
1592                 if (self.pred)(&mut node.as_mut().element) {
1593                     // `unlink_node` is okay with aliasing `element` references.
1594                     self.list.unlink_node(node);
1595                     return Some(Box::from_raw(node.as_ptr()).element);
1596                 }
1597             }
1598         }
1599
1600         None
1601     }
1602
1603     fn size_hint(&self) -> (usize, Option<usize>) {
1604         (0, Some(self.old_len - self.idx))
1605     }
1606 }
1607
1608 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1609 impl<T, F> Drop for DrainFilter<'_, T, F>
1610 where
1611     F: FnMut(&mut T) -> bool,
1612 {
1613     fn drop(&mut self) {
1614         struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>)
1615         where
1616             F: FnMut(&mut T) -> bool;
1617
1618         impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F>
1619         where
1620             F: FnMut(&mut T) -> bool,
1621         {
1622             fn drop(&mut self) {
1623                 self.0.for_each(drop);
1624             }
1625         }
1626
1627         while let Some(item) = self.next() {
1628             let guard = DropGuard(self);
1629             drop(item);
1630             mem::forget(guard);
1631         }
1632     }
1633 }
1634
1635 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1636 impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
1637 where
1638     F: FnMut(&mut T) -> bool,
1639 {
1640     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1641         f.debug_tuple("DrainFilter").field(&self.list).finish()
1642     }
1643 }
1644
1645 #[stable(feature = "rust1", since = "1.0.0")]
1646 impl<T> Iterator for IntoIter<T> {
1647     type Item = T;
1648
1649     #[inline]
1650     fn next(&mut self) -> Option<T> {
1651         self.list.pop_front()
1652     }
1653
1654     #[inline]
1655     fn size_hint(&self) -> (usize, Option<usize>) {
1656         (self.list.len, Some(self.list.len))
1657     }
1658 }
1659
1660 #[stable(feature = "rust1", since = "1.0.0")]
1661 impl<T> DoubleEndedIterator for IntoIter<T> {
1662     #[inline]
1663     fn next_back(&mut self) -> Option<T> {
1664         self.list.pop_back()
1665     }
1666 }
1667
1668 #[stable(feature = "rust1", since = "1.0.0")]
1669 impl<T> ExactSizeIterator for IntoIter<T> {}
1670
1671 #[stable(feature = "fused", since = "1.26.0")]
1672 impl<T> FusedIterator for IntoIter<T> {}
1673
1674 #[stable(feature = "rust1", since = "1.0.0")]
1675 impl<T> FromIterator<T> for LinkedList<T> {
1676     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1677         let mut list = Self::new();
1678         list.extend(iter);
1679         list
1680     }
1681 }
1682
1683 #[stable(feature = "rust1", since = "1.0.0")]
1684 impl<T> IntoIterator for LinkedList<T> {
1685     type Item = T;
1686     type IntoIter = IntoIter<T>;
1687
1688     /// Consumes the list into an iterator yielding elements by value.
1689     #[inline]
1690     fn into_iter(self) -> IntoIter<T> {
1691         IntoIter { list: self }
1692     }
1693 }
1694
1695 #[stable(feature = "rust1", since = "1.0.0")]
1696 impl<'a, T> IntoIterator for &'a LinkedList<T> {
1697     type Item = &'a T;
1698     type IntoIter = Iter<'a, T>;
1699
1700     fn into_iter(self) -> Iter<'a, T> {
1701         self.iter()
1702     }
1703 }
1704
1705 #[stable(feature = "rust1", since = "1.0.0")]
1706 impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
1707     type Item = &'a mut T;
1708     type IntoIter = IterMut<'a, T>;
1709
1710     fn into_iter(self) -> IterMut<'a, T> {
1711         self.iter_mut()
1712     }
1713 }
1714
1715 #[stable(feature = "rust1", since = "1.0.0")]
1716 impl<T> Extend<T> for LinkedList<T> {
1717     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1718         <Self as SpecExtend<I>>::spec_extend(self, iter);
1719     }
1720 }
1721
1722 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
1723     default fn spec_extend(&mut self, iter: I) {
1724         iter.into_iter().for_each(move |elt| self.push_back(elt));
1725     }
1726 }
1727
1728 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
1729     fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
1730         self.append(other);
1731     }
1732 }
1733
1734 #[stable(feature = "extend_ref", since = "1.2.0")]
1735 impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
1736     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1737         self.extend(iter.into_iter().cloned());
1738     }
1739 }
1740
1741 #[stable(feature = "rust1", since = "1.0.0")]
1742 impl<T: PartialEq> PartialEq for LinkedList<T> {
1743     fn eq(&self, other: &Self) -> bool {
1744         self.len() == other.len() && self.iter().eq(other)
1745     }
1746
1747     fn ne(&self, other: &Self) -> bool {
1748         self.len() != other.len() || self.iter().ne(other)
1749     }
1750 }
1751
1752 #[stable(feature = "rust1", since = "1.0.0")]
1753 impl<T: Eq> Eq for LinkedList<T> {}
1754
1755 #[stable(feature = "rust1", since = "1.0.0")]
1756 impl<T: PartialOrd> PartialOrd for LinkedList<T> {
1757     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1758         self.iter().partial_cmp(other)
1759     }
1760 }
1761
1762 #[stable(feature = "rust1", since = "1.0.0")]
1763 impl<T: Ord> Ord for LinkedList<T> {
1764     #[inline]
1765     fn cmp(&self, other: &Self) -> Ordering {
1766         self.iter().cmp(other)
1767     }
1768 }
1769
1770 #[stable(feature = "rust1", since = "1.0.0")]
1771 impl<T: Clone> Clone for LinkedList<T> {
1772     fn clone(&self) -> Self {
1773         self.iter().cloned().collect()
1774     }
1775
1776     fn clone_from(&mut self, other: &Self) {
1777         let mut iter_other = other.iter();
1778         if self.len() > other.len() {
1779             self.split_off(other.len());
1780         }
1781         for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
1782             elem.clone_from(elem_other);
1783         }
1784         if !iter_other.is_empty() {
1785             self.extend(iter_other.cloned());
1786         }
1787     }
1788 }
1789
1790 #[stable(feature = "rust1", since = "1.0.0")]
1791 impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
1792     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1793         f.debug_list().entries(self).finish()
1794     }
1795 }
1796
1797 #[stable(feature = "rust1", since = "1.0.0")]
1798 impl<T: Hash> Hash for LinkedList<T> {
1799     fn hash<H: Hasher>(&self, state: &mut H) {
1800         self.len().hash(state);
1801         for elt in self {
1802             elt.hash(state);
1803         }
1804     }
1805 }
1806
1807 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1808 #[allow(dead_code)]
1809 fn assert_covariance() {
1810     fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
1811         x
1812     }
1813     fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
1814         x
1815     }
1816     fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
1817         x
1818     }
1819 }
1820
1821 #[stable(feature = "rust1", since = "1.0.0")]
1822 unsafe impl<T: Send> Send for LinkedList<T> {}
1823
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1826
1827 #[stable(feature = "rust1", since = "1.0.0")]
1828 unsafe impl<T: Sync> Send for Iter<'_, T> {}
1829
1830 #[stable(feature = "rust1", since = "1.0.0")]
1831 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
1832
1833 #[stable(feature = "rust1", since = "1.0.0")]
1834 unsafe impl<T: Send> Send for IterMut<'_, T> {}
1835
1836 #[stable(feature = "rust1", since = "1.0.0")]
1837 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}