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