src/libcollections/linked_list.rs

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