1 //! A doubly-linked list with owned nodes.
3 //! The `LinkedList` allows pushing and popping elements at either end
6 //! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
7 //! array-based containers are generally faster,
8 //! more memory efficient, and make better use of CPU cache.
10 //! [`Vec`]: ../../vec/struct.Vec.html
11 //! [`VecDeque`]: ../vec_deque/struct.VecDeque.html
13 #![stable(feature = "rust1", since = "1.0.0")]
15 use core::cmp::Ordering;
17 use core::hash::{Hash, Hasher};
18 use core::iter::{FromIterator, FusedIterator};
19 use core::marker::PhantomData;
21 use core::ptr::NonNull;
23 use super::SpecExtend;
24 use crate::boxed::Box;
29 /// A doubly-linked list with owned nodes.
31 /// The `LinkedList` allows pushing and popping elements at either end
34 /// NOTE: It is almost always better to use `Vec` or `VecDeque` because
35 /// array-based containers are generally faster,
36 /// more memory efficient, and make better use of CPU cache.
37 #[stable(feature = "rust1", since = "1.0.0")]
38 pub struct LinkedList<T> {
39 head: Option<NonNull<Node<T>>>,
40 tail: Option<NonNull<Node<T>>>,
42 marker: PhantomData<Box<Node<T>>>,
46 next: Option<NonNull<Node<T>>>,
47 prev: Option<NonNull<Node<T>>>,
51 /// An iterator over the elements of a `LinkedList`.
53 /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its
54 /// documentation for more.
56 /// [`iter`]: struct.LinkedList.html#method.iter
57 /// [`LinkedList`]: struct.LinkedList.html
58 #[stable(feature = "rust1", since = "1.0.0")]
59 pub struct Iter<'a, T: 'a> {
60 head: Option<NonNull<Node<T>>>,
61 tail: Option<NonNull<Node<T>>>,
63 marker: PhantomData<&'a Node<T>>,
66 #[stable(feature = "collection_debug", since = "1.17.0")]
67 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
68 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69 f.debug_tuple("Iter").field(&self.len).finish()
73 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
74 #[stable(feature = "rust1", since = "1.0.0")]
75 impl<T> Clone for Iter<'_, T> {
76 fn clone(&self) -> Self {
81 /// A mutable iterator over the elements of a `LinkedList`.
83 /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its
84 /// documentation for more.
86 /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut
87 /// [`LinkedList`]: struct.LinkedList.html
88 #[stable(feature = "rust1", since = "1.0.0")]
89 pub struct IterMut<'a, T: 'a> {
90 // We do *not* exclusively own the entire list here, references to node's `element`
91 // have been handed out by the iterator! So be careful when using this; the methods
92 // called must be aware that there can be aliasing pointers to `element`.
93 list: &'a mut LinkedList<T>,
94 head: Option<NonNull<Node<T>>>,
95 tail: Option<NonNull<Node<T>>>,
99 #[stable(feature = "collection_debug", since = "1.17.0")]
100 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
101 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
102 f.debug_tuple("IterMut").field(&self.list).field(&self.len).finish()
106 /// An owning iterator over the elements of a `LinkedList`.
108 /// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
109 /// (provided by the `IntoIterator` trait). See its documentation for more.
111 /// [`into_iter`]: struct.LinkedList.html#method.into_iter
112 /// [`LinkedList`]: struct.LinkedList.html
114 #[stable(feature = "rust1", since = "1.0.0")]
115 pub struct IntoIter<T> {
119 #[stable(feature = "collection_debug", since = "1.17.0")]
120 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
121 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122 f.debug_tuple("IntoIter").field(&self.list).finish()
127 fn new(element: T) -> Self {
128 Node { next: None, prev: None, element }
131 fn into_element(self: Box<Self>) -> T {
137 impl<T> LinkedList<T> {
138 /// Adds the given node to the front of the list.
140 fn push_front_node(&mut self, mut node: Box<Node<T>>) {
141 // This method takes care not to create mutable references to whole nodes,
142 // to maintain validity of aliasing pointers into `element`.
144 node.next = self.head;
146 let node = Some(Box::leak(node).into());
149 None => self.tail = node,
150 // Not creating new mutable (unique!) references overlapping `element`.
151 Some(head) => (*head.as_ptr()).prev = node,
159 /// Removes and returns the node at the front of the list.
161 fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
162 // This method takes care not to create mutable references to whole nodes,
163 // to maintain validity of aliasing pointers into `element`.
164 self.head.map(|node| unsafe {
165 let node = Box::from_raw(node.as_ptr());
166 self.head = node.next;
169 None => self.tail = None,
170 // Not creating new mutable (unique!) references overlapping `element`.
171 Some(head) => (*head.as_ptr()).prev = None,
179 /// Adds the given node to the back of the list.
181 fn push_back_node(&mut self, mut node: Box<Node<T>>) {
182 // This method takes care not to create mutable references to whole nodes,
183 // to maintain validity of aliasing pointers into `element`.
186 node.prev = self.tail;
187 let node = Some(Box::leak(node).into());
190 None => self.head = node,
191 // Not creating new mutable (unique!) references overlapping `element`.
192 Some(tail) => (*tail.as_ptr()).next = node,
200 /// Removes and returns the node at the back of the list.
202 fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
203 // This method takes care not to create mutable references to whole nodes,
204 // to maintain validity of aliasing pointers into `element`.
205 self.tail.map(|node| unsafe {
206 let node = Box::from_raw(node.as_ptr());
207 self.tail = node.prev;
210 None => self.head = None,
211 // Not creating new mutable (unique!) references overlapping `element`.
212 Some(tail) => (*tail.as_ptr()).next = None,
220 /// Unlinks the specified node from the current list.
222 /// Warning: this will not check that the provided node belongs to the current list.
224 /// This method takes care not to create mutable references to `element`, to
225 /// maintain validity of aliasing pointers.
227 unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
228 let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut.
230 // Not creating new mutable (unique!) references overlapping `element`.
232 Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
233 // this node is the head node
234 None => self.head = node.next,
238 Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
239 // this node is the tail node
240 None => self.tail = node.prev,
246 /// Splices a series of nodes between two existing nodes.
248 /// Warning: this will not check that the provided node belongs to the two existing lists.
250 unsafe fn splice_nodes(
252 existing_prev: Option<NonNull<Node<T>>>,
253 existing_next: Option<NonNull<Node<T>>>,
254 mut splice_start: NonNull<Node<T>>,
255 mut splice_end: NonNull<Node<T>>,
256 splice_length: usize,
258 // This method takes care not to create multiple mutable references to whole nodes at the same time,
259 // to maintain validity of aliasing pointers into `element`.
260 if let Some(mut existing_prev) = existing_prev {
262 existing_prev.as_mut().next = Some(splice_start);
265 self.head = Some(splice_start);
267 if let Some(mut existing_next) = existing_next {
269 existing_next.as_mut().prev = Some(splice_end);
272 self.tail = Some(splice_end);
275 splice_start.as_mut().prev = existing_prev;
276 splice_end.as_mut().next = existing_next;
279 self.len += splice_length;
282 /// Detaches all nodes from a linked list as a series of nodes.
284 fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
285 let head = self.head.take();
286 let tail = self.tail.take();
287 let len = mem::replace(&mut self.len, 0);
288 if let Some(head) = head {
289 let tail = tail.unwrap_or_else(|| unsafe { core::hint::unreachable_unchecked() });
290 Some((head, tail, len))
297 unsafe fn split_off_before_node(
299 split_node: Option<NonNull<Node<T>>>,
302 // The split node is the new head node of the second part
303 if let Some(mut split_node) = split_node {
307 first_part_tail = split_node.as_mut().prev.take();
309 if let Some(mut tail) = first_part_tail {
311 tail.as_mut().next = None;
313 first_part_head = self.head;
315 first_part_head = None;
318 let first_part = LinkedList {
319 head: first_part_head,
320 tail: first_part_tail,
325 // Fix the head ptr of the second part
326 self.head = Some(split_node);
327 self.len = self.len - at;
331 mem::replace(self, LinkedList::new())
336 unsafe fn split_off_after_node(
338 split_node: Option<NonNull<Node<T>>>,
341 // The split node is the new tail node of the first part and owns
342 // the head of the second part.
343 if let Some(mut split_node) = split_node {
344 let second_part_head;
345 let second_part_tail;
347 second_part_head = split_node.as_mut().next.take();
349 if let Some(mut head) = second_part_head {
351 head.as_mut().prev = None;
353 second_part_tail = self.tail;
355 second_part_tail = None;
358 let second_part = LinkedList {
359 head: second_part_head,
360 tail: second_part_tail,
365 // Fix the tail ptr of the first part
366 self.tail = Some(split_node);
371 mem::replace(self, LinkedList::new())
376 #[stable(feature = "rust1", since = "1.0.0")]
377 impl<T> Default for LinkedList<T> {
378 /// Creates an empty `LinkedList<T>`.
380 fn default() -> Self {
385 impl<T> LinkedList<T> {
386 /// Creates an empty `LinkedList`.
391 /// use std::collections::LinkedList;
393 /// let list: LinkedList<u32> = LinkedList::new();
396 #[rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0")]
397 #[stable(feature = "rust1", since = "1.0.0")]
398 pub const fn new() -> Self {
399 LinkedList { head: None, tail: None, len: 0, marker: PhantomData }
402 /// Moves all elements from `other` to the end of the list.
404 /// This reuses all the nodes from `other` and moves them into `self`. After
405 /// this operation, `other` becomes empty.
407 /// This operation should compute in *O*(1) time and *O*(1) memory.
412 /// use std::collections::LinkedList;
414 /// let mut list1 = LinkedList::new();
415 /// list1.push_back('a');
417 /// let mut list2 = LinkedList::new();
418 /// list2.push_back('b');
419 /// list2.push_back('c');
421 /// list1.append(&mut list2);
423 /// let mut iter = list1.iter();
424 /// assert_eq!(iter.next(), Some(&'a'));
425 /// assert_eq!(iter.next(), Some(&'b'));
426 /// assert_eq!(iter.next(), Some(&'c'));
427 /// assert!(iter.next().is_none());
429 /// assert!(list2.is_empty());
431 #[stable(feature = "rust1", since = "1.0.0")]
432 pub fn append(&mut self, other: &mut Self) {
434 None => mem::swap(self, other),
436 // `as_mut` is okay here because we have exclusive access to the entirety
438 if let Some(mut other_head) = other.head.take() {
440 tail.as_mut().next = Some(other_head);
441 other_head.as_mut().prev = Some(tail);
444 self.tail = other.tail.take();
445 self.len += mem::replace(&mut other.len, 0);
451 /// Moves all elements from `other` to the begin of the list.
452 #[unstable(feature = "linked_list_prepend", issue = "none")]
453 pub fn prepend(&mut self, other: &mut Self) {
455 None => mem::swap(self, other),
457 // `as_mut` is okay here because we have exclusive access to the entirety
459 if let Some(mut other_tail) = other.tail.take() {
461 head.as_mut().prev = Some(other_tail);
462 other_tail.as_mut().next = Some(head);
465 self.head = other.head.take();
466 self.len += mem::replace(&mut other.len, 0);
472 /// Provides a forward iterator.
477 /// use std::collections::LinkedList;
479 /// let mut list: LinkedList<u32> = LinkedList::new();
481 /// list.push_back(0);
482 /// list.push_back(1);
483 /// list.push_back(2);
485 /// let mut iter = list.iter();
486 /// assert_eq!(iter.next(), Some(&0));
487 /// assert_eq!(iter.next(), Some(&1));
488 /// assert_eq!(iter.next(), Some(&2));
489 /// assert_eq!(iter.next(), None);
492 #[stable(feature = "rust1", since = "1.0.0")]
493 pub fn iter(&self) -> Iter<'_, T> {
494 Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
497 /// Provides a forward iterator with mutable references.
502 /// use std::collections::LinkedList;
504 /// let mut list: LinkedList<u32> = LinkedList::new();
506 /// list.push_back(0);
507 /// list.push_back(1);
508 /// list.push_back(2);
510 /// for element in list.iter_mut() {
514 /// let mut iter = list.iter();
515 /// assert_eq!(iter.next(), Some(&10));
516 /// assert_eq!(iter.next(), Some(&11));
517 /// assert_eq!(iter.next(), Some(&12));
518 /// assert_eq!(iter.next(), None);
521 #[stable(feature = "rust1", since = "1.0.0")]
522 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
523 IterMut { head: self.head, tail: self.tail, len: self.len, list: self }
526 /// Provides a cursor at the front element.
528 /// The cursor is pointing to the "ghost" non-element if the list is empty.
530 #[unstable(feature = "linked_list_cursors", issue = "58533")]
531 pub fn cursor_front(&self) -> Cursor<'_, T> {
532 Cursor { index: 0, current: self.head, list: self }
535 /// Provides a cursor with editing operations at the front element.
537 /// The cursor is pointing to the "ghost" non-element if the list is empty.
539 #[unstable(feature = "linked_list_cursors", issue = "58533")]
540 pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
541 CursorMut { index: 0, current: self.head, list: self }
544 /// Provides a cursor at the back element.
546 /// The cursor is pointing to the "ghost" non-element if the list is empty.
548 #[unstable(feature = "linked_list_cursors", issue = "58533")]
549 pub fn cursor_back(&self) -> Cursor<'_, T> {
550 Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
553 /// Provides a cursor with editing operations at the back element.
555 /// The cursor is pointing to the "ghost" non-element if the list is empty.
557 #[unstable(feature = "linked_list_cursors", issue = "58533")]
558 pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
559 CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
562 /// Returns `true` if the `LinkedList` is empty.
564 /// This operation should compute in *O*(1) time.
569 /// use std::collections::LinkedList;
571 /// let mut dl = LinkedList::new();
572 /// assert!(dl.is_empty());
574 /// dl.push_front("foo");
575 /// assert!(!dl.is_empty());
578 #[stable(feature = "rust1", since = "1.0.0")]
579 pub fn is_empty(&self) -> bool {
583 /// Returns the length of the `LinkedList`.
585 /// This operation should compute in *O*(1) time.
590 /// use std::collections::LinkedList;
592 /// let mut dl = LinkedList::new();
594 /// dl.push_front(2);
595 /// assert_eq!(dl.len(), 1);
597 /// dl.push_front(1);
598 /// assert_eq!(dl.len(), 2);
601 /// assert_eq!(dl.len(), 3);
604 #[stable(feature = "rust1", since = "1.0.0")]
605 pub fn len(&self) -> usize {
609 /// Removes all elements from the `LinkedList`.
611 /// This operation should compute in *O*(*n*) time.
616 /// use std::collections::LinkedList;
618 /// let mut dl = LinkedList::new();
620 /// dl.push_front(2);
621 /// dl.push_front(1);
622 /// assert_eq!(dl.len(), 2);
623 /// assert_eq!(dl.front(), Some(&1));
626 /// assert_eq!(dl.len(), 0);
627 /// assert_eq!(dl.front(), None);
630 #[stable(feature = "rust1", since = "1.0.0")]
631 pub fn clear(&mut self) {
635 /// Returns `true` if the `LinkedList` contains an element equal to the
641 /// use std::collections::LinkedList;
643 /// let mut list: LinkedList<u32> = LinkedList::new();
645 /// list.push_back(0);
646 /// list.push_back(1);
647 /// list.push_back(2);
649 /// assert_eq!(list.contains(&0), true);
650 /// assert_eq!(list.contains(&10), false);
652 #[stable(feature = "linked_list_contains", since = "1.12.0")]
653 pub fn contains(&self, x: &T) -> bool
657 self.iter().any(|e| e == x)
660 /// Provides a reference to the front element, or `None` if the list is
666 /// use std::collections::LinkedList;
668 /// let mut dl = LinkedList::new();
669 /// assert_eq!(dl.front(), None);
671 /// dl.push_front(1);
672 /// assert_eq!(dl.front(), Some(&1));
675 #[stable(feature = "rust1", since = "1.0.0")]
676 pub fn front(&self) -> Option<&T> {
677 unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
680 /// Provides a mutable reference to the front element, or `None` if the list
686 /// use std::collections::LinkedList;
688 /// let mut dl = LinkedList::new();
689 /// assert_eq!(dl.front(), None);
691 /// dl.push_front(1);
692 /// assert_eq!(dl.front(), Some(&1));
694 /// match dl.front_mut() {
696 /// Some(x) => *x = 5,
698 /// assert_eq!(dl.front(), Some(&5));
701 #[stable(feature = "rust1", since = "1.0.0")]
702 pub fn front_mut(&mut self) -> Option<&mut T> {
703 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
706 /// Provides a reference to the back element, or `None` if the list is
712 /// use std::collections::LinkedList;
714 /// let mut dl = LinkedList::new();
715 /// assert_eq!(dl.back(), None);
718 /// assert_eq!(dl.back(), Some(&1));
721 #[stable(feature = "rust1", since = "1.0.0")]
722 pub fn back(&self) -> Option<&T> {
723 unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
726 /// Provides a mutable reference to the back element, or `None` if the list
732 /// use std::collections::LinkedList;
734 /// let mut dl = LinkedList::new();
735 /// assert_eq!(dl.back(), None);
738 /// assert_eq!(dl.back(), Some(&1));
740 /// match dl.back_mut() {
742 /// Some(x) => *x = 5,
744 /// assert_eq!(dl.back(), Some(&5));
747 #[stable(feature = "rust1", since = "1.0.0")]
748 pub fn back_mut(&mut self) -> Option<&mut T> {
749 unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
752 /// Adds an element first in the list.
754 /// This operation should compute in *O*(1) time.
759 /// use std::collections::LinkedList;
761 /// let mut dl = LinkedList::new();
763 /// dl.push_front(2);
764 /// assert_eq!(dl.front().unwrap(), &2);
766 /// dl.push_front(1);
767 /// assert_eq!(dl.front().unwrap(), &1);
769 #[stable(feature = "rust1", since = "1.0.0")]
770 pub fn push_front(&mut self, elt: T) {
771 self.push_front_node(box Node::new(elt));
774 /// Removes the first element and returns it, or `None` if the list is
777 /// This operation should compute in *O*(1) time.
782 /// use std::collections::LinkedList;
784 /// let mut d = LinkedList::new();
785 /// assert_eq!(d.pop_front(), None);
789 /// assert_eq!(d.pop_front(), Some(3));
790 /// assert_eq!(d.pop_front(), Some(1));
791 /// assert_eq!(d.pop_front(), None);
793 #[stable(feature = "rust1", since = "1.0.0")]
794 pub fn pop_front(&mut self) -> Option<T> {
795 self.pop_front_node().map(Node::into_element)
798 /// Appends an element to the back of a list.
800 /// This operation should compute in *O*(1) time.
805 /// use std::collections::LinkedList;
807 /// let mut d = LinkedList::new();
810 /// assert_eq!(3, *d.back().unwrap());
812 #[stable(feature = "rust1", since = "1.0.0")]
813 pub fn push_back(&mut self, elt: T) {
814 self.push_back_node(box Node::new(elt));
817 /// Removes the last element from a list and returns it, or `None` if
820 /// This operation should compute in *O*(1) time.
825 /// use std::collections::LinkedList;
827 /// let mut d = LinkedList::new();
828 /// assert_eq!(d.pop_back(), None);
831 /// assert_eq!(d.pop_back(), Some(3));
833 #[stable(feature = "rust1", since = "1.0.0")]
834 pub fn pop_back(&mut self) -> Option<T> {
835 self.pop_back_node().map(Node::into_element)
838 /// Splits the list into two at the given index. Returns everything after the given index,
839 /// including the index.
841 /// This operation should compute in *O*(*n*) time.
845 /// Panics if `at > len`.
850 /// use std::collections::LinkedList;
852 /// let mut d = LinkedList::new();
858 /// let mut split = d.split_off(2);
860 /// assert_eq!(split.pop_front(), Some(1));
861 /// assert_eq!(split.pop_front(), None);
863 #[stable(feature = "rust1", since = "1.0.0")]
864 pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
865 let len = self.len();
866 assert!(at <= len, "Cannot split off at a nonexistent index");
868 return mem::take(self);
869 } else if at == len {
873 // Below, we iterate towards the `i-1`th node, either from the start or the end,
874 // depending on which would be faster.
875 let split_node = if at - 1 <= len - 1 - (at - 1) {
876 let mut iter = self.iter_mut();
877 // instead of skipping using .skip() (which creates a new struct),
878 // we skip manually so we can access the head field without
879 // depending on implementation details of Skip
885 // better off starting from the end
886 let mut iter = self.iter_mut();
887 for _ in 0..len - 1 - (at - 1) {
892 unsafe { self.split_off_after_node(split_node, at) }
895 /// Removes the element at the given index and returns it.
897 /// This operation should compute in *O*(*n*) time.
900 /// Panics if at >= len
905 /// #![feature(linked_list_remove)]
906 /// use std::collections::LinkedList;
908 /// let mut d = LinkedList::new();
914 /// assert_eq!(d.remove(1), 2);
915 /// assert_eq!(d.remove(0), 3);
916 /// assert_eq!(d.remove(0), 1);
918 #[unstable(feature = "linked_list_remove", issue = "69210")]
919 pub fn remove(&mut self, at: usize) -> T {
920 let len = self.len();
921 assert!(at < len, "Cannot remove at an index outside of the list bounds");
923 // Below, we iterate towards the node at the given index, either from
924 // the start or the end, depending on which would be faster.
925 let offset_from_end = len - at - 1;
926 if at <= offset_from_end {
927 let mut cursor = self.cursor_front_mut();
931 cursor.remove_current().unwrap()
933 let mut cursor = self.cursor_back_mut();
934 for _ in 0..offset_from_end {
937 cursor.remove_current().unwrap()
941 /// Creates an iterator which uses a closure to determine if an element should be removed.
943 /// If the closure returns true, then the element is removed and yielded.
944 /// If the closure returns false, the element will remain in the list and will not be yielded
947 /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of
948 /// whether you choose to keep or remove it.
952 /// Splitting a list into evens and odds, reusing the original list:
955 /// #![feature(drain_filter)]
956 /// use std::collections::LinkedList;
958 /// let mut numbers: LinkedList<u32> = LinkedList::new();
959 /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
961 /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
962 /// let odds = numbers;
964 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
965 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
967 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
968 pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
970 F: FnMut(&mut T) -> bool,
972 // avoid borrow issues.
974 let old_len = self.len;
976 DrainFilter { list: self, it, pred: filter, idx: 0, old_len }
980 #[stable(feature = "rust1", since = "1.0.0")]
981 unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
983 struct DropGuard<'a, T>(&'a mut LinkedList<T>);
985 impl<'a, T> Drop for DropGuard<'a, T> {
987 // Continue the same loop we do below. This only runs when a destructor has
988 // panicked. If another one panics this will abort.
989 while self.0.pop_front_node().is_some() {}
993 while let Some(node) = self.pop_front_node() {
994 let guard = DropGuard(self);
1001 #[stable(feature = "rust1", since = "1.0.0")]
1002 impl<'a, T> Iterator for Iter<'a, T> {
1006 fn next(&mut self) -> Option<&'a T> {
1010 self.head.map(|node| unsafe {
1011 // Need an unbound lifetime to get 'a
1012 let node = &*node.as_ptr();
1014 self.head = node.next;
1021 fn size_hint(&self) -> (usize, Option<usize>) {
1022 (self.len, Some(self.len))
1026 fn last(mut self) -> Option<&'a T> {
1031 #[stable(feature = "rust1", since = "1.0.0")]
1032 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1034 fn next_back(&mut self) -> Option<&'a T> {
1038 self.tail.map(|node| unsafe {
1039 // Need an unbound lifetime to get 'a
1040 let node = &*node.as_ptr();
1042 self.tail = node.prev;
1049 #[stable(feature = "rust1", since = "1.0.0")]
1050 impl<T> ExactSizeIterator for Iter<'_, T> {}
1052 #[stable(feature = "fused", since = "1.26.0")]
1053 impl<T> FusedIterator for Iter<'_, T> {}
1055 #[stable(feature = "rust1", since = "1.0.0")]
1056 impl<'a, T> Iterator for IterMut<'a, T> {
1057 type Item = &'a mut T;
1060 fn next(&mut self) -> Option<&'a mut T> {
1064 self.head.map(|node| unsafe {
1065 // Need an unbound lifetime to get 'a
1066 let node = &mut *node.as_ptr();
1068 self.head = node.next;
1075 fn size_hint(&self) -> (usize, Option<usize>) {
1076 (self.len, Some(self.len))
1080 fn last(mut self) -> Option<&'a mut T> {
1085 #[stable(feature = "rust1", since = "1.0.0")]
1086 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1088 fn next_back(&mut self) -> Option<&'a mut T> {
1092 self.tail.map(|node| unsafe {
1093 // Need an unbound lifetime to get 'a
1094 let node = &mut *node.as_ptr();
1096 self.tail = node.prev;
1103 #[stable(feature = "rust1", since = "1.0.0")]
1104 impl<T> ExactSizeIterator for IterMut<'_, T> {}
1106 #[stable(feature = "fused", since = "1.26.0")]
1107 impl<T> FusedIterator for IterMut<'_, T> {}
1109 impl<T> IterMut<'_, T> {
1110 /// Inserts the given element just after the element most recently returned by `.next()`.
1111 /// The inserted element does not appear in the iteration.
1116 /// #![feature(linked_list_extras)]
1118 /// use std::collections::LinkedList;
1120 /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
1123 /// let mut it = list.iter_mut();
1124 /// assert_eq!(it.next().unwrap(), &1);
1125 /// // insert `2` after `1`
1126 /// it.insert_next(2);
1129 /// let vec: Vec<_> = list.into_iter().collect();
1130 /// assert_eq!(vec, [1, 2, 3, 4]);
1135 feature = "linked_list_extras",
1136 reason = "this is probably better handled by a cursor type -- we'll see",
1139 pub fn insert_next(&mut self, element: T) {
1141 // `push_back` is okay with aliasing `element` references
1142 None => self.list.push_back(element),
1143 Some(head) => unsafe {
1144 let prev = match head.as_ref().prev {
1145 // `push_front` is okay with aliasing nodes
1146 None => return self.list.push_front(element),
1151 Box::leak(box Node { next: Some(head), prev: Some(prev), element }).into(),
1154 // Not creating references to entire nodes to not invalidate the
1155 // reference to `element` we handed to the user.
1156 (*prev.as_ptr()).next = node;
1157 (*head.as_ptr()).prev = node;
1164 /// Provides a reference to the next element, without changing the iterator.
1169 /// #![feature(linked_list_extras)]
1171 /// use std::collections::LinkedList;
1173 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
1175 /// let mut it = list.iter_mut();
1176 /// assert_eq!(it.next().unwrap(), &1);
1177 /// assert_eq!(it.peek_next().unwrap(), &2);
1178 /// // We just peeked at 2, so it was not consumed from the iterator.
1179 /// assert_eq!(it.next().unwrap(), &2);
1183 feature = "linked_list_extras",
1184 reason = "this is probably better handled by a cursor type -- we'll see",
1187 pub fn peek_next(&mut self) -> Option<&mut T> {
1191 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
1196 /// A cursor over a `LinkedList`.
1198 /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
1200 /// Cursors always rest between two elements in the list, and index in a logically circular way.
1201 /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1202 /// tail of the list.
1204 /// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
1205 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1206 pub struct Cursor<'a, T: 'a> {
1208 current: Option<NonNull<Node<T>>>,
1209 list: &'a LinkedList<T>,
1212 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1213 impl<T> Clone for Cursor<'_, T> {
1214 fn clone(&self) -> Self {
1215 let Cursor { index, current, list } = *self;
1216 Cursor { index, current, list }
1220 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1221 impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> {
1222 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1223 f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
1227 /// A cursor over a `LinkedList` with editing operations.
1229 /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
1230 /// safely mutate the list during iteration. This is because the lifetime of its yielded
1231 /// references is tied to its own lifetime, instead of just the underlying list. This means
1232 /// cursors cannot yield multiple elements at once.
1234 /// Cursors always rest between two elements in the list, and index in a logically circular way.
1235 /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1236 /// tail of the list.
1237 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1238 pub struct CursorMut<'a, T: 'a> {
1240 current: Option<NonNull<Node<T>>>,
1241 list: &'a mut LinkedList<T>,
1244 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1245 impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> {
1246 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1247 f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
1251 impl<'a, T> Cursor<'a, T> {
1252 /// Returns the cursor position index within the `LinkedList`.
1254 /// This returns `None` if the cursor is currently pointing to the
1255 /// "ghost" non-element.
1256 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1257 pub fn index(&self) -> Option<usize> {
1258 let _ = self.current?;
1262 /// Moves the cursor to the next element of the `LinkedList`.
1264 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1265 /// the first element of the `LinkedList`. If it is pointing to the last
1266 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1267 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1268 pub fn move_next(&mut self) {
1269 match self.current.take() {
1270 // We had no current element; the cursor was sitting at the start position
1271 // Next element should be the head of the list
1273 self.current = self.list.head;
1276 // We had a previous element, so let's go to its next
1277 Some(current) => unsafe {
1278 self.current = current.as_ref().next;
1284 /// Moves the cursor to the previous element of the `LinkedList`.
1286 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1287 /// the last element of the `LinkedList`. If it is pointing to the first
1288 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1289 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1290 pub fn move_prev(&mut self) {
1291 match self.current.take() {
1292 // No current. We're at the start of the list. Yield None and jump to the end.
1294 self.current = self.list.tail;
1295 self.index = self.list.len().checked_sub(1).unwrap_or(0);
1297 // Have a prev. Yield it and go to the previous element.
1298 Some(current) => unsafe {
1299 self.current = current.as_ref().prev;
1300 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1305 /// Returns a reference to the element that the cursor is currently
1308 /// This returns `None` if the cursor is currently pointing to the
1309 /// "ghost" non-element.
1310 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1311 pub fn current(&self) -> Option<&'a T> {
1312 unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
1315 /// Returns a reference to the next element.
1317 /// If the cursor is pointing to the "ghost" non-element then this returns
1318 /// the first element of the `LinkedList`. If it is pointing to the last
1319 /// element of the `LinkedList` then this returns `None`.
1320 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1321 pub fn peek_next(&self) -> Option<&'a T> {
1323 let next = match self.current {
1324 None => self.list.head,
1325 Some(current) => current.as_ref().next,
1327 next.map(|next| &(*next.as_ptr()).element)
1331 /// Returns a reference to the previous element.
1333 /// If the cursor is pointing to the "ghost" non-element then this returns
1334 /// the last element of the `LinkedList`. If it is pointing to the first
1335 /// element of the `LinkedList` then this returns `None`.
1336 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1337 pub fn peek_prev(&self) -> Option<&'a T> {
1339 let prev = match self.current {
1340 None => self.list.tail,
1341 Some(current) => current.as_ref().prev,
1343 prev.map(|prev| &(*prev.as_ptr()).element)
1348 impl<'a, T> CursorMut<'a, T> {
1349 /// Returns the cursor position index within the `LinkedList`.
1351 /// This returns `None` if the cursor is currently pointing to the
1352 /// "ghost" non-element.
1353 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1354 pub fn index(&self) -> Option<usize> {
1355 let _ = self.current?;
1359 /// Moves the cursor to the next element of the `LinkedList`.
1361 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1362 /// the first element of the `LinkedList`. If it is pointing to the last
1363 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1364 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1365 pub fn move_next(&mut self) {
1366 match self.current.take() {
1367 // We had no current element; the cursor was sitting at the start position
1368 // Next element should be the head of the list
1370 self.current = self.list.head;
1373 // We had a previous element, so let's go to its next
1374 Some(current) => unsafe {
1375 self.current = current.as_ref().next;
1381 /// Moves the cursor to the previous element of the `LinkedList`.
1383 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1384 /// the last element of the `LinkedList`. If it is pointing to the first
1385 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1386 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1387 pub fn move_prev(&mut self) {
1388 match self.current.take() {
1389 // No current. We're at the start of the list. Yield None and jump to the end.
1391 self.current = self.list.tail;
1392 self.index = self.list.len().checked_sub(1).unwrap_or(0);
1394 // Have a prev. Yield it and go to the previous element.
1395 Some(current) => unsafe {
1396 self.current = current.as_ref().prev;
1397 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1402 /// Returns a reference to the element that the cursor is currently
1405 /// This returns `None` if the cursor is currently pointing to the
1406 /// "ghost" non-element.
1407 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1408 pub fn current(&mut self) -> Option<&mut T> {
1409 unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
1412 /// Returns a reference to the next element.
1414 /// If the cursor is pointing to the "ghost" non-element then this returns
1415 /// the first element of the `LinkedList`. If it is pointing to the last
1416 /// element of the `LinkedList` then this returns `None`.
1417 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1418 pub fn peek_next(&mut self) -> Option<&mut T> {
1420 let next = match self.current {
1421 None => self.list.head,
1422 Some(current) => current.as_ref().next,
1424 next.map(|next| &mut (*next.as_ptr()).element)
1428 /// Returns a reference to the previous element.
1430 /// If the cursor is pointing to the "ghost" non-element then this returns
1431 /// the last element of the `LinkedList`. If it is pointing to the first
1432 /// element of the `LinkedList` then this returns `None`.
1433 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1434 pub fn peek_prev(&mut self) -> Option<&mut T> {
1436 let prev = match self.current {
1437 None => self.list.tail,
1438 Some(current) => current.as_ref().prev,
1440 prev.map(|prev| &mut (*prev.as_ptr()).element)
1444 /// Returns a read-only cursor pointing to the current element.
1446 /// The lifetime of the returned `Cursor` is bound to that of the
1447 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1448 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
1449 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1450 pub fn as_cursor(&self) -> Cursor<'_, T> {
1451 Cursor { list: self.list, current: self.current, index: self.index }
1455 // Now the list editing operations
1457 impl<'a, T> CursorMut<'a, T> {
1458 /// Inserts a new element into the `LinkedList` after the current one.
1460 /// If the cursor is pointing at the "ghost" non-element then the new element is
1461 /// inserted at the front of the `LinkedList`.
1462 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1463 pub fn insert_after(&mut self, item: T) {
1465 let spliced_node = Box::leak(Box::new(Node::new(item))).into();
1466 let node_next = match self.current {
1467 None => self.list.head,
1468 Some(node) => node.as_ref().next,
1470 self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
1471 if self.current.is_none() {
1472 // The "ghost" non-element's index has changed.
1473 self.index = self.list.len;
1478 /// Inserts a new element into the `LinkedList` before the current one.
1480 /// If the cursor is pointing at the "ghost" non-element then the new element is
1481 /// inserted at the end of the `LinkedList`.
1482 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1483 pub fn insert_before(&mut self, item: T) {
1485 let spliced_node = Box::leak(Box::new(Node::new(item))).into();
1486 let node_prev = match self.current {
1487 None => self.list.tail,
1488 Some(node) => node.as_ref().prev,
1490 self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
1495 /// Removes the current element from the `LinkedList`.
1497 /// The element that was removed is returned, and the cursor is
1498 /// moved to point to the next element in the `LinkedList`.
1500 /// If the cursor is currently pointing to the "ghost" non-element then no element
1501 /// is removed and `None` is returned.
1502 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1503 pub fn remove_current(&mut self) -> Option<T> {
1504 let unlinked_node = self.current?;
1506 self.current = unlinked_node.as_ref().next;
1507 self.list.unlink_node(unlinked_node);
1508 let unlinked_node = Box::from_raw(unlinked_node.as_ptr());
1509 Some(unlinked_node.element)
1513 /// Removes the current element from the `LinkedList` without deallocating the list node.
1515 /// The node that was removed is returned as a new `LinkedList` containing only this node.
1516 /// The cursor is moved to point to the next element in the current `LinkedList`.
1518 /// If the cursor is currently pointing to the "ghost" non-element then no element
1519 /// is removed and `None` is returned.
1520 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1521 pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T>> {
1522 let mut unlinked_node = self.current?;
1524 self.current = unlinked_node.as_ref().next;
1525 self.list.unlink_node(unlinked_node);
1527 unlinked_node.as_mut().prev = None;
1528 unlinked_node.as_mut().next = None;
1530 head: Some(unlinked_node),
1531 tail: Some(unlinked_node),
1533 marker: PhantomData,
1538 /// Inserts the elements from the given `LinkedList` after the current one.
1540 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1541 /// inserted at the start of the `LinkedList`.
1542 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1543 pub fn splice_after(&mut self, list: LinkedList<T>) {
1545 let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1546 Some(parts) => parts,
1549 let node_next = match self.current {
1550 None => self.list.head,
1551 Some(node) => node.as_ref().next,
1553 self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
1554 if self.current.is_none() {
1555 // The "ghost" non-element's index has changed.
1556 self.index = self.list.len;
1561 /// Inserts the elements from the given `LinkedList` before the current one.
1563 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1564 /// inserted at the end of the `LinkedList`.
1565 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1566 pub fn splice_before(&mut self, list: LinkedList<T>) {
1568 let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1569 Some(parts) => parts,
1572 let node_prev = match self.current {
1573 None => self.list.tail,
1574 Some(node) => node.as_ref().prev,
1576 self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
1577 self.index += splice_len;
1581 /// Splits the list into two after the current element. This will return a
1582 /// new list consisting of everything after the cursor, with the original
1583 /// list retaining everything before.
1585 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1586 /// of the `LinkedList` are moved.
1587 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1588 pub fn split_after(&mut self) -> LinkedList<T> {
1589 let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
1590 if self.index == self.list.len {
1591 // The "ghost" non-element's index has changed to 0.
1594 unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
1597 /// Splits the list into two before the current element. This will return a
1598 /// new list consisting of everything before the cursor, with the original
1599 /// list retaining everything after.
1601 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1602 /// of the `LinkedList` are moved.
1603 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1604 pub fn split_before(&mut self) -> LinkedList<T> {
1605 let split_off_idx = self.index;
1607 unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
1611 /// An iterator produced by calling `drain_filter` on LinkedList.
1612 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1613 pub struct DrainFilter<'a, T: 'a, F: 'a>
1615 F: FnMut(&mut T) -> bool,
1617 list: &'a mut LinkedList<T>,
1618 it: Option<NonNull<Node<T>>>,
1624 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1625 impl<T, F> Iterator for DrainFilter<'_, T, F>
1627 F: FnMut(&mut T) -> bool,
1631 fn next(&mut self) -> Option<T> {
1632 while let Some(mut node) = self.it {
1634 self.it = node.as_ref().next;
1637 if (self.pred)(&mut node.as_mut().element) {
1638 // `unlink_node` is okay with aliasing `element` references.
1639 self.list.unlink_node(node);
1640 return Some(Box::from_raw(node.as_ptr()).element);
1648 fn size_hint(&self) -> (usize, Option<usize>) {
1649 (0, Some(self.old_len - self.idx))
1653 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1654 impl<T, F> Drop for DrainFilter<'_, T, F>
1656 F: FnMut(&mut T) -> bool,
1658 fn drop(&mut self) {
1659 struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>)
1661 F: FnMut(&mut T) -> bool;
1663 impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F>
1665 F: FnMut(&mut T) -> bool,
1667 fn drop(&mut self) {
1668 self.0.for_each(drop);
1672 while let Some(item) = self.next() {
1673 let guard = DropGuard(self);
1680 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1681 impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
1683 F: FnMut(&mut T) -> bool,
1685 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1686 f.debug_tuple("DrainFilter").field(&self.list).finish()
1690 #[stable(feature = "rust1", since = "1.0.0")]
1691 impl<T> Iterator for IntoIter<T> {
1695 fn next(&mut self) -> Option<T> {
1696 self.list.pop_front()
1700 fn size_hint(&self) -> (usize, Option<usize>) {
1701 (self.list.len, Some(self.list.len))
1705 #[stable(feature = "rust1", since = "1.0.0")]
1706 impl<T> DoubleEndedIterator for IntoIter<T> {
1708 fn next_back(&mut self) -> Option<T> {
1709 self.list.pop_back()
1713 #[stable(feature = "rust1", since = "1.0.0")]
1714 impl<T> ExactSizeIterator for IntoIter<T> {}
1716 #[stable(feature = "fused", since = "1.26.0")]
1717 impl<T> FusedIterator for IntoIter<T> {}
1719 #[stable(feature = "rust1", since = "1.0.0")]
1720 impl<T> FromIterator<T> for LinkedList<T> {
1721 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1722 let mut list = Self::new();
1728 #[stable(feature = "rust1", since = "1.0.0")]
1729 impl<T> IntoIterator for LinkedList<T> {
1731 type IntoIter = IntoIter<T>;
1733 /// Consumes the list into an iterator yielding elements by value.
1735 fn into_iter(self) -> IntoIter<T> {
1736 IntoIter { list: self }
1740 #[stable(feature = "rust1", since = "1.0.0")]
1741 impl<'a, T> IntoIterator for &'a LinkedList<T> {
1743 type IntoIter = Iter<'a, T>;
1745 fn into_iter(self) -> Iter<'a, T> {
1750 #[stable(feature = "rust1", since = "1.0.0")]
1751 impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
1752 type Item = &'a mut T;
1753 type IntoIter = IterMut<'a, T>;
1755 fn into_iter(self) -> IterMut<'a, T> {
1760 #[stable(feature = "rust1", since = "1.0.0")]
1761 impl<T> Extend<T> for LinkedList<T> {
1762 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1763 <Self as SpecExtend<I>>::spec_extend(self, iter);
1767 fn extend_one(&mut self, elem: T) {
1768 self.push_back(elem);
1772 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
1773 default fn spec_extend(&mut self, iter: I) {
1774 iter.into_iter().for_each(move |elt| self.push_back(elt));
1778 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
1779 fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
1784 #[stable(feature = "extend_ref", since = "1.2.0")]
1785 impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
1786 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1787 self.extend(iter.into_iter().cloned());
1791 fn extend_one(&mut self, &elem: &'a T) {
1792 self.push_back(elem);
1796 #[stable(feature = "rust1", since = "1.0.0")]
1797 impl<T: PartialEq> PartialEq for LinkedList<T> {
1798 fn eq(&self, other: &Self) -> bool {
1799 self.len() == other.len() && self.iter().eq(other)
1802 fn ne(&self, other: &Self) -> bool {
1803 self.len() != other.len() || self.iter().ne(other)
1807 #[stable(feature = "rust1", since = "1.0.0")]
1808 impl<T: Eq> Eq for LinkedList<T> {}
1810 #[stable(feature = "rust1", since = "1.0.0")]
1811 impl<T: PartialOrd> PartialOrd for LinkedList<T> {
1812 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1813 self.iter().partial_cmp(other)
1817 #[stable(feature = "rust1", since = "1.0.0")]
1818 impl<T: Ord> Ord for LinkedList<T> {
1820 fn cmp(&self, other: &Self) -> Ordering {
1821 self.iter().cmp(other)
1825 #[stable(feature = "rust1", since = "1.0.0")]
1826 impl<T: Clone> Clone for LinkedList<T> {
1827 fn clone(&self) -> Self {
1828 self.iter().cloned().collect()
1831 fn clone_from(&mut self, other: &Self) {
1832 let mut iter_other = other.iter();
1833 if self.len() > other.len() {
1834 self.split_off(other.len());
1836 for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
1837 elem.clone_from(elem_other);
1839 if !iter_other.is_empty() {
1840 self.extend(iter_other.cloned());
1845 #[stable(feature = "rust1", since = "1.0.0")]
1846 impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
1847 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1848 f.debug_list().entries(self).finish()
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 impl<T: Hash> Hash for LinkedList<T> {
1854 fn hash<H: Hasher>(&self, state: &mut H) {
1855 self.len().hash(state);
1862 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1864 fn assert_covariance() {
1865 fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
1868 fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
1871 fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
1876 #[stable(feature = "rust1", since = "1.0.0")]
1877 unsafe impl<T: Send> Send for LinkedList<T> {}
1879 #[stable(feature = "rust1", since = "1.0.0")]
1880 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1882 #[stable(feature = "rust1", since = "1.0.0")]
1883 unsafe impl<T: Sync> Send for Iter<'_, T> {}
1885 #[stable(feature = "rust1", since = "1.0.0")]
1886 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
1888 #[stable(feature = "rust1", since = "1.0.0")]
1889 unsafe impl<T: Send> Send for IterMut<'_, T> {}
1891 #[stable(feature = "rust1", since = "1.0.0")]
1892 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
1894 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1895 unsafe impl<T: Sync> Send for Cursor<'_, T> {}
1897 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1898 unsafe impl<T: Sync> Sync for Cursor<'_, T> {}
1900 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1901 unsafe impl<T: Send> Send for CursorMut<'_, T> {}
1903 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1904 unsafe impl<T: Sync> Sync for CursorMut<'_, T> {}