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 //! Almost always it is better to use `Vec` or [`VecDeque`] instead of
   7 //! [`LinkedList`]. In general, array-based containers are faster,
   8 //! more memory efficient and make better use of CPU cache.
   9 //!
  10 //! [`LinkedList`]: ../linked_list/struct.LinkedList.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::{Hasher, Hash};
  18 use core::iter::{FromIterator, FusedIterator};
  19 use core::marker::PhantomData;
  20 use core::mem;
  21 use core::ptr::NonNull;
  22
  23 use crate::boxed::Box;
  24 use super::SpecExtend;
  25
  26 /// A doubly-linked list with owned nodes.
  27 ///
  28 /// The `LinkedList` allows pushing and popping elements at either end
  29 /// in constant time.
  30 ///
  31 /// Almost always it is better to use `Vec` or `VecDeque` instead of
  32 /// `LinkedList`. In general, array-based containers are faster,
  33 /// more memory efficient and make better use of CPU cache.
  34 #[stable(feature = "rust1", since = "1.0.0")]
  35 pub struct LinkedList<T> {
  36     head: Option<NonNull<Node<T>>>,
  37     tail: Option<NonNull<Node<T>>>,
  38     len: usize,
  39     marker: PhantomData<Box<Node<T>>>,
  40 }
  41
  42 struct Node<T> {
  43     next: Option<NonNull<Node<T>>>,
  44     prev: Option<NonNull<Node<T>>>,
  45     element: T,
  46 }
  47
  48 /// An iterator over the elements of a `LinkedList`.
  49 ///
  50 /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its
  51 /// documentation for more.
  52 ///
  53 /// [`iter`]: struct.LinkedList.html#method.iter
  54 /// [`LinkedList`]: struct.LinkedList.html
  55 #[stable(feature = "rust1", since = "1.0.0")]
  56 pub struct Iter<'a, T: 'a> {
  57     head: Option<NonNull<Node<T>>>,
  58     tail: Option<NonNull<Node<T>>>,
  59     len: usize,
  60     marker: PhantomData<&'a Node<T>>,
  61 }
  62
  63 #[stable(feature = "collection_debug", since = "1.17.0")]
  64 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
  65     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  66         f.debug_tuple("Iter")
  67          .field(&self.len)
  68          .finish()
  69     }
  70 }
  71
  72 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
  73 #[stable(feature = "rust1", since = "1.0.0")]
  74 impl<T> Clone for Iter<'_, T> {
  75     fn clone(&self) -> Self {
  76         Iter { ..*self }
  77     }
  78 }
  79
  80 /// A mutable iterator over the elements of a `LinkedList`.
  81 ///
  82 /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its
  83 /// documentation for more.
  84 ///
  85 /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut
  86 /// [`LinkedList`]: struct.LinkedList.html
  87 #[stable(feature = "rust1", since = "1.0.0")]
  88 pub struct IterMut<'a, T: 'a> {
  89     // We do *not* exclusively own the entire list here, references to node's `element`
  90     // have been handed out by the iterator!  So be careful when using this; the methods
  91     // called must be aware that there can be aliasing pointers to `element`.
  92     list: &'a mut LinkedList<T>,
  93     head: Option<NonNull<Node<T>>>,
  94     tail: Option<NonNull<Node<T>>>,
  95     len: usize,
  96 }
  97
  98 #[stable(feature = "collection_debug", since = "1.17.0")]
  99 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
 100     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 101         f.debug_tuple("IterMut")
 102          .field(&self.list)
 103          .field(&self.len)
 104          .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`][`LinkedList`]
 111 /// (provided by the `IntoIterator` trait). See its documentation for more.
 112 ///
 113 /// [`into_iter`]: struct.LinkedList.html#method.into_iter
 114 /// [`LinkedList`]: struct.LinkedList.html
 115 #[derive(Clone)]
 116 #[stable(feature = "rust1", since = "1.0.0")]
 117 pub struct IntoIter<T> {
 118     list: LinkedList<T>,
 119 }
 120
 121 #[stable(feature = "collection_debug", since = "1.17.0")]
 122 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
 123     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 124         f.debug_tuple("IntoIter")
 125          .field(&self.list)
 126          .finish()
 127     }
 128 }
 129
 130 impl<T> Node<T> {
 131     fn new(element: T) -> Self {
 132         Node {
 133             next: None,
 134             prev: None,
 135             element,
 136         }
 137     }
 138
 139     fn into_element(self: Box<Self>) -> T {
 140         self.element
 141     }
 142 }
 143
 144 // private methods
 145 impl<T> LinkedList<T> {
 146     /// Adds the given node to the front of the list.
 147     #[inline]
 148     fn push_front_node(&mut self, mut node: Box<Node<T>>) {
 149         // This method takes care not to create mutable references to whole nodes,
 150         // to maintain validity of aliasing pointers into `element`.
 151         unsafe {
 152             node.next = self.head;
 153             node.prev = None;
 154             let node = Some(Box::into_raw_non_null(node));
 155
 156             match self.head {
 157                 None => self.tail = node,
 158                 // Not creating new mutable (unique!) references overlapping `element`.
 159                 Some(head) => (*head.as_ptr()).prev = node,
 160             }
 161
 162             self.head = node;
 163             self.len += 1;
 164         }
 165     }
 166
 167     /// Removes and returns the node at the front of the list.
 168     #[inline]
 169     fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
 170         // This method takes care not to create mutable references to whole nodes,
 171         // to maintain validity of aliasing pointers into `element`.
 172         self.head.map(|node| unsafe {
 173             let node = Box::from_raw(node.as_ptr());
 174             self.head = node.next;
 175
 176             match self.head {
 177                 None => self.tail = None,
 178                 // Not creating new mutable (unique!) references overlapping `element`.
 179                 Some(head) => (*head.as_ptr()).prev = None,
 180             }
 181
 182             self.len -= 1;
 183             node
 184         })
 185     }
 186
 187     /// Adds the given node to the back of the list.
 188     #[inline]
 189     fn push_back_node(&mut self, mut node: Box<Node<T>>) {
 190         // This method takes care not to create mutable references to whole nodes,
 191         // to maintain validity of aliasing pointers into `element`.
 192         unsafe {
 193             node.next = None;
 194             node.prev = self.tail;
 195             let node = Some(Box::into_raw_non_null(node));
 196
 197             match self.tail {
 198                 None => self.head = node,
 199                 // Not creating new mutable (unique!) references overlapping `element`.
 200                 Some(tail) => (*tail.as_ptr()).next = node,
 201             }
 202
 203             self.tail = node;
 204             self.len += 1;
 205         }
 206     }
 207
 208     /// Removes and returns the node at the back of the list.
 209     #[inline]
 210     fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
 211         // This method takes care not to create mutable references to whole nodes,
 212         // to maintain validity of aliasing pointers into `element`.
 213         self.tail.map(|node| unsafe {
 214             let node = Box::from_raw(node.as_ptr());
 215             self.tail = node.prev;
 216
 217             match self.tail {
 218                 None => self.head = None,
 219                 // Not creating new mutable (unique!) references overlapping `element`.
 220                 Some(tail) => (*tail.as_ptr()).next = None,
 221             }
 222
 223             self.len -= 1;
 224             node
 225         })
 226     }
 227
 228     /// Unlinks the specified node from the current list.
 229     ///
 230     /// Warning: this will not check that the provided node belongs to the current list.
 231     ///
 232     /// This method takes care not to create mutable references to `element`, to
 233     /// maintain validity of aliasing pointers.
 234     #[inline]
 235     unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
 236         let node = node.as_mut(); // this one is ours now, we can create an &mut.
 237
 238         // Not creating new mutable (unique!) references overlapping `element`.
 239         match node.prev {
 240             Some(prev) => (*prev.as_ptr()).next = node.next.clone(),
 241             // this node is the head node
 242             None => self.head = node.next.clone(),
 243         };
 244
 245         match node.next {
 246             Some(next) => (*next.as_ptr()).prev = node.prev.clone(),
 247             // this node is the tail node
 248             None => self.tail = node.prev.clone(),
 249         };
 250
 251         self.len -= 1;
 252     }
 253 }
 254
 255 #[stable(feature = "rust1", since = "1.0.0")]
 256 impl<T> Default for LinkedList<T> {
 257     /// Creates an empty `LinkedList<T>`.
 258     #[inline]
 259     fn default() -> Self {
 260         Self::new()
 261     }
 262 }
 263
 264 impl<T> LinkedList<T> {
 265     /// Creates an empty `LinkedList`.
 266     ///
 267     /// # Examples
 268     ///
 269     /// ```
 270     /// use std::collections::LinkedList;
 271     ///
 272     /// let list: LinkedList<u32> = LinkedList::new();
 273     /// ```
 274     #[inline]
 275     #[stable(feature = "rust1", since = "1.0.0")]
 276     pub fn new() -> Self {
 277         LinkedList {
 278             head: None,
 279             tail: None,
 280             len: 0,
 281             marker: PhantomData,
 282         }
 283     }
 284
 285     /// Moves all elements from `other` to the end of the list.
 286     ///
 287     /// This reuses all the nodes from `other` and moves them into `self`. After
 288     /// this operation, `other` becomes empty.
 289     ///
 290     /// This operation should compute in O(1) time and O(1) memory.
 291     ///
 292     /// # Examples
 293     ///
 294     /// ```
 295     /// use std::collections::LinkedList;
 296     ///
 297     /// let mut list1 = LinkedList::new();
 298     /// list1.push_back('a');
 299     ///
 300     /// let mut list2 = LinkedList::new();
 301     /// list2.push_back('b');
 302     /// list2.push_back('c');
 303     ///
 304     /// list1.append(&mut list2);
 305     ///
 306     /// let mut iter = list1.iter();
 307     /// assert_eq!(iter.next(), Some(&'a'));
 308     /// assert_eq!(iter.next(), Some(&'b'));
 309     /// assert_eq!(iter.next(), Some(&'c'));
 310     /// assert!(iter.next().is_none());
 311     ///
 312     /// assert!(list2.is_empty());
 313     /// ```
 314     #[stable(feature = "rust1", since = "1.0.0")]
 315     pub fn append(&mut self, other: &mut Self) {
 316         match self.tail {
 317             None => mem::swap(self, other),
 318             Some(mut tail) => {
 319                 // `as_mut` is okay here because we have exclusive access to the entirety
 320                 // of both lists.
 321                 if let Some(mut other_head) = other.head.take() {
 322                     unsafe {
 323                         tail.as_mut().next = Some(other_head);
 324                         other_head.as_mut().prev = Some(tail);
 325                     }
 326
 327                     self.tail = other.tail.take();
 328                     self.len += mem::replace(&mut other.len, 0);
 329                 }
 330             }
 331         }
 332     }
 333
 334     /// Provides a forward iterator.
 335     ///
 336     /// # Examples
 337     ///
 338     /// ```
 339     /// use std::collections::LinkedList;
 340     ///
 341     /// let mut list: LinkedList<u32> = LinkedList::new();
 342     ///
 343     /// list.push_back(0);
 344     /// list.push_back(1);
 345     /// list.push_back(2);
 346     ///
 347     /// let mut iter = list.iter();
 348     /// assert_eq!(iter.next(), Some(&0));
 349     /// assert_eq!(iter.next(), Some(&1));
 350     /// assert_eq!(iter.next(), Some(&2));
 351     /// assert_eq!(iter.next(), None);
 352     /// ```
 353     #[inline]
 354     #[stable(feature = "rust1", since = "1.0.0")]
 355     pub fn iter(&self) -> Iter<'_, T> {
 356         Iter {
 357             head: self.head,
 358             tail: self.tail,
 359             len: self.len,
 360             marker: PhantomData,
 361         }
 362     }
 363
 364     /// Provides a forward iterator with mutable references.
 365     ///
 366     /// # Examples
 367     ///
 368     /// ```
 369     /// use std::collections::LinkedList;
 370     ///
 371     /// let mut list: LinkedList<u32> = LinkedList::new();
 372     ///
 373     /// list.push_back(0);
 374     /// list.push_back(1);
 375     /// list.push_back(2);
 376     ///
 377     /// for element in list.iter_mut() {
 378     ///     *element += 10;
 379     /// }
 380     ///
 381     /// let mut iter = list.iter();
 382     /// assert_eq!(iter.next(), Some(&10));
 383     /// assert_eq!(iter.next(), Some(&11));
 384     /// assert_eq!(iter.next(), Some(&12));
 385     /// assert_eq!(iter.next(), None);
 386     /// ```
 387     #[inline]
 388     #[stable(feature = "rust1", since = "1.0.0")]
 389     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
 390         IterMut {
 391             head: self.head,
 392             tail: self.tail,
 393             len: self.len,
 394             list: self,
 395         }
 396     }
 397
 398     /// Returns `true` if the `LinkedList` is empty.
 399     ///
 400     /// This operation should compute in O(1) time.
 401     ///
 402     /// # Examples
 403     ///
 404     /// ```
 405     /// use std::collections::LinkedList;
 406     ///
 407     /// let mut dl = LinkedList::new();
 408     /// assert!(dl.is_empty());
 409     ///
 410     /// dl.push_front("foo");
 411     /// assert!(!dl.is_empty());
 412     /// ```
 413     #[inline]
 414     #[stable(feature = "rust1", since = "1.0.0")]
 415     pub fn is_empty(&self) -> bool {
 416         self.head.is_none()
 417     }
 418
 419     /// Returns the length of the `LinkedList`.
 420     ///
 421     /// This operation should compute in O(1) time.
 422     ///
 423     /// # Examples
 424     ///
 425     /// ```
 426     /// use std::collections::LinkedList;
 427     ///
 428     /// let mut dl = LinkedList::new();
 429     ///
 430     /// dl.push_front(2);
 431     /// assert_eq!(dl.len(), 1);
 432     ///
 433     /// dl.push_front(1);
 434     /// assert_eq!(dl.len(), 2);
 435     ///
 436     /// dl.push_back(3);
 437     /// assert_eq!(dl.len(), 3);
 438     /// ```
 439     #[inline]
 440     #[stable(feature = "rust1", since = "1.0.0")]
 441     pub fn len(&self) -> usize {
 442         self.len
 443     }
 444
 445     /// Removes all elements from the `LinkedList`.
 446     ///
 447     /// This operation should compute in O(n) time.
 448     ///
 449     /// # Examples
 450     ///
 451     /// ```
 452     /// use std::collections::LinkedList;
 453     ///
 454     /// let mut dl = LinkedList::new();
 455     ///
 456     /// dl.push_front(2);
 457     /// dl.push_front(1);
 458     /// assert_eq!(dl.len(), 2);
 459     /// assert_eq!(dl.front(), Some(&1));
 460     ///
 461     /// dl.clear();
 462     /// assert_eq!(dl.len(), 0);
 463     /// assert_eq!(dl.front(), None);
 464     /// ```
 465     #[inline]
 466     #[stable(feature = "rust1", since = "1.0.0")]
 467     pub fn clear(&mut self) {
 468         *self = Self::new();
 469     }
 470
 471     /// Returns `true` if the `LinkedList` contains an element equal to the
 472     /// given value.
 473     ///
 474     /// # Examples
 475     ///
 476     /// ```
 477     /// use std::collections::LinkedList;
 478     ///
 479     /// let mut list: LinkedList<u32> = LinkedList::new();
 480     ///
 481     /// list.push_back(0);
 482     /// list.push_back(1);
 483     /// list.push_back(2);
 484     ///
 485     /// assert_eq!(list.contains(&0), true);
 486     /// assert_eq!(list.contains(&10), false);
 487     /// ```
 488     #[stable(feature = "linked_list_contains", since = "1.12.0")]
 489     pub fn contains(&self, x: &T) -> bool
 490         where T: PartialEq<T>
 491     {
 492         self.iter().any(|e| e == x)
 493     }
 494
 495     /// Provides a reference to the front element, or `None` if the list is
 496     /// empty.
 497     ///
 498     /// # Examples
 499     ///
 500     /// ```
 501     /// use std::collections::LinkedList;
 502     ///
 503     /// let mut dl = LinkedList::new();
 504     /// assert_eq!(dl.front(), None);
 505     ///
 506     /// dl.push_front(1);
 507     /// assert_eq!(dl.front(), Some(&1));
 508     /// ```
 509     #[inline]
 510     #[stable(feature = "rust1", since = "1.0.0")]
 511     pub fn front(&self) -> Option<&T> {
 512         unsafe {
 513             self.head.as_ref().map(|node| &node.as_ref().element)
 514         }
 515     }
 516
 517     /// Provides a mutable reference to the front element, or `None` if the list
 518     /// is empty.
 519     ///
 520     /// # Examples
 521     ///
 522     /// ```
 523     /// use std::collections::LinkedList;
 524     ///
 525     /// let mut dl = LinkedList::new();
 526     /// assert_eq!(dl.front(), None);
 527     ///
 528     /// dl.push_front(1);
 529     /// assert_eq!(dl.front(), Some(&1));
 530     ///
 531     /// match dl.front_mut() {
 532     ///     None => {},
 533     ///     Some(x) => *x = 5,
 534     /// }
 535     /// assert_eq!(dl.front(), Some(&5));
 536     /// ```
 537     #[inline]
 538     #[stable(feature = "rust1", since = "1.0.0")]
 539     pub fn front_mut(&mut self) -> Option<&mut T> {
 540         unsafe {
 541             self.head.as_mut().map(|node| &mut node.as_mut().element)
 542         }
 543     }
 544
 545     /// Provides a reference to the back element, or `None` if the list is
 546     /// empty.
 547     ///
 548     /// # Examples
 549     ///
 550     /// ```
 551     /// use std::collections::LinkedList;
 552     ///
 553     /// let mut dl = LinkedList::new();
 554     /// assert_eq!(dl.back(), None);
 555     ///
 556     /// dl.push_back(1);
 557     /// assert_eq!(dl.back(), Some(&1));
 558     /// ```
 559     #[inline]
 560     #[stable(feature = "rust1", since = "1.0.0")]
 561     pub fn back(&self) -> Option<&T> {
 562         unsafe {
 563             self.tail.as_ref().map(|node| &node.as_ref().element)
 564         }
 565     }
 566
 567     /// Provides a mutable reference to the back element, or `None` if the list
 568     /// is empty.
 569     ///
 570     /// # Examples
 571     ///
 572     /// ```
 573     /// use std::collections::LinkedList;
 574     ///
 575     /// let mut dl = LinkedList::new();
 576     /// assert_eq!(dl.back(), None);
 577     ///
 578     /// dl.push_back(1);
 579     /// assert_eq!(dl.back(), Some(&1));
 580     ///
 581     /// match dl.back_mut() {
 582     ///     None => {},
 583     ///     Some(x) => *x = 5,
 584     /// }
 585     /// assert_eq!(dl.back(), Some(&5));
 586     /// ```
 587     #[inline]
 588     #[stable(feature = "rust1", since = "1.0.0")]
 589     pub fn back_mut(&mut self) -> Option<&mut T> {
 590         unsafe {
 591             self.tail.as_mut().map(|node| &mut node.as_mut().element)
 592         }
 593     }
 594
 595     /// Adds an element first in the list.
 596     ///
 597     /// This operation should compute in O(1) 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     /// assert_eq!(dl.front().unwrap(), &2);
 608     ///
 609     /// dl.push_front(1);
 610     /// assert_eq!(dl.front().unwrap(), &1);
 611     /// ```
 612     #[stable(feature = "rust1", since = "1.0.0")]
 613     pub fn push_front(&mut self, elt: T) {
 614         self.push_front_node(box Node::new(elt));
 615     }
 616
 617     /// Removes the first element and returns it, or `None` if the list is
 618     /// empty.
 619     ///
 620     /// This operation should compute in O(1) time.
 621     ///
 622     /// # Examples
 623     ///
 624     /// ```
 625     /// use std::collections::LinkedList;
 626     ///
 627     /// let mut d = LinkedList::new();
 628     /// assert_eq!(d.pop_front(), None);
 629     ///
 630     /// d.push_front(1);
 631     /// d.push_front(3);
 632     /// assert_eq!(d.pop_front(), Some(3));
 633     /// assert_eq!(d.pop_front(), Some(1));
 634     /// assert_eq!(d.pop_front(), None);
 635     /// ```
 636     #[stable(feature = "rust1", since = "1.0.0")]
 637     pub fn pop_front(&mut self) -> Option<T> {
 638         self.pop_front_node().map(Node::into_element)
 639     }
 640
 641     /// Appends an element to the back of a list.
 642     ///
 643     /// This operation should compute in O(1) time.
 644     ///
 645     /// # Examples
 646     ///
 647     /// ```
 648     /// use std::collections::LinkedList;
 649     ///
 650     /// let mut d = LinkedList::new();
 651     /// d.push_back(1);
 652     /// d.push_back(3);
 653     /// assert_eq!(3, *d.back().unwrap());
 654     /// ```
 655     #[stable(feature = "rust1", since = "1.0.0")]
 656     pub fn push_back(&mut self, elt: T) {
 657         self.push_back_node(box Node::new(elt));
 658     }
 659
 660     /// Removes the last element from a list and returns it, or `None` if
 661     /// it is empty.
 662     ///
 663     /// This operation should compute in O(1) time.
 664     ///
 665     /// # Examples
 666     ///
 667     /// ```
 668     /// use std::collections::LinkedList;
 669     ///
 670     /// let mut d = LinkedList::new();
 671     /// assert_eq!(d.pop_back(), None);
 672     /// d.push_back(1);
 673     /// d.push_back(3);
 674     /// assert_eq!(d.pop_back(), Some(3));
 675     /// ```
 676     #[stable(feature = "rust1", since = "1.0.0")]
 677     pub fn pop_back(&mut self) -> Option<T> {
 678         self.pop_back_node().map(Node::into_element)
 679     }
 680
 681     /// Splits the list into two at the given index. Returns everything after the given index,
 682     /// including the index.
 683     ///
 684     /// This operation should compute in O(n) time.
 685     ///
 686     /// # Panics
 687     ///
 688     /// Panics if `at > len`.
 689     ///
 690     /// # Examples
 691     ///
 692     /// ```
 693     /// use std::collections::LinkedList;
 694     ///
 695     /// let mut d = LinkedList::new();
 696     ///
 697     /// d.push_front(1);
 698     /// d.push_front(2);
 699     /// d.push_front(3);
 700     ///
 701     /// let mut splitted = d.split_off(2);
 702     ///
 703     /// assert_eq!(splitted.pop_front(), Some(1));
 704     /// assert_eq!(splitted.pop_front(), None);
 705     /// ```
 706     #[stable(feature = "rust1", since = "1.0.0")]
 707     pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
 708         let len = self.len();
 709         assert!(at <= len, "Cannot split off at a nonexistent index");
 710         if at == 0 {
 711             return mem::take(self);
 712         } else if at == len {
 713             return Self::new();
 714         }
 715
 716         // Below, we iterate towards the `i-1`th node, either from the start or the end,
 717         // depending on which would be faster.
 718         let split_node = if at - 1 <= len - 1 - (at - 1) {
 719             let mut iter = self.iter_mut();
 720             // instead of skipping using .skip() (which creates a new struct),
 721             // we skip manually so we can access the head field without
 722             // depending on implementation details of Skip
 723             for _ in 0..at - 1 {
 724                 iter.next();
 725             }
 726             iter.head
 727         } else {
 728             // better off starting from the end
 729             let mut iter = self.iter_mut();
 730             for _ in 0..len - 1 - (at - 1) {
 731                 iter.next_back();
 732             }
 733             iter.tail
 734         };
 735
 736         // The split node is the new tail node of the first part and owns
 737         // the head of the second part.
 738         let second_part_head;
 739
 740         unsafe {
 741             second_part_head = split_node.unwrap().as_mut().next.take();
 742             if let Some(mut head) = second_part_head {
 743                 head.as_mut().prev = None;
 744             }
 745         }
 746
 747         let second_part = LinkedList {
 748             head: second_part_head,
 749             tail: self.tail,
 750             len: len - at,
 751             marker: PhantomData,
 752         };
 753
 754         // Fix the tail ptr of the first part
 755         self.tail = split_node;
 756         self.len = at;
 757
 758         second_part
 759     }
 760
 761     /// Creates an iterator which uses a closure to determine if an element should be removed.
 762     ///
 763     /// If the closure returns true, then the element is removed and yielded.
 764     /// If the closure returns false, the element will remain in the list and will not be yielded
 765     /// by the iterator.
 766     ///
 767     /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of
 768     /// whether you choose to keep or remove it.
 769     ///
 770     /// # Examples
 771     ///
 772     /// Splitting a list into evens and odds, reusing the original list:
 773     ///
 774     /// ```
 775     /// #![feature(drain_filter)]
 776     /// use std::collections::LinkedList;
 777     ///
 778     /// let mut numbers: LinkedList<u32> = LinkedList::new();
 779     /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
 780     ///
 781     /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
 782     /// let odds = numbers;
 783     ///
 784     /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
 785     /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
 786     /// ```
 787     #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 788     pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
 789         where F: FnMut(&mut T) -> bool
 790     {
 791         // avoid borrow issues.
 792         let it = self.head;
 793         let old_len = self.len;
 794
 795         DrainFilter {
 796             list: self,
 797             it: it,
 798             pred: filter,
 799             idx: 0,
 800             old_len: old_len,
 801         }
 802     }
 803 }
 804
 805 #[stable(feature = "rust1", since = "1.0.0")]
 806 unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
 807     fn drop(&mut self) {
 808         while let Some(_) = self.pop_front_node() {}
 809     }
 810 }
 811
 812 #[stable(feature = "rust1", since = "1.0.0")]
 813 impl<'a, T> Iterator for Iter<'a, T> {
 814     type Item = &'a T;
 815
 816     #[inline]
 817     fn next(&mut self) -> Option<&'a T> {
 818         if self.len == 0 {
 819             None
 820         } else {
 821             self.head.map(|node| unsafe {
 822                 // Need an unbound lifetime to get 'a
 823                 let node = &*node.as_ptr();
 824                 self.len -= 1;
 825                 self.head = node.next;
 826                 &node.element
 827             })
 828         }
 829     }
 830
 831     #[inline]
 832     fn size_hint(&self) -> (usize, Option<usize>) {
 833         (self.len, Some(self.len))
 834     }
 835
 836     #[inline]
 837     fn last(mut self) -> Option<&'a T> {
 838         self.next_back()
 839     }
 840 }
 841
 842 #[stable(feature = "rust1", since = "1.0.0")]
 843 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 844     #[inline]
 845     fn next_back(&mut self) -> Option<&'a T> {
 846         if self.len == 0 {
 847             None
 848         } else {
 849             self.tail.map(|node| unsafe {
 850                 // Need an unbound lifetime to get 'a
 851                 let node = &*node.as_ptr();
 852                 self.len -= 1;
 853                 self.tail = node.prev;
 854                 &node.element
 855             })
 856         }
 857     }
 858 }
 859
 860 #[stable(feature = "rust1", since = "1.0.0")]
 861 impl<T> ExactSizeIterator for Iter<'_, T> {}
 862
 863 #[stable(feature = "fused", since = "1.26.0")]
 864 impl<T> FusedIterator for Iter<'_, T> {}
 865
 866 #[stable(feature = "rust1", since = "1.0.0")]
 867 impl<'a, T> Iterator for IterMut<'a, T> {
 868     type Item = &'a mut T;
 869
 870     #[inline]
 871     fn next(&mut self) -> Option<&'a mut T> {
 872         if self.len == 0 {
 873             None
 874         } else {
 875             self.head.map(|node| unsafe {
 876                 // Need an unbound lifetime to get 'a
 877                 let node = &mut *node.as_ptr();
 878                 self.len -= 1;
 879                 self.head = node.next;
 880                 &mut node.element
 881             })
 882         }
 883     }
 884
 885     #[inline]
 886     fn size_hint(&self) -> (usize, Option<usize>) {
 887         (self.len, Some(self.len))
 888     }
 889
 890     #[inline]
 891     fn last(mut self) -> Option<&'a mut T> {
 892         self.next_back()
 893     }
 894 }
 895
 896 #[stable(feature = "rust1", since = "1.0.0")]
 897 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 898     #[inline]
 899     fn next_back(&mut self) -> Option<&'a mut T> {
 900         if self.len == 0 {
 901             None
 902         } else {
 903             self.tail.map(|node| unsafe {
 904                 // Need an unbound lifetime to get 'a
 905                 let node = &mut *node.as_ptr();
 906                 self.len -= 1;
 907                 self.tail = node.prev;
 908                 &mut node.element
 909             })
 910         }
 911     }
 912 }
 913
 914 #[stable(feature = "rust1", since = "1.0.0")]
 915 impl<T> ExactSizeIterator for IterMut<'_, T> {}
 916
 917 #[stable(feature = "fused", since = "1.26.0")]
 918 impl<T> FusedIterator for IterMut<'_, T> {}
 919
 920 impl<T> IterMut<'_, T> {
 921     /// Inserts the given element just after the element most recently returned by `.next()`.
 922     /// The inserted element does not appear in the iteration.
 923     ///
 924     /// # Examples
 925     ///
 926     /// ```
 927     /// #![feature(linked_list_extras)]
 928     ///
 929     /// use std::collections::LinkedList;
 930     ///
 931     /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
 932     ///
 933     /// {
 934     ///     let mut it = list.iter_mut();
 935     ///     assert_eq!(it.next().unwrap(), &1);
 936     ///     // insert `2` after `1`
 937     ///     it.insert_next(2);
 938     /// }
 939     /// {
 940     ///     let vec: Vec<_> = list.into_iter().collect();
 941     ///     assert_eq!(vec, [1, 2, 3, 4]);
 942     /// }
 943     /// ```
 944     #[inline]
 945     #[unstable(feature = "linked_list_extras",
 946                reason = "this is probably better handled by a cursor type -- we'll see",
 947                issue = "27794")]
 948     pub fn insert_next(&mut self, element: T) {
 949         match self.head {
 950             // `push_back` is okay with aliasing `element` references
 951             None => self.list.push_back(element),
 952             Some(head) => unsafe {
 953                 let prev = match head.as_ref().prev {
 954                     // `push_front` is okay with aliasing nodes
 955                     None => return self.list.push_front(element),
 956                     Some(prev) => prev,
 957                 };
 958
 959                 let node = Some(Box::into_raw_non_null(box Node {
 960                     next: Some(head),
 961                     prev: Some(prev),
 962                     element,
 963                 }));
 964
 965                 // Not creating references to entire nodes to not invalidate the
 966                 // reference to `element` we handed to the user.
 967                 (*prev.as_ptr()).next = node;
 968                 (*head.as_ptr()).prev = node;
 969
 970                 self.list.len += 1;
 971             },
 972         }
 973     }
 974
 975     /// Provides a reference to the next element, without changing the iterator.
 976     ///
 977     /// # Examples
 978     ///
 979     /// ```
 980     /// #![feature(linked_list_extras)]
 981     ///
 982     /// use std::collections::LinkedList;
 983     ///
 984     /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
 985     ///
 986     /// let mut it = list.iter_mut();
 987     /// assert_eq!(it.next().unwrap(), &1);
 988     /// assert_eq!(it.peek_next().unwrap(), &2);
 989     /// // We just peeked at 2, so it was not consumed from the iterator.
 990     /// assert_eq!(it.next().unwrap(), &2);
 991     /// ```
 992     #[inline]
 993     #[unstable(feature = "linked_list_extras",
 994                reason = "this is probably better handled by a cursor type -- we'll see",
 995                issue = "27794")]
 996     pub fn peek_next(&mut self) -> Option<&mut T> {
 997         if self.len == 0 {
 998             None
 999         } else {
1000             unsafe {
1001                 self.head.as_mut().map(|node| &mut node.as_mut().element)
1002             }
1003         }
1004     }
1005 }
1006
1007 /// An iterator produced by calling `drain_filter` on LinkedList.
1008 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1009 pub struct DrainFilter<'a, T: 'a, F: 'a>
1010     where F: FnMut(&mut T) -> bool,
1011 {
1012     list: &'a mut LinkedList<T>,
1013     it: Option<NonNull<Node<T>>>,
1014     pred: F,
1015     idx: usize,
1016     old_len: usize,
1017 }
1018
1019 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1020 impl<T, F> Iterator for DrainFilter<'_, T, F>
1021     where F: FnMut(&mut T) -> bool,
1022 {
1023     type Item = T;
1024
1025     fn next(&mut self) -> Option<T> {
1026         while let Some(mut node) = self.it {
1027             unsafe {
1028                 self.it = node.as_ref().next;
1029                 self.idx += 1;
1030
1031                 if (self.pred)(&mut node.as_mut().element) {
1032                     // `unlink_node` is okay with aliasing `element` references.
1033                     self.list.unlink_node(node);
1034                     return Some(Box::from_raw(node.as_ptr()).element);
1035                 }
1036             }
1037         }
1038
1039         None
1040     }
1041
1042     fn size_hint(&self) -> (usize, Option<usize>) {
1043         (0, Some(self.old_len - self.idx))
1044     }
1045 }
1046
1047 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1048 impl<T, F> Drop for DrainFilter<'_, T, F>
1049     where F: FnMut(&mut T) -> bool,
1050 {
1051     fn drop(&mut self) {
1052         self.for_each(drop);
1053     }
1054 }
1055
1056 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1057 impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
1058     where F: FnMut(&mut T) -> bool
1059 {
1060     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1061         f.debug_tuple("DrainFilter")
1062          .field(&self.list)
1063          .finish()
1064     }
1065 }
1066
1067 #[stable(feature = "rust1", since = "1.0.0")]
1068 impl<T> Iterator for IntoIter<T> {
1069     type Item = T;
1070
1071     #[inline]
1072     fn next(&mut self) -> Option<T> {
1073         self.list.pop_front()
1074     }
1075
1076     #[inline]
1077     fn size_hint(&self) -> (usize, Option<usize>) {
1078         (self.list.len, Some(self.list.len))
1079     }
1080 }
1081
1082 #[stable(feature = "rust1", since = "1.0.0")]
1083 impl<T> DoubleEndedIterator for IntoIter<T> {
1084     #[inline]
1085     fn next_back(&mut self) -> Option<T> {
1086         self.list.pop_back()
1087     }
1088 }
1089
1090 #[stable(feature = "rust1", since = "1.0.0")]
1091 impl<T> ExactSizeIterator for IntoIter<T> {}
1092
1093 #[stable(feature = "fused", since = "1.26.0")]
1094 impl<T> FusedIterator for IntoIter<T> {}
1095
1096 #[stable(feature = "rust1", since = "1.0.0")]
1097 impl<T> FromIterator<T> for LinkedList<T> {
1098     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1099         let mut list = Self::new();
1100         list.extend(iter);
1101         list
1102     }
1103 }
1104
1105 #[stable(feature = "rust1", since = "1.0.0")]
1106 impl<T> IntoIterator for LinkedList<T> {
1107     type Item = T;
1108     type IntoIter = IntoIter<T>;
1109
1110     /// Consumes the list into an iterator yielding elements by value.
1111     #[inline]
1112     fn into_iter(self) -> IntoIter<T> {
1113         IntoIter { list: self }
1114     }
1115 }
1116
1117 #[stable(feature = "rust1", since = "1.0.0")]
1118 impl<'a, T> IntoIterator for &'a LinkedList<T> {
1119     type Item = &'a T;
1120     type IntoIter = Iter<'a, T>;
1121
1122     fn into_iter(self) -> Iter<'a, T> {
1123         self.iter()
1124     }
1125 }
1126
1127 #[stable(feature = "rust1", since = "1.0.0")]
1128 impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
1129     type Item = &'a mut T;
1130     type IntoIter = IterMut<'a, T>;
1131
1132     fn into_iter(self) -> IterMut<'a, T> {
1133         self.iter_mut()
1134     }
1135 }
1136
1137 #[stable(feature = "rust1", since = "1.0.0")]
1138 impl<T> Extend<T> for LinkedList<T> {
1139     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1140         <Self as SpecExtend<I>>::spec_extend(self, iter);
1141     }
1142 }
1143
1144 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
1145     default fn spec_extend(&mut self, iter: I) {
1146         iter.into_iter().for_each(move |elt| self.push_back(elt));
1147     }
1148 }
1149
1150 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
1151     fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
1152         self.append(other);
1153     }
1154 }
1155
1156 #[stable(feature = "extend_ref", since = "1.2.0")]
1157 impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
1158     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1159         self.extend(iter.into_iter().cloned());
1160     }
1161 }
1162
1163 #[stable(feature = "rust1", since = "1.0.0")]
1164 impl<T: PartialEq> PartialEq for LinkedList<T> {
1165     fn eq(&self, other: &Self) -> bool {
1166         self.len() == other.len() && self.iter().eq(other)
1167     }
1168
1169     fn ne(&self, other: &Self) -> bool {
1170         self.len() != other.len() || self.iter().ne(other)
1171     }
1172 }
1173
1174 #[stable(feature = "rust1", since = "1.0.0")]
1175 impl<T: Eq> Eq for LinkedList<T> {}
1176
1177 #[stable(feature = "rust1", since = "1.0.0")]
1178 impl<T: PartialOrd> PartialOrd for LinkedList<T> {
1179     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1180         self.iter().partial_cmp(other)
1181     }
1182 }
1183
1184 #[stable(feature = "rust1", since = "1.0.0")]
1185 impl<T: Ord> Ord for LinkedList<T> {
1186     #[inline]
1187     fn cmp(&self, other: &Self) -> Ordering {
1188         self.iter().cmp(other)
1189     }
1190 }
1191
1192 #[stable(feature = "rust1", since = "1.0.0")]
1193 impl<T: Clone> Clone for LinkedList<T> {
1194     fn clone(&self) -> Self {
1195         self.iter().cloned().collect()
1196     }
1197 }
1198
1199 #[stable(feature = "rust1", since = "1.0.0")]
1200 impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
1201     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1202         f.debug_list().entries(self).finish()
1203     }
1204 }
1205
1206 #[stable(feature = "rust1", since = "1.0.0")]
1207 impl<T: Hash> Hash for LinkedList<T> {
1208     fn hash<H: Hasher>(&self, state: &mut H) {
1209         self.len().hash(state);
1210         for elt in self {
1211             elt.hash(state);
1212         }
1213     }
1214 }
1215
1216 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1217 #[allow(dead_code)]
1218 fn assert_covariance() {
1219     fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
1220         x
1221     }
1222     fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
1223         x
1224     }
1225     fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
1226         x
1227     }
1228 }
1229
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 unsafe impl<T: Send> Send for LinkedList<T> {}
1232
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1235
1236 #[stable(feature = "rust1", since = "1.0.0")]
1237 unsafe impl<T: Sync> Send for Iter<'_, T> {}
1238
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
1241
1242 #[stable(feature = "rust1", since = "1.0.0")]
1243 unsafe impl<T: Send> Send for IterMut<'_, T> {}
1244
1245 #[stable(feature = "rust1", since = "1.0.0")]
1246 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
1247
1248 #[cfg(test)]
1249 mod tests {
1250     use std::thread;
1251     use std::vec::Vec;
1252
1253     use rand::{thread_rng, RngCore};
1254
1255     use super::{LinkedList, Node};
1256
1257     #[cfg(test)]
1258     fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
1259         v.iter().cloned().collect()
1260     }
1261
1262     pub fn check_links<T>(list: &LinkedList<T>) {
1263         unsafe {
1264             let mut len = 0;
1265             let mut last_ptr: Option<&Node<T>> = None;
1266             let mut node_ptr: &Node<T>;
1267             match list.head {
1268                 None => {
1269                     // tail node should also be None.
1270                     assert!(list.tail.is_none());
1271                     assert_eq!(0, list.len);
1272                     return;
1273                 }
1274                 Some(node) => node_ptr = &*node.as_ptr(),
1275             }
1276             loop {
1277                 match (last_ptr, node_ptr.prev) {
1278                     (None, None) => {}
1279                     (None, _) => panic!("prev link for head"),
1280                     (Some(p), Some(pptr)) => {
1281                         assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
1282                     }
1283                     _ => panic!("prev link is none, not good"),
1284                 }
1285                 match node_ptr.next {
1286                     Some(next) => {
1287                         last_ptr = Some(node_ptr);
1288                         node_ptr = &*next.as_ptr();
1289                         len += 1;
1290                     }
1291                     None => {
1292                         len += 1;
1293                         break;
1294                     }
1295                 }
1296             }
1297
1298             // verify that the tail node points to the last node.
1299             let tail = list.tail.as_ref().expect("some tail node").as_ref();
1300             assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
1301             // check that len matches interior links.
1302             assert_eq!(len, list.len);
1303         }
1304     }
1305
1306     #[test]
1307     fn test_append() {
1308         // Empty to empty
1309         {
1310             let mut m = LinkedList::<i32>::new();
1311             let mut n = LinkedList::new();
1312             m.append(&mut n);
1313             check_links(&m);
1314             assert_eq!(m.len(), 0);
1315             assert_eq!(n.len(), 0);
1316         }
1317         // Non-empty to empty
1318         {
1319             let mut m = LinkedList::new();
1320             let mut n = LinkedList::new();
1321             n.push_back(2);
1322             m.append(&mut n);
1323             check_links(&m);
1324             assert_eq!(m.len(), 1);
1325             assert_eq!(m.pop_back(), Some(2));
1326             assert_eq!(n.len(), 0);
1327             check_links(&m);
1328         }
1329         // Empty to non-empty
1330         {
1331             let mut m = LinkedList::new();
1332             let mut n = LinkedList::new();
1333             m.push_back(2);
1334             m.append(&mut n);
1335             check_links(&m);
1336             assert_eq!(m.len(), 1);
1337             assert_eq!(m.pop_back(), Some(2));
1338             check_links(&m);
1339         }
1340
1341         // Non-empty to non-empty
1342         let v = vec![1, 2, 3, 4, 5];
1343         let u = vec![9, 8, 1, 2, 3, 4, 5];
1344         let mut m = list_from(&v);
1345         let mut n = list_from(&u);
1346         m.append(&mut n);
1347         check_links(&m);
1348         let mut sum = v;
1349         sum.extend_from_slice(&u);
1350         assert_eq!(sum.len(), m.len());
1351         for elt in sum {
1352             assert_eq!(m.pop_front(), Some(elt))
1353         }
1354         assert_eq!(n.len(), 0);
1355         // let's make sure it's working properly, since we
1356         // did some direct changes to private members
1357         n.push_back(3);
1358         assert_eq!(n.len(), 1);
1359         assert_eq!(n.pop_front(), Some(3));
1360         check_links(&n);
1361     }
1362
1363     #[test]
1364     fn test_insert_prev() {
1365         let mut m = list_from(&[0, 2, 4, 6, 8]);
1366         let len = m.len();
1367         {
1368             let mut it = m.iter_mut();
1369             it.insert_next(-2);
1370             loop {
1371                 match it.next() {
1372                     None => break,
1373                     Some(elt) => {
1374                         it.insert_next(*elt + 1);
1375                         match it.peek_next() {
1376                             Some(x) => assert_eq!(*x, *elt + 2),
1377                             None => assert_eq!(8, *elt),
1378                         }
1379                     }
1380                 }
1381             }
1382             it.insert_next(0);
1383             it.insert_next(1);
1384         }
1385         check_links(&m);
1386         assert_eq!(m.len(), 3 + len * 2);
1387         assert_eq!(m.into_iter().collect::<Vec<_>>(),
1388                    [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
1389     }
1390
1391     #[test]
1392     #[cfg_attr(target_os = "emscripten", ignore)]
1393     #[cfg(not(miri))] // Miri does not support threads
1394     fn test_send() {
1395         let n = list_from(&[1, 2, 3]);
1396         thread::spawn(move || {
1397                 check_links(&n);
1398                 let a: &[_] = &[&1, &2, &3];
1399                 assert_eq!(a, &*n.iter().collect::<Vec<_>>());
1400             })
1401             .join()
1402             .ok()
1403             .unwrap();
1404     }
1405
1406     #[test]
1407     fn test_fuzz() {
1408         for _ in 0..25 {
1409             fuzz_test(3);
1410             fuzz_test(16);
1411             #[cfg(not(miri))] // Miri is too slow
1412             fuzz_test(189);
1413         }
1414     }
1415
1416     #[test]
1417     fn test_26021() {
1418         // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
1419         // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
1420         // its nodes.
1421         //
1422         // https://github.com/rust-lang/rust/issues/26021
1423         let mut v1 = LinkedList::new();
1424         v1.push_front(1);
1425         v1.push_front(1);
1426         v1.push_front(1);
1427         v1.push_front(1);
1428         let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
1429         assert_eq!(v1.len(), 3);
1430
1431         assert_eq!(v1.iter().len(), 3);
1432         assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
1433     }
1434
1435     #[test]
1436     fn test_split_off() {
1437         let mut v1 = LinkedList::new();
1438         v1.push_front(1);
1439         v1.push_front(1);
1440         v1.push_front(1);
1441         v1.push_front(1);
1442
1443         // test all splits
1444         for ix in 0..1 + v1.len() {
1445             let mut a = v1.clone();
1446             let b = a.split_off(ix);
1447             check_links(&a);
1448             check_links(&b);
1449             a.extend(b);
1450             assert_eq!(v1, a);
1451         }
1452     }
1453
1454     #[cfg(test)]
1455     fn fuzz_test(sz: i32) {
1456         let mut m: LinkedList<_> = LinkedList::new();
1457         let mut v = vec![];
1458         for i in 0..sz {
1459             check_links(&m);
1460             let r: u8 = thread_rng().next_u32() as u8;
1461             match r % 6 {
1462                 0 => {
1463                     m.pop_back();
1464                     v.pop();
1465                 }
1466                 1 => {
1467                     if !v.is_empty() {
1468                         m.pop_front();
1469                         v.remove(0);
1470                     }
1471                 }
1472                 2 | 4 => {
1473                     m.push_front(-i);
1474                     v.insert(0, -i);
1475                 }
1476                 3 | 5 | _ => {
1477                     m.push_back(i);
1478                     v.push(i);
1479                 }
1480             }
1481         }
1482
1483         check_links(&m);
1484
1485         let mut i = 0;
1486         for (a, &b) in m.into_iter().zip(&v) {
1487             i += 1;
1488             assert_eq!(a, b);
1489         }
1490         assert_eq!(i, v.len());
1491     }
1492
1493     #[test]
1494     fn drain_filter_test() {
1495         let mut m: LinkedList<u32> = LinkedList::new();
1496         m.extend(&[1, 2, 3, 4, 5, 6]);
1497         let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
1498
1499         check_links(&m);
1500
1501         assert_eq!(deleted, &[1, 2, 3]);
1502         assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
1503     }
1504
1505     #[test]
1506     fn drain_to_empty_test() {
1507         let mut m: LinkedList<u32> = LinkedList::new();
1508         m.extend(&[1, 2, 3, 4, 5, 6]);
1509         let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
1510
1511         check_links(&m);
1512
1513         assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
1514         assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
1515     }
1516 }