1//! A doubly-linked list with owned nodes.
2//!
3//! The `LinkedList` allows pushing and popping elements at either end
4//! in constant time.
5//!
6//! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
7//! array-based containers are generally faster,
8//! more memory efficient, and make better use of CPU cache.
9//!
10//! [`Vec`]: crate::vec::Vec
11//! [`VecDeque`]: super::vec_deque::VecDeque
12
13#![stable(feature = "rust1", since = "1.0.0")]
14
15use core::cmp::Ordering;
16use core::hash::{Hash, Hasher};
17use core::iter::FusedIterator;
18use core::marker::PhantomData;
19use core::ptr::NonNull;
20use core::{fmt, mem};
21
22use super::SpecExtend;
23use crate::alloc::{Allocator, Global};
24use crate::boxed::Box;
25
26#[cfg(test)]
27mod tests;
28
29/// A doubly-linked list with owned nodes.
30///
31/// The `LinkedList` allows pushing and popping elements at either end
32/// in constant time.
33///
34/// A `LinkedList` with a known list of items can be initialized from an array:
35/// ```
36/// use std::collections::LinkedList;
37///
38/// let list = LinkedList::from([1, 2, 3]);
39/// ```
40///
41/// NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
42/// array-based containers are generally faster,
43/// more memory efficient, and make better use of CPU cache.
44///
45/// [`Vec`]: crate::vec::Vec
46/// [`VecDeque`]: super::vec_deque::VecDeque
47#[stable(feature = "rust1", since = "1.0.0")]
48#[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")]
49#[rustc_insignificant_dtor]
50pub struct LinkedList<
51 T,
52 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
53> {
54 head: Option<NonNull<Node<T>>>,
55 tail: Option<NonNull<Node<T>>>,
56 len: usize,
57 alloc: A,
58 marker: PhantomData<Box<Node<T>, A>>,
59}
60
61struct Node<T> {
62 next: Option<NonNull<Node<T>>>,
63 prev: Option<NonNull<Node<T>>>,
64 element: T,
65}
66
67/// An iterator over the elements of a `LinkedList`.
68///
69/// This `struct` is created by [`LinkedList::iter()`]. See its
70/// documentation for more.
71#[must_use = "iterators are lazy and do nothing unless consumed"]
72#[stable(feature = "rust1", since = "1.0.0")]
73pub struct Iter<'a, T: 'a> {
74 head: Option<NonNull<Node<T>>>,
75 tail: Option<NonNull<Node<T>>>,
76 len: usize,
77 marker: PhantomData<&'a Node<T>>,
78}
79
80#[stable(feature = "collection_debug", since = "1.17.0")]
81impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
82 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
83 f.debug_tuple("Iter")
84 .field(&*mem::ManuallyDrop::new(LinkedList {
85 head: self.head,
86 tail: self.tail,
87 len: self.len,
88 alloc: Global,
89 marker: PhantomData,
90 }))
91 .field(&self.len)
92 .finish()
93 }
94}
95
96// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
97#[stable(feature = "rust1", since = "1.0.0")]
98impl<T> Clone for Iter<'_, T> {
99 fn clone(&self) -> Self {
100 Iter { ..*self }
101 }
102}
103
104/// A mutable iterator over the elements of a `LinkedList`.
105///
106/// This `struct` is created by [`LinkedList::iter_mut()`]. See its
107/// documentation for more.
108#[must_use = "iterators are lazy and do nothing unless consumed"]
109#[stable(feature = "rust1", since = "1.0.0")]
110pub struct IterMut<'a, T: 'a> {
111 head: Option<NonNull<Node<T>>>,
112 tail: Option<NonNull<Node<T>>>,
113 len: usize,
114 marker: PhantomData<&'a mut Node<T>>,
115}
116
117#[stable(feature = "collection_debug", since = "1.17.0")]
118impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
119 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
120 f.debug_tuple("IterMut")
121 .field(&*mem::ManuallyDrop::new(LinkedList {
122 head: self.head,
123 tail: self.tail,
124 len: self.len,
125 alloc: Global,
126 marker: PhantomData,
127 }))
128 .field(&self.len)
129 .finish()
130 }
131}
132
133/// An owning iterator over the elements of a `LinkedList`.
134///
135/// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
136/// (provided by the [`IntoIterator`] trait). See its documentation for more.
137///
138/// [`into_iter`]: LinkedList::into_iter
139#[derive(Clone)]
140#[stable(feature = "rust1", since = "1.0.0")]
141pub struct IntoIter<
142 T,
143 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
144> {
145 list: LinkedList<T, A>,
146}
147
148#[stable(feature = "collection_debug", since = "1.17.0")]
149impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
150 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
151 f.debug_tuple("IntoIter").field(&self.list).finish()
152 }
153}
154
155impl<T> Node<T> {
156 fn new(element: T) -> Self {
157 Node { next: None, prev: None, element }
158 }
159
160 fn into_element<A: Allocator>(self: Box<Self, A>) -> T {
161 self.element
162 }
163}
164
165// private methods
166impl<T, A: Allocator> LinkedList<T, A> {
167 /// Adds the given node to the front of the list.
168 ///
169 /// # Safety
170 /// `node` must point to a valid node in the list's allocator.
171 /// This method takes ownership of the node, so the pointer should not be used again.
172 #[inline]
173 unsafe fn push_front_node(&mut self, node: NonNull<Node<T>>) {
174 // This method takes care not to create mutable references to whole nodes,
175 // to maintain validity of aliasing pointers into `element`.
176 unsafe {
177 (*node.as_ptr()).next = self.head;
178 (*node.as_ptr()).prev = None;
179 let node = Some(node);
180
181 match self.head {
182 None => self.tail = node,
183 // Not creating new mutable (unique!) references overlapping `element`.
184 Some(head) => (*head.as_ptr()).prev = node,
185 }
186
187 self.head = node;
188 self.len += 1;
189 }
190 }
191
192 /// Removes and returns the node at the front of the list.
193 #[inline]
194 fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>> {
195 // This method takes care not to create mutable references to whole nodes,
196 // to maintain validity of aliasing pointers into `element`.
197 self.head.map(|node| unsafe {
198 let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
199 self.head = node.next;
200
201 match self.head {
202 None => self.tail = None,
203 // Not creating new mutable (unique!) references overlapping `element`.
204 Some(head) => (*head.as_ptr()).prev = None,
205 }
206
207 self.len -= 1;
208 node
209 })
210 }
211
212 /// Adds the given node to the back of the list.
213 ///
214 /// # Safety
215 /// `node` must point to a valid node in the list's allocator.
216 /// This method takes ownership of the node, so the pointer should not be used again.
217 #[inline]
218 unsafe fn push_back_node(&mut self, node: NonNull<Node<T>>) {
219 // This method takes care not to create mutable references to whole nodes,
220 // to maintain validity of aliasing pointers into `element`.
221 unsafe {
222 (*node.as_ptr()).next = None;
223 (*node.as_ptr()).prev = self.tail;
224 let node = Some(node);
225
226 match self.tail {
227 None => self.head = node,
228 // Not creating new mutable (unique!) references overlapping `element`.
229 Some(tail) => (*tail.as_ptr()).next = node,
230 }
231
232 self.tail = node;
233 self.len += 1;
234 }
235 }
236
237 /// Removes and returns the node at the back of the list.
238 #[inline]
239 fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>> {
240 // This method takes care not to create mutable references to whole nodes,
241 // to maintain validity of aliasing pointers into `element`.
242 self.tail.map(|node| unsafe {
243 let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
244 self.tail = node.prev;
245
246 match self.tail {
247 None => self.head = None,
248 // Not creating new mutable (unique!) references overlapping `element`.
249 Some(tail) => (*tail.as_ptr()).next = None,
250 }
251
252 self.len -= 1;
253 node
254 })
255 }
256
257 /// Unlinks the specified node from the current list.
258 ///
259 /// Warning: this will not check that the provided node belongs to the current list.
260 ///
261 /// This method takes care not to create mutable references to `element`, to
262 /// maintain validity of aliasing pointers.
263 #[inline]
264 unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
265 let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut.
266
267 // Not creating new mutable (unique!) references overlapping `element`.
268 match node.prev {
269 Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
270 // this node is the head node
271 None => self.head = node.next,
272 };
273
274 match node.next {
275 Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
276 // this node is the tail node
277 None => self.tail = node.prev,
278 };
279
280 self.len -= 1;
281 }
282
283 /// Splices a series of nodes between two existing nodes.
284 ///
285 /// Warning: this will not check that the provided node belongs to the two existing lists.
286 #[inline]
287 unsafe fn splice_nodes(
288 &mut self,
289 existing_prev: Option<NonNull<Node<T>>>,
290 existing_next: Option<NonNull<Node<T>>>,
291 mut splice_start: NonNull<Node<T>>,
292 mut splice_end: NonNull<Node<T>>,
293 splice_length: usize,
294 ) {
295 // This method takes care not to create multiple mutable references to whole nodes at the same time,
296 // to maintain validity of aliasing pointers into `element`.
297 if let Some(mut existing_prev) = existing_prev {
298 unsafe {
299 existing_prev.as_mut().next = Some(splice_start);
300 }
301 } else {
302 self.head = Some(splice_start);
303 }
304 if let Some(mut existing_next) = existing_next {
305 unsafe {
306 existing_next.as_mut().prev = Some(splice_end);
307 }
308 } else {
309 self.tail = Some(splice_end);
310 }
311 unsafe {
312 splice_start.as_mut().prev = existing_prev;
313 splice_end.as_mut().next = existing_next;
314 }
315
316 self.len += splice_length;
317 }
318
319 /// Detaches all nodes from a linked list as a series of nodes.
320 #[inline]
321 fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
322 let head = self.head.take();
323 let tail = self.tail.take();
324 let len = mem::replace(&mut self.len, 0);
325 if let Some(head) = head {
326 // SAFETY: In a LinkedList, either both the head and tail are None because
327 // the list is empty, or both head and tail are Some because the list is populated.
328 // Since we have verified the head is Some, we are sure the tail is Some too.
329 let tail = unsafe { tail.unwrap_unchecked() };
330 Some((head, tail, len))
331 } else {
332 None
333 }
334 }
335
336 #[inline]
337 unsafe fn split_off_before_node(
338 &mut self,
339 split_node: Option<NonNull<Node<T>>>,
340 at: usize,
341 ) -> Self
342 where
343 A: Clone,
344 {
345 // The split node is the new head node of the second part
346 if let Some(mut split_node) = split_node {
347 let first_part_head;
348 let first_part_tail;
349 unsafe {
350 first_part_tail = split_node.as_mut().prev.take();
351 }
352 if let Some(mut tail) = first_part_tail {
353 unsafe {
354 tail.as_mut().next = None;
355 }
356 first_part_head = self.head;
357 } else {
358 first_part_head = None;
359 }
360
361 let first_part = LinkedList {
362 head: first_part_head,
363 tail: first_part_tail,
364 len: at,
365 alloc: self.alloc.clone(),
366 marker: PhantomData,
367 };
368
369 // Fix the head ptr of the second part
370 self.head = Some(split_node);
371 self.len = self.len - at;
372
373 first_part
374 } else {
375 mem::replace(self, LinkedList::new_in(self.alloc.clone()))
376 }
377 }
378
379 #[inline]
380 unsafe fn split_off_after_node(
381 &mut self,
382 split_node: Option<NonNull<Node<T>>>,
383 at: usize,
384 ) -> Self
385 where
386 A: Clone,
387 {
388 // The split node is the new tail node of the first part and owns
389 // the head of the second part.
390 if let Some(mut split_node) = split_node {
391 let second_part_head;
392 let second_part_tail;
393 unsafe {
394 second_part_head = split_node.as_mut().next.take();
395 }
396 if let Some(mut head) = second_part_head {
397 unsafe {
398 head.as_mut().prev = None;
399 }
400 second_part_tail = self.tail;
401 } else {
402 second_part_tail = None;
403 }
404
405 let second_part = LinkedList {
406 head: second_part_head,
407 tail: second_part_tail,
408 len: self.len - at,
409 alloc: self.alloc.clone(),
410 marker: PhantomData,
411 };
412
413 // Fix the tail ptr of the first part
414 self.tail = Some(split_node);
415 self.len = at;
416
417 second_part
418 } else {
419 mem::replace(self, LinkedList::new_in(self.alloc.clone()))
420 }
421 }
422}
423
424#[stable(feature = "rust1", since = "1.0.0")]
425impl<T> Default for LinkedList<T> {
426 /// Creates an empty `LinkedList<T>`.
427 #[inline]
428 fn default() -> Self {
429 Self::new()
430 }
431}
432
433impl<T> LinkedList<T> {
434 /// Creates an empty `LinkedList`.
435 ///
436 /// # Examples
437 ///
438 /// ```
439 /// use std::collections::LinkedList;
440 ///
441 /// let list: LinkedList<u32> = LinkedList::new();
442 /// ```
443 #[inline]
444 #[rustc_const_stable(feature = "const_linked_list_new", since = "1.39.0")]
445 #[stable(feature = "rust1", since = "1.0.0")]
446 #[must_use]
447 pub const fn new() -> Self {
448 LinkedList { head: None, tail: None, len: 0, alloc: Global, marker: PhantomData }
449 }
450
451 /// Moves all elements from `other` to the end of the list.
452 ///
453 /// This reuses all the nodes from `other` and moves them into `self`. After
454 /// this operation, `other` becomes empty.
455 ///
456 /// This operation should compute in *O*(1) time and *O*(1) memory.
457 ///
458 /// # Examples
459 ///
460 /// ```
461 /// use std::collections::LinkedList;
462 ///
463 /// let mut list1 = LinkedList::new();
464 /// list1.push_back('a');
465 ///
466 /// let mut list2 = LinkedList::new();
467 /// list2.push_back('b');
468 /// list2.push_back('c');
469 ///
470 /// list1.append(&mut list2);
471 ///
472 /// let mut iter = list1.iter();
473 /// assert_eq!(iter.next(), Some(&'a'));
474 /// assert_eq!(iter.next(), Some(&'b'));
475 /// assert_eq!(iter.next(), Some(&'c'));
476 /// assert!(iter.next().is_none());
477 ///
478 /// assert!(list2.is_empty());
479 /// ```
480 #[stable(feature = "rust1", since = "1.0.0")]
481 pub fn append(&mut self, other: &mut Self) {
482 match self.tail {
483 None => mem::swap(self, other),
484 Some(mut tail) => {
485 // `as_mut` is okay here because we have exclusive access to the entirety
486 // of both lists.
487 if let Some(mut other_head) = other.head.take() {
488 unsafe {
489 tail.as_mut().next = Some(other_head);
490 other_head.as_mut().prev = Some(tail);
491 }
492
493 self.tail = other.tail.take();
494 self.len += mem::replace(&mut other.len, 0);
495 }
496 }
497 }
498 }
499}
500
501impl<T, A: Allocator> LinkedList<T, A> {
502 /// Constructs an empty `LinkedList<T, A>`.
503 ///
504 /// # Examples
505 ///
506 /// ```
507 /// #![feature(allocator_api)]
508 ///
509 /// use std::alloc::System;
510 /// use std::collections::LinkedList;
511 ///
512 /// let list: LinkedList<u32, _> = LinkedList::new_in(System);
513 /// ```
514 #[inline]
515 #[unstable(feature = "allocator_api", issue = "32838")]
516 pub const fn new_in(alloc: A) -> Self {
517 LinkedList { head: None, tail: None, len: 0, alloc, marker: PhantomData }
518 }
519 /// Provides a forward iterator.
520 ///
521 /// # Examples
522 ///
523 /// ```
524 /// use std::collections::LinkedList;
525 ///
526 /// let mut list: LinkedList<u32> = LinkedList::new();
527 ///
528 /// list.push_back(0);
529 /// list.push_back(1);
530 /// list.push_back(2);
531 ///
532 /// let mut iter = list.iter();
533 /// assert_eq!(iter.next(), Some(&0));
534 /// assert_eq!(iter.next(), Some(&1));
535 /// assert_eq!(iter.next(), Some(&2));
536 /// assert_eq!(iter.next(), None);
537 /// ```
538 #[inline]
539 #[stable(feature = "rust1", since = "1.0.0")]
540 pub fn iter(&self) -> Iter<'_, T> {
541 Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
542 }
543
544 /// Provides a forward iterator with mutable references.
545 ///
546 /// # Examples
547 ///
548 /// ```
549 /// use std::collections::LinkedList;
550 ///
551 /// let mut list: LinkedList<u32> = LinkedList::new();
552 ///
553 /// list.push_back(0);
554 /// list.push_back(1);
555 /// list.push_back(2);
556 ///
557 /// for element in list.iter_mut() {
558 /// *element += 10;
559 /// }
560 ///
561 /// let mut iter = list.iter();
562 /// assert_eq!(iter.next(), Some(&10));
563 /// assert_eq!(iter.next(), Some(&11));
564 /// assert_eq!(iter.next(), Some(&12));
565 /// assert_eq!(iter.next(), None);
566 /// ```
567 #[inline]
568 #[stable(feature = "rust1", since = "1.0.0")]
569 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
570 IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
571 }
572
573 /// Provides a cursor at the front element.
574 ///
575 /// The cursor is pointing to the "ghost" non-element if the list is empty.
576 #[inline]
577 #[must_use]
578 #[unstable(feature = "linked_list_cursors", issue = "58533")]
579 pub fn cursor_front(&self) -> Cursor<'_, T, A> {
580 Cursor { index: 0, current: self.head, list: self }
581 }
582
583 /// Provides a cursor with editing operations at the front element.
584 ///
585 /// The cursor is pointing to the "ghost" non-element if the list is empty.
586 #[inline]
587 #[must_use]
588 #[unstable(feature = "linked_list_cursors", issue = "58533")]
589 pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A> {
590 CursorMut { index: 0, current: self.head, list: self }
591 }
592
593 /// Provides a cursor at the back element.
594 ///
595 /// The cursor is pointing to the "ghost" non-element if the list is empty.
596 #[inline]
597 #[must_use]
598 #[unstable(feature = "linked_list_cursors", issue = "58533")]
599 pub fn cursor_back(&self) -> Cursor<'_, T, A> {
600 Cursor { index: self.len.saturating_sub(1), current: self.tail, list: self }
601 }
602
603 /// Provides a cursor with editing operations at the back element.
604 ///
605 /// The cursor is pointing to the "ghost" non-element if the list is empty.
606 #[inline]
607 #[must_use]
608 #[unstable(feature = "linked_list_cursors", issue = "58533")]
609 pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A> {
610 CursorMut { index: self.len.saturating_sub(1), current: self.tail, list: self }
611 }
612
613 /// Returns `true` if the `LinkedList` is empty.
614 ///
615 /// This operation should compute in *O*(1) time.
616 ///
617 /// # Examples
618 ///
619 /// ```
620 /// use std::collections::LinkedList;
621 ///
622 /// let mut dl = LinkedList::new();
623 /// assert!(dl.is_empty());
624 ///
625 /// dl.push_front("foo");
626 /// assert!(!dl.is_empty());
627 /// ```
628 #[inline]
629 #[must_use]
630 #[stable(feature = "rust1", since = "1.0.0")]
631 pub fn is_empty(&self) -> bool {
632 self.head.is_none()
633 }
634
635 /// Returns the length of the `LinkedList`.
636 ///
637 /// This operation should compute in *O*(1) time.
638 ///
639 /// # Examples
640 ///
641 /// ```
642 /// use std::collections::LinkedList;
643 ///
644 /// let mut dl = LinkedList::new();
645 ///
646 /// dl.push_front(2);
647 /// assert_eq!(dl.len(), 1);
648 ///
649 /// dl.push_front(1);
650 /// assert_eq!(dl.len(), 2);
651 ///
652 /// dl.push_back(3);
653 /// assert_eq!(dl.len(), 3);
654 /// ```
655 #[inline]
656 #[must_use]
657 #[stable(feature = "rust1", since = "1.0.0")]
658 #[rustc_confusables("length", "size")]
659 pub fn len(&self) -> usize {
660 self.len
661 }
662
663 /// Removes all elements from the `LinkedList`.
664 ///
665 /// This operation should compute in *O*(*n*) time.
666 ///
667 /// # Examples
668 ///
669 /// ```
670 /// use std::collections::LinkedList;
671 ///
672 /// let mut dl = LinkedList::new();
673 ///
674 /// dl.push_front(2);
675 /// dl.push_front(1);
676 /// assert_eq!(dl.len(), 2);
677 /// assert_eq!(dl.front(), Some(&1));
678 ///
679 /// dl.clear();
680 /// assert_eq!(dl.len(), 0);
681 /// assert_eq!(dl.front(), None);
682 /// ```
683 #[inline]
684 #[stable(feature = "rust1", since = "1.0.0")]
685 pub fn clear(&mut self) {
686 // We need to drop the nodes while keeping self.alloc
687 // We can do this by moving (head, tail, len) into a new list that borrows self.alloc
688 drop(LinkedList {
689 head: self.head.take(),
690 tail: self.tail.take(),
691 len: mem::take(&mut self.len),
692 alloc: &self.alloc,
693 marker: PhantomData,
694 });
695 }
696
697 /// Returns `true` if the `LinkedList` contains an element equal to the
698 /// given value.
699 ///
700 /// This operation should compute linearly in *O*(*n*) time.
701 ///
702 /// # Examples
703 ///
704 /// ```
705 /// use std::collections::LinkedList;
706 ///
707 /// let mut list: LinkedList<u32> = LinkedList::new();
708 ///
709 /// list.push_back(0);
710 /// list.push_back(1);
711 /// list.push_back(2);
712 ///
713 /// assert_eq!(list.contains(&0), true);
714 /// assert_eq!(list.contains(&10), false);
715 /// ```
716 #[stable(feature = "linked_list_contains", since = "1.12.0")]
717 pub fn contains(&self, x: &T) -> bool
718 where
719 T: PartialEq<T>,
720 {
721 self.iter().any(|e| e == x)
722 }
723
724 /// Provides a reference to the front element, or `None` if the list is
725 /// empty.
726 ///
727 /// This operation should compute in *O*(1) time.
728 ///
729 /// # Examples
730 ///
731 /// ```
732 /// use std::collections::LinkedList;
733 ///
734 /// let mut dl = LinkedList::new();
735 /// assert_eq!(dl.front(), None);
736 ///
737 /// dl.push_front(1);
738 /// assert_eq!(dl.front(), Some(&1));
739 /// ```
740 #[inline]
741 #[must_use]
742 #[stable(feature = "rust1", since = "1.0.0")]
743 #[rustc_confusables("first")]
744 pub fn front(&self) -> Option<&T> {
745 unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
746 }
747
748 /// Provides a mutable reference to the front element, or `None` if the list
749 /// is empty.
750 ///
751 /// This operation should compute in *O*(1) time.
752 ///
753 /// # Examples
754 ///
755 /// ```
756 /// use std::collections::LinkedList;
757 ///
758 /// let mut dl = LinkedList::new();
759 /// assert_eq!(dl.front(), None);
760 ///
761 /// dl.push_front(1);
762 /// assert_eq!(dl.front(), Some(&1));
763 ///
764 /// match dl.front_mut() {
765 /// None => {},
766 /// Some(x) => *x = 5,
767 /// }
768 /// assert_eq!(dl.front(), Some(&5));
769 /// ```
770 #[inline]
771 #[must_use]
772 #[stable(feature = "rust1", since = "1.0.0")]
773 pub fn front_mut(&mut self) -> Option<&mut T> {
774 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
775 }
776
777 /// Provides a reference to the back element, or `None` if the list is
778 /// empty.
779 ///
780 /// This operation should compute in *O*(1) time.
781 ///
782 /// # Examples
783 ///
784 /// ```
785 /// use std::collections::LinkedList;
786 ///
787 /// let mut dl = LinkedList::new();
788 /// assert_eq!(dl.back(), None);
789 ///
790 /// dl.push_back(1);
791 /// assert_eq!(dl.back(), Some(&1));
792 /// ```
793 #[inline]
794 #[must_use]
795 #[stable(feature = "rust1", since = "1.0.0")]
796 pub fn back(&self) -> Option<&T> {
797 unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
798 }
799
800 /// Provides a mutable reference to the back element, or `None` if the list
801 /// is empty.
802 ///
803 /// This operation should compute in *O*(1) time.
804 ///
805 /// # Examples
806 ///
807 /// ```
808 /// use std::collections::LinkedList;
809 ///
810 /// let mut dl = LinkedList::new();
811 /// assert_eq!(dl.back(), None);
812 ///
813 /// dl.push_back(1);
814 /// assert_eq!(dl.back(), Some(&1));
815 ///
816 /// match dl.back_mut() {
817 /// None => {},
818 /// Some(x) => *x = 5,
819 /// }
820 /// assert_eq!(dl.back(), Some(&5));
821 /// ```
822 #[inline]
823 #[stable(feature = "rust1", since = "1.0.0")]
824 pub fn back_mut(&mut self) -> Option<&mut T> {
825 unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
826 }
827
828 /// Adds an element to the front of the list.
829 ///
830 /// This operation should compute in *O*(1) time.
831 ///
832 /// # Examples
833 ///
834 /// ```
835 /// use std::collections::LinkedList;
836 ///
837 /// let mut dl = LinkedList::new();
838 ///
839 /// dl.push_front(2);
840 /// assert_eq!(dl.front().unwrap(), &2);
841 ///
842 /// dl.push_front(1);
843 /// assert_eq!(dl.front().unwrap(), &1);
844 /// ```
845 #[stable(feature = "rust1", since = "1.0.0")]
846 pub fn push_front(&mut self, elt: T) {
847 let _ = self.push_front_mut(elt);
848 }
849
850 /// Adds an element to the front of the list, returning a reference to it.
851 ///
852 /// This operation should compute in *O*(1) time.
853 ///
854 /// # Examples
855 ///
856 /// ```
857 /// use std::collections::LinkedList;
858 ///
859 /// let mut dl = LinkedList::from([1, 2, 3]);
860 ///
861 /// let ptr = dl.push_front_mut(2);
862 /// *ptr += 4;
863 /// assert_eq!(dl.front().unwrap(), &6);
864 /// ```
865 #[stable(feature = "push_mut", since = "CURRENT_RUSTC_VERSION")]
866 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_front` instead"]
867 pub fn push_front_mut(&mut self, elt: T) -> &mut T {
868 let mut node =
869 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
870 // SAFETY: node is a unique pointer to a node in self.alloc
871 unsafe {
872 self.push_front_node(node);
873 &mut node.as_mut().element
874 }
875 }
876
877 /// Removes the first element and returns it, or `None` if the list is
878 /// empty.
879 ///
880 /// This operation should compute in *O*(1) time.
881 ///
882 /// # Examples
883 ///
884 /// ```
885 /// use std::collections::LinkedList;
886 ///
887 /// let mut d = LinkedList::new();
888 /// assert_eq!(d.pop_front(), None);
889 ///
890 /// d.push_front(1);
891 /// d.push_front(3);
892 /// assert_eq!(d.pop_front(), Some(3));
893 /// assert_eq!(d.pop_front(), Some(1));
894 /// assert_eq!(d.pop_front(), None);
895 /// ```
896 #[stable(feature = "rust1", since = "1.0.0")]
897 pub fn pop_front(&mut self) -> Option<T> {
898 self.pop_front_node().map(Node::into_element)
899 }
900
901 /// Adds an element to the back of the list.
902 ///
903 /// This operation should compute in *O*(1) time.
904 ///
905 /// # Examples
906 ///
907 /// ```
908 /// use std::collections::LinkedList;
909 ///
910 /// let mut d = LinkedList::new();
911 /// d.push_back(1);
912 /// d.push_back(3);
913 /// assert_eq!(3, *d.back().unwrap());
914 /// ```
915 #[stable(feature = "rust1", since = "1.0.0")]
916 #[rustc_confusables("push", "append")]
917 pub fn push_back(&mut self, elt: T) {
918 let _ = self.push_back_mut(elt);
919 }
920
921 /// Adds an element to the back of the list, returning a reference to it.
922 ///
923 /// This operation should compute in *O*(1) time.
924 ///
925 /// # Examples
926 ///
927 /// ```
928 /// use std::collections::LinkedList;
929 ///
930 /// let mut dl = LinkedList::from([1, 2, 3]);
931 ///
932 /// let ptr = dl.push_back_mut(2);
933 /// *ptr += 4;
934 /// assert_eq!(dl.back().unwrap(), &6);
935 /// ```
936 #[stable(feature = "push_mut", since = "CURRENT_RUSTC_VERSION")]
937 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_back` instead"]
938 pub fn push_back_mut(&mut self, elt: T) -> &mut T {
939 let mut node =
940 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
941 // SAFETY: node is a unique pointer to a node in self.alloc
942 unsafe {
943 self.push_back_node(node);
944 &mut node.as_mut().element
945 }
946 }
947
948 /// Removes the last element from a list and returns it, or `None` if
949 /// it is empty.
950 ///
951 /// This operation should compute in *O*(1) time.
952 ///
953 /// # Examples
954 ///
955 /// ```
956 /// use std::collections::LinkedList;
957 ///
958 /// let mut d = LinkedList::new();
959 /// assert_eq!(d.pop_back(), None);
960 /// d.push_back(1);
961 /// d.push_back(3);
962 /// assert_eq!(d.pop_back(), Some(3));
963 /// ```
964 #[stable(feature = "rust1", since = "1.0.0")]
965 pub fn pop_back(&mut self) -> Option<T> {
966 self.pop_back_node().map(Node::into_element)
967 }
968
969 /// Splits the list into two at the given index. Returns everything after the given index,
970 /// including the index.
971 ///
972 /// This operation should compute in *O*(*n*) time.
973 ///
974 /// # Panics
975 ///
976 /// Panics if `at > len`.
977 ///
978 /// # Examples
979 ///
980 /// ```
981 /// use std::collections::LinkedList;
982 ///
983 /// let mut d = LinkedList::new();
984 ///
985 /// d.push_front(1);
986 /// d.push_front(2);
987 /// d.push_front(3);
988 ///
989 /// let mut split = d.split_off(2);
990 ///
991 /// assert_eq!(split.pop_front(), Some(1));
992 /// assert_eq!(split.pop_front(), None);
993 /// ```
994 #[stable(feature = "rust1", since = "1.0.0")]
995 pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>
996 where
997 A: Clone,
998 {
999 let len = self.len();
1000 assert!(at <= len, "Cannot split off at a nonexistent index");
1001 if at == 0 {
1002 return mem::replace(self, Self::new_in(self.alloc.clone()));
1003 } else if at == len {
1004 return Self::new_in(self.alloc.clone());
1005 }
1006
1007 // Below, we iterate towards the `i-1`th node, either from the start or the end,
1008 // depending on which would be faster.
1009 let split_node = if at - 1 <= len - 1 - (at - 1) {
1010 let mut iter = self.iter_mut();
1011 // instead of skipping using .skip() (which creates a new struct),
1012 // we skip manually so we can access the head field without
1013 // depending on implementation details of Skip
1014 for _ in 0..at - 1 {
1015 iter.next();
1016 }
1017 iter.head
1018 } else {
1019 // better off starting from the end
1020 let mut iter = self.iter_mut();
1021 for _ in 0..len - 1 - (at - 1) {
1022 iter.next_back();
1023 }
1024 iter.tail
1025 };
1026 unsafe { self.split_off_after_node(split_node, at) }
1027 }
1028
1029 /// Removes the element at the given index and returns it.
1030 ///
1031 /// This operation should compute in *O*(*n*) time.
1032 ///
1033 /// # Panics
1034 /// Panics if at >= len
1035 ///
1036 /// # Examples
1037 ///
1038 /// ```
1039 /// #![feature(linked_list_remove)]
1040 /// use std::collections::LinkedList;
1041 ///
1042 /// let mut d = LinkedList::new();
1043 ///
1044 /// d.push_front(1);
1045 /// d.push_front(2);
1046 /// d.push_front(3);
1047 ///
1048 /// assert_eq!(d.remove(1), 2);
1049 /// assert_eq!(d.remove(0), 3);
1050 /// assert_eq!(d.remove(0), 1);
1051 /// ```
1052 #[unstable(feature = "linked_list_remove", issue = "69210")]
1053 #[rustc_confusables("delete", "take")]
1054 pub fn remove(&mut self, at: usize) -> T {
1055 let len = self.len();
1056 assert!(at < len, "Cannot remove at an index outside of the list bounds");
1057
1058 // Below, we iterate towards the node at the given index, either from
1059 // the start or the end, depending on which would be faster.
1060 let offset_from_end = len - at - 1;
1061 if at <= offset_from_end {
1062 let mut cursor = self.cursor_front_mut();
1063 for _ in 0..at {
1064 cursor.move_next();
1065 }
1066 cursor.remove_current().unwrap()
1067 } else {
1068 let mut cursor = self.cursor_back_mut();
1069 for _ in 0..offset_from_end {
1070 cursor.move_prev();
1071 }
1072 cursor.remove_current().unwrap()
1073 }
1074 }
1075
1076 /// Retains only the elements specified by the predicate.
1077 ///
1078 /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
1079 /// This method operates in place, visiting each element exactly once in the
1080 /// original order, and preserves the order of the retained elements.
1081 ///
1082 /// # Examples
1083 ///
1084 /// ```
1085 /// #![feature(linked_list_retain)]
1086 /// use std::collections::LinkedList;
1087 ///
1088 /// let mut d = LinkedList::new();
1089 ///
1090 /// d.push_front(1);
1091 /// d.push_front(2);
1092 /// d.push_front(3);
1093 ///
1094 /// d.retain(|&mut x| x % 2 == 0);
1095 ///
1096 /// assert_eq!(d.pop_front(), Some(2));
1097 /// assert_eq!(d.pop_front(), None);
1098 /// ```
1099 ///
1100 /// Because the elements are visited exactly once in the original order,
1101 /// external state may be used to decide which elements to keep.
1102 ///
1103 /// ```
1104 /// #![feature(linked_list_retain)]
1105 /// use std::collections::LinkedList;
1106 ///
1107 /// let mut d = LinkedList::new();
1108 ///
1109 /// d.push_front(1);
1110 /// d.push_front(2);
1111 /// d.push_front(3);
1112 ///
1113 /// let keep = [false, true, false];
1114 /// let mut iter = keep.iter();
1115 /// d.retain(|_| *iter.next().unwrap());
1116 /// assert_eq!(d.pop_front(), Some(2));
1117 /// assert_eq!(d.pop_front(), None);
1118 /// ```
1119 #[unstable(feature = "linked_list_retain", issue = "114135")]
1120 pub fn retain<F>(&mut self, mut f: F)
1121 where
1122 F: FnMut(&mut T) -> bool,
1123 {
1124 let mut cursor = self.cursor_front_mut();
1125 while let Some(node) = cursor.current() {
1126 if !f(node) {
1127 cursor.remove_current().unwrap();
1128 } else {
1129 cursor.move_next();
1130 }
1131 }
1132 }
1133
1134 /// Creates an iterator which uses a closure to determine if an element should be removed.
1135 ///
1136 /// If the closure returns `true`, the element is removed from the list and
1137 /// yielded. If the closure returns `false`, or panics, the element remains
1138 /// in the list and will not be yielded.
1139 ///
1140 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1141 /// or the iteration short-circuits, then the remaining elements will be retained.
1142 /// Use `extract_if().for_each(drop)` if you do not need the returned iterator.
1143 ///
1144 /// The iterator also lets you mutate the value of each element in the
1145 /// closure, regardless of whether you choose to keep or remove it.
1146 ///
1147 /// # Examples
1148 ///
1149 /// Splitting a list into even and odd values, reusing the original list:
1150 ///
1151 /// ```
1152 /// use std::collections::LinkedList;
1153 ///
1154 /// let mut numbers: LinkedList<u32> = LinkedList::new();
1155 /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
1156 ///
1157 /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<LinkedList<_>>();
1158 /// let odds = numbers;
1159 ///
1160 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
1161 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
1162 /// ```
1163 #[stable(feature = "extract_if", since = "1.87.0")]
1164 pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
1165 where
1166 F: FnMut(&mut T) -> bool,
1167 {
1168 // avoid borrow issues.
1169 let it = self.head;
1170 let old_len = self.len;
1171
1172 ExtractIf { list: self, it, pred: filter, idx: 0, old_len }
1173 }
1174}
1175
1176#[stable(feature = "rust1", since = "1.0.0")]
1177unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> {
1178 fn drop(&mut self) {
1179 struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>);
1180
1181 impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
1182 fn drop(&mut self) {
1183 // Continue the same loop we do below. This only runs when a destructor has
1184 // panicked. If another one panics this will abort.
1185 while self.0.pop_front_node().is_some() {}
1186 }
1187 }
1188
1189 // Wrap self so that if a destructor panics, we can try to keep looping
1190 let guard: DropGuard<'_, T, A> = DropGuard(self);
1191 while guard.0.pop_front_node().is_some() {}
1192 mem::forget(guard);
1193 }
1194}
1195
1196#[stable(feature = "rust1", since = "1.0.0")]
1197impl<'a, T> Iterator for Iter<'a, T> {
1198 type Item = &'a T;
1199
1200 #[inline]
1201 fn next(&mut self) -> Option<&'a T> {
1202 if self.len == 0 {
1203 None
1204 } else {
1205 self.head.map(|node| unsafe {
1206 // Need an unbound lifetime to get 'a
1207 let node = &*node.as_ptr();
1208 self.len -= 1;
1209 self.head = node.next;
1210 &node.element
1211 })
1212 }
1213 }
1214
1215 #[inline]
1216 fn size_hint(&self) -> (usize, Option<usize>) {
1217 (self.len, Some(self.len))
1218 }
1219
1220 #[inline]
1221 fn last(mut self) -> Option<&'a T> {
1222 self.next_back()
1223 }
1224}
1225
1226#[stable(feature = "rust1", since = "1.0.0")]
1227impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1228 #[inline]
1229 fn next_back(&mut self) -> Option<&'a T> {
1230 if self.len == 0 {
1231 None
1232 } else {
1233 self.tail.map(|node| unsafe {
1234 // Need an unbound lifetime to get 'a
1235 let node: &{unknown} = &*node.as_ptr();
1236 self.len -= 1;
1237 self.tail = node.prev;
1238 &node.element
1239 })
1240 }
1241 }
1242}
1243
1244#[stable(feature = "rust1", since = "1.0.0")]
1245impl<T> ExactSizeIterator for Iter<'_, T> {}
1246
1247#[stable(feature = "fused", since = "1.26.0")]
1248impl<T> FusedIterator for Iter<'_, T> {}
1249
1250#[stable(feature = "default_iters", since = "1.70.0")]
1251impl<T> Default for Iter<'_, T> {
1252 /// Creates an empty `linked_list::Iter`.
1253 ///
1254 /// ```
1255 /// # use std::collections::linked_list;
1256 /// let iter: linked_list::Iter<'_, u8> = Default::default();
1257 /// assert_eq!(iter.len(), 0);
1258 /// ```
1259 fn default() -> Self {
1260 Iter { head: None, tail: None, len: 0, marker: Default::default() }
1261 }
1262}
1263
1264#[stable(feature = "rust1", since = "1.0.0")]
1265impl<'a, T> Iterator for IterMut<'a, T> {
1266 type Item = &'a mut T;
1267
1268 #[inline]
1269 fn next(&mut self) -> Option<&'a mut T> {
1270 if self.len == 0 {
1271 None
1272 } else {
1273 self.head.map(|node| unsafe {
1274 // Need an unbound lifetime to get 'a
1275 let node = &mut *node.as_ptr();
1276 self.len -= 1;
1277 self.head = node.next;
1278 &mut node.element
1279 })
1280 }
1281 }
1282
1283 #[inline]
1284 fn size_hint(&self) -> (usize, Option<usize>) {
1285 (self.len, Some(self.len))
1286 }
1287
1288 #[inline]
1289 fn last(mut self) -> Option<&'a mut T> {
1290 self.next_back()
1291 }
1292}
1293
1294#[stable(feature = "rust1", since = "1.0.0")]
1295impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1296 #[inline]
1297 fn next_back(&mut self) -> Option<&'a mut T> {
1298 if self.len == 0 {
1299 None
1300 } else {
1301 self.tail.map(|node| unsafe {
1302 // Need an unbound lifetime to get 'a
1303 let node: &mut {unknown} = &mut *node.as_ptr();
1304 self.len -= 1;
1305 self.tail = node.prev;
1306 &mut node.element
1307 })
1308 }
1309 }
1310}
1311
1312#[stable(feature = "rust1", since = "1.0.0")]
1313impl<T> ExactSizeIterator for IterMut<'_, T> {}
1314
1315#[stable(feature = "fused", since = "1.26.0")]
1316impl<T> FusedIterator for IterMut<'_, T> {}
1317
1318#[stable(feature = "default_iters", since = "1.70.0")]
1319impl<T> Default for IterMut<'_, T> {
1320 fn default() -> Self {
1321 IterMut { head: None, tail: None, len: 0, marker: Default::default() }
1322 }
1323}
1324
1325/// A cursor over a `LinkedList`.
1326///
1327/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
1328///
1329/// Cursors always rest between two elements in the list, and index in a logically circular way.
1330/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1331/// tail of the list.
1332///
1333/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
1334#[unstable(feature = "linked_list_cursors", issue = "58533")]
1335pub struct Cursor<
1336 'a,
1337 T: 'a,
1338 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1339> {
1340 index: usize,
1341 current: Option<NonNull<Node<T>>>,
1342 list: &'a LinkedList<T, A>,
1343}
1344
1345#[unstable(feature = "linked_list_cursors", issue = "58533")]
1346impl<T, A: Allocator> Clone for Cursor<'_, T, A> {
1347 fn clone(&self) -> Self {
1348 let Cursor { index: usize, current, list: &LinkedList } = *self;
1349 Cursor { index, current, list }
1350 }
1351}
1352
1353#[unstable(feature = "linked_list_cursors", issue = "58533")]
1354impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> {
1355 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1356 f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
1357 }
1358}
1359
1360/// A cursor over a `LinkedList` with editing operations.
1361///
1362/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
1363/// safely mutate the list during iteration. This is because the lifetime of its yielded
1364/// references is tied to its own lifetime, instead of just the underlying list. This means
1365/// cursors cannot yield multiple elements at once.
1366///
1367/// Cursors always rest between two elements in the list, and index in a logically circular way.
1368/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1369/// tail of the list.
1370#[unstable(feature = "linked_list_cursors", issue = "58533")]
1371pub struct CursorMut<
1372 'a,
1373 T: 'a,
1374 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1375> {
1376 index: usize,
1377 current: Option<NonNull<Node<T>>>,
1378 list: &'a mut LinkedList<T, A>,
1379}
1380
1381#[unstable(feature = "linked_list_cursors", issue = "58533")]
1382impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> {
1383 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1384 f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
1385 }
1386}
1387
1388impl<'a, T, A: Allocator> Cursor<'a, T, A> {
1389 /// Returns the cursor position index within the `LinkedList`.
1390 ///
1391 /// This returns `None` if the cursor is currently pointing to the
1392 /// "ghost" non-element.
1393 #[must_use]
1394 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1395 pub fn index(&self) -> Option<usize> {
1396 let _ = self.current?;
1397 Some(self.index)
1398 }
1399
1400 /// Moves the cursor to the next element of the `LinkedList`.
1401 ///
1402 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1403 /// the first element of the `LinkedList`. If it is pointing to the last
1404 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1405 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1406 pub fn move_next(&mut self) {
1407 match self.current.take() {
1408 // We had no current element; the cursor was sitting at the start position
1409 // Next element should be the head of the list
1410 None => {
1411 self.current = self.list.head;
1412 self.index = 0;
1413 }
1414 // We had a previous element, so let's go to its next
1415 Some(current) => unsafe {
1416 self.current = current.as_ref().next;
1417 self.index += 1;
1418 },
1419 }
1420 }
1421
1422 /// Moves the cursor to the previous element of the `LinkedList`.
1423 ///
1424 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1425 /// the last element of the `LinkedList`. If it is pointing to the first
1426 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1427 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1428 pub fn move_prev(&mut self) {
1429 match self.current.take() {
1430 // No current. We're at the start of the list. Yield None and jump to the end.
1431 None => {
1432 self.current = self.list.tail;
1433 self.index = self.list.len().saturating_sub(1);
1434 }
1435 // Have a prev. Yield it and go to the previous element.
1436 Some(current) => unsafe {
1437 self.current = current.as_ref().prev;
1438 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1439 },
1440 }
1441 }
1442
1443 /// Returns a reference to the element that the cursor is currently
1444 /// pointing to.
1445 ///
1446 /// This returns `None` if the cursor is currently pointing to the
1447 /// "ghost" non-element.
1448 #[must_use]
1449 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1450 pub fn current(&self) -> Option<&'a T> {
1451 unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
1452 }
1453
1454 /// Returns a reference to the next element.
1455 ///
1456 /// If the cursor is pointing to the "ghost" non-element then this returns
1457 /// the first element of the `LinkedList`. If it is pointing to the last
1458 /// element of the `LinkedList` then this returns `None`.
1459 #[must_use]
1460 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1461 pub fn peek_next(&self) -> Option<&'a T> {
1462 unsafe {
1463 let next = match self.current {
1464 None => self.list.head,
1465 Some(current) => current.as_ref().next,
1466 };
1467 next.map(|next| &(*next.as_ptr()).element)
1468 }
1469 }
1470
1471 /// Returns a reference to the previous element.
1472 ///
1473 /// If the cursor is pointing to the "ghost" non-element then this returns
1474 /// the last element of the `LinkedList`. If it is pointing to the first
1475 /// element of the `LinkedList` then this returns `None`.
1476 #[must_use]
1477 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1478 pub fn peek_prev(&self) -> Option<&'a T> {
1479 unsafe {
1480 let prev = match self.current {
1481 None => self.list.tail,
1482 Some(current) => current.as_ref().prev,
1483 };
1484 prev.map(|prev| &(*prev.as_ptr()).element)
1485 }
1486 }
1487
1488 /// Provides a reference to the front element of the cursor's parent list,
1489 /// or None if the list is empty.
1490 #[must_use]
1491 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1492 #[rustc_confusables("first")]
1493 pub fn front(&self) -> Option<&'a T> {
1494 self.list.front()
1495 }
1496
1497 /// Provides a reference to the back element of the cursor's parent list,
1498 /// or None if the list is empty.
1499 #[must_use]
1500 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1501 #[rustc_confusables("last")]
1502 pub fn back(&self) -> Option<&'a T> {
1503 self.list.back()
1504 }
1505
1506 /// Provides a reference to the cursor's parent list.
1507 #[must_use]
1508 #[inline(always)]
1509 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1510 pub fn as_list(&self) -> &'a LinkedList<T, A> {
1511 self.list
1512 }
1513}
1514
1515impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1516 /// Returns the cursor position index within the `LinkedList`.
1517 ///
1518 /// This returns `None` if the cursor is currently pointing to the
1519 /// "ghost" non-element.
1520 #[must_use]
1521 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1522 pub fn index(&self) -> Option<usize> {
1523 let _ = self.current?;
1524 Some(self.index)
1525 }
1526
1527 /// Moves the cursor to the next element of the `LinkedList`.
1528 ///
1529 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1530 /// the first element of the `LinkedList`. If it is pointing to the last
1531 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1532 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1533 pub fn move_next(&mut self) {
1534 match self.current.take() {
1535 // We had no current element; the cursor was sitting at the start position
1536 // Next element should be the head of the list
1537 None => {
1538 self.current = self.list.head;
1539 self.index = 0;
1540 }
1541 // We had a previous element, so let's go to its next
1542 Some(current) => unsafe {
1543 self.current = current.as_ref().next;
1544 self.index += 1;
1545 },
1546 }
1547 }
1548
1549 /// Moves the cursor to the previous element of the `LinkedList`.
1550 ///
1551 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1552 /// the last element of the `LinkedList`. If it is pointing to the first
1553 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1554 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1555 pub fn move_prev(&mut self) {
1556 match self.current.take() {
1557 // No current. We're at the start of the list. Yield None and jump to the end.
1558 None => {
1559 self.current = self.list.tail;
1560 self.index = self.list.len().saturating_sub(1);
1561 }
1562 // Have a prev. Yield it and go to the previous element.
1563 Some(current) => unsafe {
1564 self.current = current.as_ref().prev;
1565 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1566 },
1567 }
1568 }
1569
1570 /// Returns a reference to the element that the cursor is currently
1571 /// pointing to.
1572 ///
1573 /// This returns `None` if the cursor is currently pointing to the
1574 /// "ghost" non-element.
1575 #[must_use]
1576 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1577 pub fn current(&mut self) -> Option<&mut T> {
1578 unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
1579 }
1580
1581 /// Returns a reference to the next element.
1582 ///
1583 /// If the cursor is pointing to the "ghost" non-element then this returns
1584 /// the first element of the `LinkedList`. If it is pointing to the last
1585 /// element of the `LinkedList` then this returns `None`.
1586 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1587 pub fn peek_next(&mut self) -> Option<&mut T> {
1588 unsafe {
1589 let next = match self.current {
1590 None => self.list.head,
1591 Some(current) => current.as_ref().next,
1592 };
1593 next.map(|next| &mut (*next.as_ptr()).element)
1594 }
1595 }
1596
1597 /// Returns a reference to the previous element.
1598 ///
1599 /// If the cursor is pointing to the "ghost" non-element then this returns
1600 /// the last element of the `LinkedList`. If it is pointing to the first
1601 /// element of the `LinkedList` then this returns `None`.
1602 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1603 pub fn peek_prev(&mut self) -> Option<&mut T> {
1604 unsafe {
1605 let prev = match self.current {
1606 None => self.list.tail,
1607 Some(current) => current.as_ref().prev,
1608 };
1609 prev.map(|prev| &mut (*prev.as_ptr()).element)
1610 }
1611 }
1612
1613 /// Returns a read-only cursor pointing to the current element.
1614 ///
1615 /// The lifetime of the returned `Cursor` is bound to that of the
1616 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1617 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
1618 #[must_use]
1619 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1620 pub fn as_cursor(&self) -> Cursor<'_, T, A> {
1621 Cursor { list: self.list, current: self.current, index: self.index }
1622 }
1623
1624 /// Provides a read-only reference to the cursor's parent list.
1625 ///
1626 /// The lifetime of the returned reference is bound to that of the
1627 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1628 /// `CursorMut` is frozen for the lifetime of the reference.
1629 #[must_use]
1630 #[inline(always)]
1631 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1632 pub fn as_list(&self) -> &LinkedList<T, A> {
1633 self.list
1634 }
1635}
1636
1637// Now the list editing operations
1638
1639impl<'a, T> CursorMut<'a, T> {
1640 /// Inserts the elements from the given `LinkedList` after the current one.
1641 ///
1642 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1643 /// inserted at the start of the `LinkedList`.
1644 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1645 pub fn splice_after(&mut self, list: LinkedList<T>) {
1646 unsafe {
1647 let Some((splice_head, splice_tail, splice_len)) = list.detach_all_nodes() else {
1648 return;
1649 };
1650 let node_next = match self.current {
1651 None => self.list.head,
1652 Some(node) => node.as_ref().next,
1653 };
1654 self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
1655 if self.current.is_none() {
1656 // The "ghost" non-element's index has changed.
1657 self.index = self.list.len;
1658 }
1659 }
1660 }
1661
1662 /// Inserts the elements from the given `LinkedList` before the current one.
1663 ///
1664 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1665 /// inserted at the end of the `LinkedList`.
1666 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1667 pub fn splice_before(&mut self, list: LinkedList<T>) {
1668 unsafe {
1669 let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1670 Some(parts) => parts,
1671 _ => return,
1672 };
1673 let node_prev = match self.current {
1674 None => self.list.tail,
1675 Some(node) => node.as_ref().prev,
1676 };
1677 self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
1678 self.index += splice_len;
1679 }
1680 }
1681}
1682
1683impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1684 /// Inserts a new element into the `LinkedList` after the current one.
1685 ///
1686 /// If the cursor is pointing at the "ghost" non-element then the new element is
1687 /// inserted at the front of the `LinkedList`.
1688 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1689 pub fn insert_after(&mut self, item: T) {
1690 unsafe {
1691 let spliced_node =
1692 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1693 let node_next = match self.current {
1694 None => self.list.head,
1695 Some(node) => node.as_ref().next,
1696 };
1697 self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
1698 if self.current.is_none() {
1699 // The "ghost" non-element's index has changed.
1700 self.index = self.list.len;
1701 }
1702 }
1703 }
1704
1705 /// Inserts a new element into the `LinkedList` before the current one.
1706 ///
1707 /// If the cursor is pointing at the "ghost" non-element then the new element is
1708 /// inserted at the end of the `LinkedList`.
1709 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1710 pub fn insert_before(&mut self, item: T) {
1711 unsafe {
1712 let spliced_node =
1713 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1714 let node_prev = match self.current {
1715 None => self.list.tail,
1716 Some(node) => node.as_ref().prev,
1717 };
1718 self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
1719 self.index += 1;
1720 }
1721 }
1722
1723 /// Removes the current element from the `LinkedList`.
1724 ///
1725 /// The element that was removed is returned, and the cursor is
1726 /// moved to point to the next element in the `LinkedList`.
1727 ///
1728 /// If the cursor is currently pointing to the "ghost" non-element then no element
1729 /// is removed and `None` is returned.
1730 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1731 pub fn remove_current(&mut self) -> Option<T> {
1732 let unlinked_node = self.current?;
1733 unsafe {
1734 self.current = unlinked_node.as_ref().next;
1735 self.list.unlink_node(unlinked_node);
1736 let unlinked_node = Box::from_raw_in(unlinked_node.as_ptr(), &self.list.alloc);
1737 Some(unlinked_node.element)
1738 }
1739 }
1740
1741 /// Removes the current element from the `LinkedList` without deallocating the list node.
1742 ///
1743 /// The node that was removed is returned as a new `LinkedList` containing only this node.
1744 /// The cursor is moved to point to the next element in the current `LinkedList`.
1745 ///
1746 /// If the cursor is currently pointing to the "ghost" non-element then no element
1747 /// is removed and `None` is returned.
1748 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1749 pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>>
1750 where
1751 A: Clone,
1752 {
1753 let mut unlinked_node = self.current?;
1754 unsafe {
1755 self.current = unlinked_node.as_ref().next;
1756 self.list.unlink_node(unlinked_node);
1757
1758 unlinked_node.as_mut().prev = None;
1759 unlinked_node.as_mut().next = None;
1760 Some(LinkedList {
1761 head: Some(unlinked_node),
1762 tail: Some(unlinked_node),
1763 len: 1,
1764 alloc: self.list.alloc.clone(),
1765 marker: PhantomData,
1766 })
1767 }
1768 }
1769
1770 /// Splits the list into two after the current element. This will return a
1771 /// new list consisting of everything after the cursor, with the original
1772 /// list retaining everything before.
1773 ///
1774 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1775 /// of the `LinkedList` are moved.
1776 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1777 pub fn split_after(&mut self) -> LinkedList<T, A>
1778 where
1779 A: Clone,
1780 {
1781 let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
1782 if self.index == self.list.len {
1783 // The "ghost" non-element's index has changed to 0.
1784 self.index = 0;
1785 }
1786 unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
1787 }
1788
1789 /// Splits the list into two before the current element. This will return a
1790 /// new list consisting of everything before the cursor, with the original
1791 /// list retaining everything after.
1792 ///
1793 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1794 /// of the `LinkedList` are moved.
1795 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1796 pub fn split_before(&mut self) -> LinkedList<T, A>
1797 where
1798 A: Clone,
1799 {
1800 let split_off_idx = self.index;
1801 self.index = 0;
1802 unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
1803 }
1804
1805 /// Appends an element to the front of the cursor's parent list. The node
1806 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1807 ///
1808 /// This operation should compute in *O*(1) time.
1809 // `push_front` continues to point to "ghost" when it adds a node to mimic
1810 // the behavior of `insert_before` on an empty list.
1811 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1812 pub fn push_front(&mut self, elt: T) {
1813 // Safety: We know that `push_front` does not change the position in
1814 // memory of other nodes. This ensures that `self.current` remains
1815 // valid.
1816 self.list.push_front(elt);
1817 self.index += 1;
1818 }
1819
1820 /// Appends an element to the back of the cursor's parent list. The node
1821 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1822 ///
1823 /// This operation should compute in *O*(1) time.
1824 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1825 #[rustc_confusables("push", "append")]
1826 pub fn push_back(&mut self, elt: T) {
1827 // Safety: We know that `push_back` does not change the position in
1828 // memory of other nodes. This ensures that `self.current` remains
1829 // valid.
1830 self.list.push_back(elt);
1831 if self.current().is_none() {
1832 // The index of "ghost" is the length of the list, so we just need
1833 // to increment self.index to reflect the new length of the list.
1834 self.index += 1;
1835 }
1836 }
1837
1838 /// Removes the first element from the cursor's parent list and returns it,
1839 /// or None if the list is empty. The element the cursor points to remains
1840 /// unchanged, unless it was pointing to the front element. In that case, it
1841 /// points to the new front element.
1842 ///
1843 /// This operation should compute in *O*(1) time.
1844 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1845 pub fn pop_front(&mut self) -> Option<T> {
1846 // We can't check if current is empty, we must check the list directly.
1847 // It is possible for `self.current == None` and the list to be
1848 // non-empty.
1849 if self.list.is_empty() {
1850 None
1851 } else {
1852 // We can't point to the node that we pop. Copying the behavior of
1853 // `remove_current`, we move on to the next node in the sequence.
1854 // If the list is of length 1 then we end pointing to the "ghost"
1855 // node at index 0, which is expected.
1856 if self.list.head == self.current {
1857 self.move_next();
1858 }
1859 // An element was removed before (or at) our current position, so
1860 // the index must be decremented. `saturating_sub` handles the
1861 // ghost node case where index could be 0.
1862 self.index = self.index.saturating_sub(1);
1863 self.list.pop_front()
1864 }
1865 }
1866
1867 /// Removes the last element from the cursor's parent list and returns it,
1868 /// or None if the list is empty. The element the cursor points to remains
1869 /// unchanged, unless it was pointing to the back element. In that case, it
1870 /// points to the "ghost" element.
1871 ///
1872 /// This operation should compute in *O*(1) time.
1873 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1874 #[rustc_confusables("pop")]
1875 pub fn pop_back(&mut self) -> Option<T> {
1876 if self.list.is_empty() {
1877 None
1878 } else {
1879 if self.list.tail == self.current {
1880 // The index now reflects the length of the list. It was the
1881 // length of the list minus 1, but now the list is 1 smaller. No
1882 // change is needed for `index`.
1883 self.current = None;
1884 } else if self.current.is_none() {
1885 self.index = self.list.len - 1;
1886 }
1887 self.list.pop_back()
1888 }
1889 }
1890
1891 /// Provides a reference to the front element of the cursor's parent list,
1892 /// or None if the list is empty.
1893 #[must_use]
1894 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1895 #[rustc_confusables("first")]
1896 pub fn front(&self) -> Option<&T> {
1897 self.list.front()
1898 }
1899
1900 /// Provides a mutable reference to the front element of the cursor's
1901 /// parent list, or None if the list is empty.
1902 #[must_use]
1903 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1904 pub fn front_mut(&mut self) -> Option<&mut T> {
1905 self.list.front_mut()
1906 }
1907
1908 /// Provides a reference to the back element of the cursor's parent list,
1909 /// or None if the list is empty.
1910 #[must_use]
1911 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1912 #[rustc_confusables("last")]
1913 pub fn back(&self) -> Option<&T> {
1914 self.list.back()
1915 }
1916
1917 /// Provides a mutable reference to back element of the cursor's parent
1918 /// list, or `None` if the list is empty.
1919 ///
1920 /// # Examples
1921 /// Building and mutating a list with a cursor, then getting the back element:
1922 /// ```
1923 /// #![feature(linked_list_cursors)]
1924 /// use std::collections::LinkedList;
1925 /// let mut dl = LinkedList::new();
1926 /// dl.push_front(3);
1927 /// dl.push_front(2);
1928 /// dl.push_front(1);
1929 /// let mut cursor = dl.cursor_front_mut();
1930 /// *cursor.current().unwrap() = 99;
1931 /// *cursor.back_mut().unwrap() = 0;
1932 /// let mut contents = dl.into_iter();
1933 /// assert_eq!(contents.next(), Some(99));
1934 /// assert_eq!(contents.next(), Some(2));
1935 /// assert_eq!(contents.next(), Some(0));
1936 /// assert_eq!(contents.next(), None);
1937 /// ```
1938 #[must_use]
1939 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1940 pub fn back_mut(&mut self) -> Option<&mut T> {
1941 self.list.back_mut()
1942 }
1943}
1944
1945/// An iterator produced by calling `extract_if` on LinkedList.
1946#[stable(feature = "extract_if", since = "1.87.0")]
1947#[must_use = "iterators are lazy and do nothing unless consumed; \
1948 use `extract_if().for_each(drop)` to remove and discard elements"]
1949pub struct ExtractIf<
1950 'a,
1951 T: 'a,
1952 F: 'a,
1953 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1954> {
1955 list: &'a mut LinkedList<T, A>,
1956 it: Option<NonNull<Node<T>>>,
1957 pred: F,
1958 idx: usize,
1959 old_len: usize,
1960}
1961
1962#[stable(feature = "extract_if", since = "1.87.0")]
1963impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
1964where
1965 F: FnMut(&mut T) -> bool,
1966{
1967 type Item = T;
1968
1969 fn next(&mut self) -> Option<T> {
1970 while let Some(mut node) = self.it {
1971 unsafe {
1972 self.it = node.as_ref().next;
1973 self.idx += 1;
1974
1975 if (self.pred)(&mut node.as_mut().element) {
1976 // `unlink_node` is okay with aliasing `element` references.
1977 self.list.unlink_node(node);
1978 return Some(Box::from_raw_in(raw:node.as_ptr(), &self.list.alloc).element);
1979 }
1980 }
1981 }
1982
1983 None
1984 }
1985
1986 fn size_hint(&self) -> (usize, Option<usize>) {
1987 (0, Some(self.old_len - self.idx))
1988 }
1989}
1990
1991#[stable(feature = "extract_if", since = "1.87.0")]
1992impl<T, F, A> fmt::Debug for ExtractIf<'_, T, F, A>
1993where
1994 T: fmt::Debug,
1995 A: Allocator,
1996{
1997 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1998 let peek = self.it.map(|node| unsafe { &node.as_ref().element });
1999 f.debug_struct("ExtractIf").field("peek", &peek).finish_non_exhaustive()
2000 }
2001}
2002
2003#[stable(feature = "rust1", since = "1.0.0")]
2004impl<T, A: Allocator> Iterator for IntoIter<T, A> {
2005 type Item = T;
2006
2007 #[inline]
2008 fn next(&mut self) -> Option<T> {
2009 self.list.pop_front()
2010 }
2011
2012 #[inline]
2013 fn size_hint(&self) -> (usize, Option<usize>) {
2014 (self.list.len, Some(self.list.len))
2015 }
2016}
2017
2018#[stable(feature = "rust1", since = "1.0.0")]
2019impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
2020 #[inline]
2021 fn next_back(&mut self) -> Option<T> {
2022 self.list.pop_back()
2023 }
2024}
2025
2026#[stable(feature = "rust1", since = "1.0.0")]
2027impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {}
2028
2029#[stable(feature = "fused", since = "1.26.0")]
2030impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
2031
2032#[stable(feature = "default_iters", since = "1.70.0")]
2033impl<T> Default for IntoIter<T> {
2034 /// Creates an empty `linked_list::IntoIter`.
2035 ///
2036 /// ```
2037 /// # use std::collections::linked_list;
2038 /// let iter: linked_list::IntoIter<u8> = Default::default();
2039 /// assert_eq!(iter.len(), 0);
2040 /// ```
2041 fn default() -> Self {
2042 LinkedList::new().into_iter()
2043 }
2044}
2045
2046#[stable(feature = "rust1", since = "1.0.0")]
2047impl<T> FromIterator<T> for LinkedList<T> {
2048 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
2049 let mut list: LinkedList = Self::new();
2050 list.extend(iter);
2051 list
2052 }
2053}
2054
2055#[stable(feature = "rust1", since = "1.0.0")]
2056impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
2057 type Item = T;
2058 type IntoIter = IntoIter<T, A>;
2059
2060 /// Consumes the list into an iterator yielding elements by value.
2061 #[inline]
2062 fn into_iter(self) -> IntoIter<T, A> {
2063 IntoIter { list: self }
2064 }
2065}
2066
2067#[stable(feature = "rust1", since = "1.0.0")]
2068impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
2069 type Item = &'a T;
2070 type IntoIter = Iter<'a, T>;
2071
2072 fn into_iter(self) -> Iter<'a, T> {
2073 self.iter()
2074 }
2075}
2076
2077#[stable(feature = "rust1", since = "1.0.0")]
2078impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
2079 type Item = &'a mut T;
2080 type IntoIter = IterMut<'a, T>;
2081
2082 fn into_iter(self) -> IterMut<'a, T> {
2083 self.iter_mut()
2084 }
2085}
2086
2087#[stable(feature = "rust1", since = "1.0.0")]
2088impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
2089 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2090 <Self as SpecExtend<I>>::spec_extend(self, iter);
2091 }
2092
2093 #[inline]
2094 fn extend_one(&mut self, elem: T) {
2095 self.push_back(elt:elem);
2096 }
2097}
2098
2099impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> {
2100 default fn spec_extend(&mut self, iter: I) {
2101 iter.into_iter().for_each(move |elt| self.push_back(elt));
2102 }
2103}
2104
2105impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
2106 fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
2107 self.append(other);
2108 }
2109}
2110
2111#[stable(feature = "extend_ref", since = "1.2.0")]
2112impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> {
2113 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2114 self.extend(iter.into_iter().cloned());
2115 }
2116
2117 #[inline]
2118 fn extend_one(&mut self, &elem: T: &'a T) {
2119 self.push_back(elt:elem);
2120 }
2121}
2122
2123#[stable(feature = "rust1", since = "1.0.0")]
2124impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> {
2125 fn eq(&self, other: &Self) -> bool {
2126 self.len() == other.len() && self.iter().eq(other)
2127 }
2128
2129 fn ne(&self, other: &Self) -> bool {
2130 self.len() != other.len() || self.iter().ne(other)
2131 }
2132}
2133
2134#[stable(feature = "rust1", since = "1.0.0")]
2135impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}
2136
2137#[stable(feature = "rust1", since = "1.0.0")]
2138impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> {
2139 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2140 self.iter().partial_cmp(other)
2141 }
2142}
2143
2144#[stable(feature = "rust1", since = "1.0.0")]
2145impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
2146 #[inline]
2147 fn cmp(&self, other: &Self) -> Ordering {
2148 self.iter().cmp(other)
2149 }
2150}
2151
2152#[stable(feature = "rust1", since = "1.0.0")]
2153impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
2154 fn clone(&self) -> Self {
2155 let mut list = Self::new_in(self.alloc.clone());
2156 list.extend(self.iter().cloned());
2157 list
2158 }
2159
2160 /// Overwrites the contents of `self` with a clone of the contents of `source`.
2161 ///
2162 /// This method is preferred over simply assigning `source.clone()` to `self`,
2163 /// as it avoids reallocation of the nodes of the linked list. Additionally,
2164 /// if the element type `T` overrides `clone_from()`, this will reuse the
2165 /// resources of `self`'s elements as well.
2166 fn clone_from(&mut self, source: &Self) {
2167 let mut source_iter = source.iter();
2168 if self.len() > source.len() {
2169 self.split_off(source.len());
2170 }
2171 for (elem, source_elem) in self.iter_mut().zip(&mut source_iter) {
2172 elem.clone_from(source_elem);
2173 }
2174 if !source_iter.is_empty() {
2175 self.extend(source_iter.cloned());
2176 }
2177 }
2178}
2179
2180#[stable(feature = "rust1", since = "1.0.0")]
2181impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> {
2182 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2183 f.debug_list().entries(self).finish()
2184 }
2185}
2186
2187#[stable(feature = "rust1", since = "1.0.0")]
2188impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
2189 fn hash<H: Hasher>(&self, state: &mut H) {
2190 state.write_length_prefix(self.len());
2191 for elt in self {
2192 elt.hash(state);
2193 }
2194 }
2195}
2196
2197#[stable(feature = "std_collections_from_array", since = "1.56.0")]
2198impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
2199 /// Converts a `[T; N]` into a `LinkedList<T>`.
2200 ///
2201 /// ```
2202 /// use std::collections::LinkedList;
2203 ///
2204 /// let list1 = LinkedList::from([1, 2, 3, 4]);
2205 /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
2206 /// assert_eq!(list1, list2);
2207 /// ```
2208 fn from(arr: [T; N]) -> Self {
2209 Self::from_iter(arr)
2210 }
2211}
2212
2213// Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
2214#[allow(dead_code)]
2215fn assert_covariance() {
2216 fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
2217 x
2218 }
2219 fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
2220 x
2221 }
2222 fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
2223 x
2224 }
2225}
2226
2227#[stable(feature = "rust1", since = "1.0.0")]
2228unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {}
2229
2230#[stable(feature = "rust1", since = "1.0.0")]
2231unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {}
2232
2233#[stable(feature = "rust1", since = "1.0.0")]
2234unsafe impl<T: Sync> Send for Iter<'_, T> {}
2235
2236#[stable(feature = "rust1", since = "1.0.0")]
2237unsafe impl<T: Sync> Sync for Iter<'_, T> {}
2238
2239#[stable(feature = "rust1", since = "1.0.0")]
2240unsafe impl<T: Send> Send for IterMut<'_, T> {}
2241
2242#[stable(feature = "rust1", since = "1.0.0")]
2243unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
2244
2245#[unstable(feature = "linked_list_cursors", issue = "58533")]
2246unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {}
2247
2248#[unstable(feature = "linked_list_cursors", issue = "58533")]
2249unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {}
2250
2251#[unstable(feature = "linked_list_cursors", issue = "58533")]
2252unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {}
2253
2254#[unstable(feature = "linked_list_cursors", issue = "58533")]
2255unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {}
2256