alloc/collections/linked_list.rs
1//! A doubly-linked list with owned nodes.
2//!
3//! The `LinkedList` allows pushing and popping elements at either end
4//! in constant time.
5//!
6//! 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 /// #![feature(push_mut)]
858 /// use std::collections::LinkedList;
859 ///
860 /// let mut dl = LinkedList::from([1, 2, 3]);
861 ///
862 /// let ptr = dl.push_front_mut(2);
863 /// *ptr += 4;
864 /// assert_eq!(dl.front().unwrap(), &6);
865 /// ```
866 #[unstable(feature = "push_mut", issue = "135974")]
867 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_front` instead"]
868 pub fn push_front_mut(&mut self, elt: T) -> &mut T {
869 let mut node =
870 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
871 // SAFETY: node is a unique pointer to a node in self.alloc
872 unsafe {
873 self.push_front_node(node);
874 &mut node.as_mut().element
875 }
876 }
877
878 /// Removes the first element and returns it, or `None` if the list is
879 /// empty.
880 ///
881 /// This operation should compute in *O*(1) time.
882 ///
883 /// # Examples
884 ///
885 /// ```
886 /// use std::collections::LinkedList;
887 ///
888 /// let mut d = LinkedList::new();
889 /// assert_eq!(d.pop_front(), None);
890 ///
891 /// d.push_front(1);
892 /// d.push_front(3);
893 /// assert_eq!(d.pop_front(), Some(3));
894 /// assert_eq!(d.pop_front(), Some(1));
895 /// assert_eq!(d.pop_front(), None);
896 /// ```
897 #[stable(feature = "rust1", since = "1.0.0")]
898 pub fn pop_front(&mut self) -> Option<T> {
899 self.pop_front_node().map(Node::into_element)
900 }
901
902 /// Adds an element to the back of the list.
903 ///
904 /// This operation should compute in *O*(1) time.
905 ///
906 /// # Examples
907 ///
908 /// ```
909 /// use std::collections::LinkedList;
910 ///
911 /// let mut d = LinkedList::new();
912 /// d.push_back(1);
913 /// d.push_back(3);
914 /// assert_eq!(3, *d.back().unwrap());
915 /// ```
916 #[stable(feature = "rust1", since = "1.0.0")]
917 #[rustc_confusables("push", "append")]
918 pub fn push_back(&mut self, elt: T) {
919 let _ = self.push_back_mut(elt);
920 }
921
922 /// Adds an element to the back of the list, returning a reference to it.
923 ///
924 /// This operation should compute in *O*(1) time.
925 ///
926 /// # Examples
927 ///
928 /// ```
929 /// #![feature(push_mut)]
930 /// use std::collections::LinkedList;
931 ///
932 /// let mut dl = LinkedList::from([1, 2, 3]);
933 ///
934 /// let ptr = dl.push_back_mut(2);
935 /// *ptr += 4;
936 /// assert_eq!(dl.back().unwrap(), &6);
937 /// ```
938 #[unstable(feature = "push_mut", issue = "135974")]
939 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_back` instead"]
940 pub fn push_back_mut(&mut self, elt: T) -> &mut T {
941 let mut node =
942 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
943 // SAFETY: node is a unique pointer to a node in self.alloc
944 unsafe {
945 self.push_back_node(node);
946 &mut node.as_mut().element
947 }
948 }
949
950 /// Removes the last element from a list and returns it, or `None` if
951 /// it is empty.
952 ///
953 /// This operation should compute in *O*(1) time.
954 ///
955 /// # Examples
956 ///
957 /// ```
958 /// use std::collections::LinkedList;
959 ///
960 /// let mut d = LinkedList::new();
961 /// assert_eq!(d.pop_back(), None);
962 /// d.push_back(1);
963 /// d.push_back(3);
964 /// assert_eq!(d.pop_back(), Some(3));
965 /// ```
966 #[stable(feature = "rust1", since = "1.0.0")]
967 pub fn pop_back(&mut self) -> Option<T> {
968 self.pop_back_node().map(Node::into_element)
969 }
970
971 /// Splits the list into two at the given index. Returns everything after the given index,
972 /// including the index.
973 ///
974 /// This operation should compute in *O*(*n*) time.
975 ///
976 /// # Panics
977 ///
978 /// Panics if `at > len`.
979 ///
980 /// # Examples
981 ///
982 /// ```
983 /// use std::collections::LinkedList;
984 ///
985 /// let mut d = LinkedList::new();
986 ///
987 /// d.push_front(1);
988 /// d.push_front(2);
989 /// d.push_front(3);
990 ///
991 /// let mut split = d.split_off(2);
992 ///
993 /// assert_eq!(split.pop_front(), Some(1));
994 /// assert_eq!(split.pop_front(), None);
995 /// ```
996 #[stable(feature = "rust1", since = "1.0.0")]
997 pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>
998 where
999 A: Clone,
1000 {
1001 let len = self.len();
1002 assert!(at <= len, "Cannot split off at a nonexistent index");
1003 if at == 0 {
1004 return mem::replace(self, Self::new_in(self.alloc.clone()));
1005 } else if at == len {
1006 return Self::new_in(self.alloc.clone());
1007 }
1008
1009 // Below, we iterate towards the `i-1`th node, either from the start or the end,
1010 // depending on which would be faster.
1011 let split_node = if at - 1 <= len - 1 - (at - 1) {
1012 let mut iter = self.iter_mut();
1013 // instead of skipping using .skip() (which creates a new struct),
1014 // we skip manually so we can access the head field without
1015 // depending on implementation details of Skip
1016 for _ in 0..at - 1 {
1017 iter.next();
1018 }
1019 iter.head
1020 } else {
1021 // better off starting from the end
1022 let mut iter = self.iter_mut();
1023 for _ in 0..len - 1 - (at - 1) {
1024 iter.next_back();
1025 }
1026 iter.tail
1027 };
1028 unsafe { self.split_off_after_node(split_node, at) }
1029 }
1030
1031 /// Removes the element at the given index and returns it.
1032 ///
1033 /// This operation should compute in *O*(*n*) time.
1034 ///
1035 /// # Panics
1036 /// Panics if at >= len
1037 ///
1038 /// # Examples
1039 ///
1040 /// ```
1041 /// #![feature(linked_list_remove)]
1042 /// use std::collections::LinkedList;
1043 ///
1044 /// let mut d = LinkedList::new();
1045 ///
1046 /// d.push_front(1);
1047 /// d.push_front(2);
1048 /// d.push_front(3);
1049 ///
1050 /// assert_eq!(d.remove(1), 2);
1051 /// assert_eq!(d.remove(0), 3);
1052 /// assert_eq!(d.remove(0), 1);
1053 /// ```
1054 #[unstable(feature = "linked_list_remove", issue = "69210")]
1055 #[rustc_confusables("delete", "take")]
1056 pub fn remove(&mut self, at: usize) -> T {
1057 let len = self.len();
1058 assert!(at < len, "Cannot remove at an index outside of the list bounds");
1059
1060 // Below, we iterate towards the node at the given index, either from
1061 // the start or the end, depending on which would be faster.
1062 let offset_from_end = len - at - 1;
1063 if at <= offset_from_end {
1064 let mut cursor = self.cursor_front_mut();
1065 for _ in 0..at {
1066 cursor.move_next();
1067 }
1068 cursor.remove_current().unwrap()
1069 } else {
1070 let mut cursor = self.cursor_back_mut();
1071 for _ in 0..offset_from_end {
1072 cursor.move_prev();
1073 }
1074 cursor.remove_current().unwrap()
1075 }
1076 }
1077
1078 /// Retains only the elements specified by the predicate.
1079 ///
1080 /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
1081 /// This method operates in place, visiting each element exactly once in the
1082 /// original order, and preserves the order of the retained elements.
1083 ///
1084 /// # Examples
1085 ///
1086 /// ```
1087 /// #![feature(linked_list_retain)]
1088 /// use std::collections::LinkedList;
1089 ///
1090 /// let mut d = LinkedList::new();
1091 ///
1092 /// d.push_front(1);
1093 /// d.push_front(2);
1094 /// d.push_front(3);
1095 ///
1096 /// d.retain(|&mut x| x % 2 == 0);
1097 ///
1098 /// assert_eq!(d.pop_front(), Some(2));
1099 /// assert_eq!(d.pop_front(), None);
1100 /// ```
1101 ///
1102 /// Because the elements are visited exactly once in the original order,
1103 /// external state may be used to decide which elements to keep.
1104 ///
1105 /// ```
1106 /// #![feature(linked_list_retain)]
1107 /// use std::collections::LinkedList;
1108 ///
1109 /// let mut d = LinkedList::new();
1110 ///
1111 /// d.push_front(1);
1112 /// d.push_front(2);
1113 /// d.push_front(3);
1114 ///
1115 /// let keep = [false, true, false];
1116 /// let mut iter = keep.iter();
1117 /// d.retain(|_| *iter.next().unwrap());
1118 /// assert_eq!(d.pop_front(), Some(2));
1119 /// assert_eq!(d.pop_front(), None);
1120 /// ```
1121 #[unstable(feature = "linked_list_retain", issue = "114135")]
1122 pub fn retain<F>(&mut self, mut f: F)
1123 where
1124 F: FnMut(&mut T) -> bool,
1125 {
1126 let mut cursor = self.cursor_front_mut();
1127 while let Some(node) = cursor.current() {
1128 if !f(node) {
1129 cursor.remove_current().unwrap();
1130 } else {
1131 cursor.move_next();
1132 }
1133 }
1134 }
1135
1136 /// Creates an iterator which uses a closure to determine if an element should be removed.
1137 ///
1138 /// If the closure returns `true`, the element is removed from the list and
1139 /// yielded. If the closure returns `false`, or panics, the element remains
1140 /// in the list and will not be yielded.
1141 ///
1142 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1143 /// or the iteration short-circuits, then the remaining elements will be retained.
1144 /// Use `extract_if().for_each(drop)` if you do not need the returned iterator.
1145 ///
1146 /// The iterator also lets you mutate the value of each element in the
1147 /// closure, regardless of whether you choose to keep or remove it.
1148 ///
1149 /// # Examples
1150 ///
1151 /// Splitting a list into even and odd values, reusing the original list:
1152 ///
1153 /// ```
1154 /// use std::collections::LinkedList;
1155 ///
1156 /// let mut numbers: LinkedList<u32> = LinkedList::new();
1157 /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
1158 ///
1159 /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<LinkedList<_>>();
1160 /// let odds = numbers;
1161 ///
1162 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
1163 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
1164 /// ```
1165 #[stable(feature = "extract_if", since = "1.87.0")]
1166 pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
1167 where
1168 F: FnMut(&mut T) -> bool,
1169 {
1170 // avoid borrow issues.
1171 let it = self.head;
1172 let old_len = self.len;
1173
1174 ExtractIf { list: self, it, pred: filter, idx: 0, old_len }
1175 }
1176}
1177
1178#[stable(feature = "rust1", since = "1.0.0")]
1179unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> {
1180 fn drop(&mut self) {
1181 struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>);
1182
1183 impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
1184 fn drop(&mut self) {
1185 // Continue the same loop we do below. This only runs when a destructor has
1186 // panicked. If another one panics this will abort.
1187 while self.0.pop_front_node().is_some() {}
1188 }
1189 }
1190
1191 // Wrap self so that if a destructor panics, we can try to keep looping
1192 let guard = DropGuard(self);
1193 while guard.0.pop_front_node().is_some() {}
1194 mem::forget(guard);
1195 }
1196}
1197
1198#[stable(feature = "rust1", since = "1.0.0")]
1199impl<'a, T> Iterator for Iter<'a, T> {
1200 type Item = &'a T;
1201
1202 #[inline]
1203 fn next(&mut self) -> Option<&'a T> {
1204 if self.len == 0 {
1205 None
1206 } else {
1207 self.head.map(|node| unsafe {
1208 // Need an unbound lifetime to get 'a
1209 let node = &*node.as_ptr();
1210 self.len -= 1;
1211 self.head = node.next;
1212 &node.element
1213 })
1214 }
1215 }
1216
1217 #[inline]
1218 fn size_hint(&self) -> (usize, Option<usize>) {
1219 (self.len, Some(self.len))
1220 }
1221
1222 #[inline]
1223 fn last(mut self) -> Option<&'a T> {
1224 self.next_back()
1225 }
1226}
1227
1228#[stable(feature = "rust1", since = "1.0.0")]
1229impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1230 #[inline]
1231 fn next_back(&mut self) -> Option<&'a T> {
1232 if self.len == 0 {
1233 None
1234 } else {
1235 self.tail.map(|node| unsafe {
1236 // Need an unbound lifetime to get 'a
1237 let node = &*node.as_ptr();
1238 self.len -= 1;
1239 self.tail = node.prev;
1240 &node.element
1241 })
1242 }
1243 }
1244}
1245
1246#[stable(feature = "rust1", since = "1.0.0")]
1247impl<T> ExactSizeIterator for Iter<'_, T> {}
1248
1249#[stable(feature = "fused", since = "1.26.0")]
1250impl<T> FusedIterator for Iter<'_, T> {}
1251
1252#[stable(feature = "default_iters", since = "1.70.0")]
1253impl<T> Default for Iter<'_, T> {
1254 /// Creates an empty `linked_list::Iter`.
1255 ///
1256 /// ```
1257 /// # use std::collections::linked_list;
1258 /// let iter: linked_list::Iter<'_, u8> = Default::default();
1259 /// assert_eq!(iter.len(), 0);
1260 /// ```
1261 fn default() -> Self {
1262 Iter { head: None, tail: None, len: 0, marker: Default::default() }
1263 }
1264}
1265
1266#[stable(feature = "rust1", since = "1.0.0")]
1267impl<'a, T> Iterator for IterMut<'a, T> {
1268 type Item = &'a mut T;
1269
1270 #[inline]
1271 fn next(&mut self) -> Option<&'a mut T> {
1272 if self.len == 0 {
1273 None
1274 } else {
1275 self.head.map(|node| unsafe {
1276 // Need an unbound lifetime to get 'a
1277 let node = &mut *node.as_ptr();
1278 self.len -= 1;
1279 self.head = node.next;
1280 &mut node.element
1281 })
1282 }
1283 }
1284
1285 #[inline]
1286 fn size_hint(&self) -> (usize, Option<usize>) {
1287 (self.len, Some(self.len))
1288 }
1289
1290 #[inline]
1291 fn last(mut self) -> Option<&'a mut T> {
1292 self.next_back()
1293 }
1294}
1295
1296#[stable(feature = "rust1", since = "1.0.0")]
1297impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1298 #[inline]
1299 fn next_back(&mut self) -> Option<&'a mut T> {
1300 if self.len == 0 {
1301 None
1302 } else {
1303 self.tail.map(|node| unsafe {
1304 // Need an unbound lifetime to get 'a
1305 let node = &mut *node.as_ptr();
1306 self.len -= 1;
1307 self.tail = node.prev;
1308 &mut node.element
1309 })
1310 }
1311 }
1312}
1313
1314#[stable(feature = "rust1", since = "1.0.0")]
1315impl<T> ExactSizeIterator for IterMut<'_, T> {}
1316
1317#[stable(feature = "fused", since = "1.26.0")]
1318impl<T> FusedIterator for IterMut<'_, T> {}
1319
1320#[stable(feature = "default_iters", since = "1.70.0")]
1321impl<T> Default for IterMut<'_, T> {
1322 fn default() -> Self {
1323 IterMut { head: None, tail: None, len: 0, marker: Default::default() }
1324 }
1325}
1326
1327/// A cursor over a `LinkedList`.
1328///
1329/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
1330///
1331/// Cursors always rest between two elements in the list, and index in a logically circular way.
1332/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1333/// tail of the list.
1334///
1335/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
1336#[unstable(feature = "linked_list_cursors", issue = "58533")]
1337pub struct Cursor<
1338 'a,
1339 T: 'a,
1340 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1341> {
1342 index: usize,
1343 current: Option<NonNull<Node<T>>>,
1344 list: &'a LinkedList<T, A>,
1345}
1346
1347#[unstable(feature = "linked_list_cursors", issue = "58533")]
1348impl<T, A: Allocator> Clone for Cursor<'_, T, A> {
1349 fn clone(&self) -> Self {
1350 let Cursor { index, current, list } = *self;
1351 Cursor { index, current, list }
1352 }
1353}
1354
1355#[unstable(feature = "linked_list_cursors", issue = "58533")]
1356impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> {
1357 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1358 f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
1359 }
1360}
1361
1362/// A cursor over a `LinkedList` with editing operations.
1363///
1364/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
1365/// safely mutate the list during iteration. This is because the lifetime of its yielded
1366/// references is tied to its own lifetime, instead of just the underlying list. This means
1367/// cursors cannot yield multiple elements at once.
1368///
1369/// Cursors always rest between two elements in the list, and index in a logically circular way.
1370/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1371/// tail of the list.
1372#[unstable(feature = "linked_list_cursors", issue = "58533")]
1373pub struct CursorMut<
1374 'a,
1375 T: 'a,
1376 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1377> {
1378 index: usize,
1379 current: Option<NonNull<Node<T>>>,
1380 list: &'a mut LinkedList<T, A>,
1381}
1382
1383#[unstable(feature = "linked_list_cursors", issue = "58533")]
1384impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> {
1385 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1386 f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
1387 }
1388}
1389
1390impl<'a, T, A: Allocator> Cursor<'a, T, A> {
1391 /// Returns the cursor position index within the `LinkedList`.
1392 ///
1393 /// This returns `None` if the cursor is currently pointing to the
1394 /// "ghost" non-element.
1395 #[must_use]
1396 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1397 pub fn index(&self) -> Option<usize> {
1398 let _ = self.current?;
1399 Some(self.index)
1400 }
1401
1402 /// Moves the cursor to the next element of the `LinkedList`.
1403 ///
1404 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1405 /// the first element of the `LinkedList`. If it is pointing to the last
1406 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1407 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1408 pub fn move_next(&mut self) {
1409 match self.current.take() {
1410 // We had no current element; the cursor was sitting at the start position
1411 // Next element should be the head of the list
1412 None => {
1413 self.current = self.list.head;
1414 self.index = 0;
1415 }
1416 // We had a previous element, so let's go to its next
1417 Some(current) => unsafe {
1418 self.current = current.as_ref().next;
1419 self.index += 1;
1420 },
1421 }
1422 }
1423
1424 /// Moves the cursor to the previous element of the `LinkedList`.
1425 ///
1426 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1427 /// the last element of the `LinkedList`. If it is pointing to the first
1428 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1429 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1430 pub fn move_prev(&mut self) {
1431 match self.current.take() {
1432 // No current. We're at the start of the list. Yield None and jump to the end.
1433 None => {
1434 self.current = self.list.tail;
1435 self.index = self.list.len().saturating_sub(1);
1436 }
1437 // Have a prev. Yield it and go to the previous element.
1438 Some(current) => unsafe {
1439 self.current = current.as_ref().prev;
1440 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1441 },
1442 }
1443 }
1444
1445 /// Returns a reference to the element that the cursor is currently
1446 /// pointing to.
1447 ///
1448 /// This returns `None` if the cursor is currently pointing to the
1449 /// "ghost" non-element.
1450 #[must_use]
1451 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1452 pub fn current(&self) -> Option<&'a T> {
1453 unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
1454 }
1455
1456 /// Returns a reference to the next element.
1457 ///
1458 /// If the cursor is pointing to the "ghost" non-element then this returns
1459 /// the first element of the `LinkedList`. If it is pointing to the last
1460 /// element of the `LinkedList` then this returns `None`.
1461 #[must_use]
1462 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1463 pub fn peek_next(&self) -> Option<&'a T> {
1464 unsafe {
1465 let next = match self.current {
1466 None => self.list.head,
1467 Some(current) => current.as_ref().next,
1468 };
1469 next.map(|next| &(*next.as_ptr()).element)
1470 }
1471 }
1472
1473 /// Returns a reference to the previous element.
1474 ///
1475 /// If the cursor is pointing to the "ghost" non-element then this returns
1476 /// the last element of the `LinkedList`. If it is pointing to the first
1477 /// element of the `LinkedList` then this returns `None`.
1478 #[must_use]
1479 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1480 pub fn peek_prev(&self) -> Option<&'a T> {
1481 unsafe {
1482 let prev = match self.current {
1483 None => self.list.tail,
1484 Some(current) => current.as_ref().prev,
1485 };
1486 prev.map(|prev| &(*prev.as_ptr()).element)
1487 }
1488 }
1489
1490 /// Provides a reference to the front element of the cursor's parent list,
1491 /// or None if the list is empty.
1492 #[must_use]
1493 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1494 #[rustc_confusables("first")]
1495 pub fn front(&self) -> Option<&'a T> {
1496 self.list.front()
1497 }
1498
1499 /// Provides a reference to the back element of the cursor's parent list,
1500 /// or None if the list is empty.
1501 #[must_use]
1502 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1503 #[rustc_confusables("last")]
1504 pub fn back(&self) -> Option<&'a T> {
1505 self.list.back()
1506 }
1507
1508 /// Provides a reference to the cursor's parent list.
1509 #[must_use]
1510 #[inline(always)]
1511 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1512 pub fn as_list(&self) -> &'a LinkedList<T, A> {
1513 self.list
1514 }
1515}
1516
1517impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1518 /// Returns the cursor position index within the `LinkedList`.
1519 ///
1520 /// This returns `None` if the cursor is currently pointing to the
1521 /// "ghost" non-element.
1522 #[must_use]
1523 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1524 pub fn index(&self) -> Option<usize> {
1525 let _ = self.current?;
1526 Some(self.index)
1527 }
1528
1529 /// Moves the cursor to the next element of the `LinkedList`.
1530 ///
1531 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1532 /// the first element of the `LinkedList`. If it is pointing to the last
1533 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1534 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1535 pub fn move_next(&mut self) {
1536 match self.current.take() {
1537 // We had no current element; the cursor was sitting at the start position
1538 // Next element should be the head of the list
1539 None => {
1540 self.current = self.list.head;
1541 self.index = 0;
1542 }
1543 // We had a previous element, so let's go to its next
1544 Some(current) => unsafe {
1545 self.current = current.as_ref().next;
1546 self.index += 1;
1547 },
1548 }
1549 }
1550
1551 /// Moves the cursor to the previous element of the `LinkedList`.
1552 ///
1553 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1554 /// the last element of the `LinkedList`. If it is pointing to the first
1555 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1556 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1557 pub fn move_prev(&mut self) {
1558 match self.current.take() {
1559 // No current. We're at the start of the list. Yield None and jump to the end.
1560 None => {
1561 self.current = self.list.tail;
1562 self.index = self.list.len().saturating_sub(1);
1563 }
1564 // Have a prev. Yield it and go to the previous element.
1565 Some(current) => unsafe {
1566 self.current = current.as_ref().prev;
1567 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1568 },
1569 }
1570 }
1571
1572 /// Returns a reference to the element that the cursor is currently
1573 /// pointing to.
1574 ///
1575 /// This returns `None` if the cursor is currently pointing to the
1576 /// "ghost" non-element.
1577 #[must_use]
1578 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1579 pub fn current(&mut self) -> Option<&mut T> {
1580 unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
1581 }
1582
1583 /// Returns a reference to the next element.
1584 ///
1585 /// If the cursor is pointing to the "ghost" non-element then this returns
1586 /// the first element of the `LinkedList`. If it is pointing to the last
1587 /// element of the `LinkedList` then this returns `None`.
1588 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1589 pub fn peek_next(&mut self) -> Option<&mut T> {
1590 unsafe {
1591 let next = match self.current {
1592 None => self.list.head,
1593 Some(current) => current.as_ref().next,
1594 };
1595 next.map(|next| &mut (*next.as_ptr()).element)
1596 }
1597 }
1598
1599 /// Returns a reference to the previous element.
1600 ///
1601 /// If the cursor is pointing to the "ghost" non-element then this returns
1602 /// the last element of the `LinkedList`. If it is pointing to the first
1603 /// element of the `LinkedList` then this returns `None`.
1604 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1605 pub fn peek_prev(&mut self) -> Option<&mut T> {
1606 unsafe {
1607 let prev = match self.current {
1608 None => self.list.tail,
1609 Some(current) => current.as_ref().prev,
1610 };
1611 prev.map(|prev| &mut (*prev.as_ptr()).element)
1612 }
1613 }
1614
1615 /// Returns a read-only cursor pointing to the current element.
1616 ///
1617 /// The lifetime of the returned `Cursor` is bound to that of the
1618 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1619 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
1620 #[must_use]
1621 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1622 pub fn as_cursor(&self) -> Cursor<'_, T, A> {
1623 Cursor { list: self.list, current: self.current, index: self.index }
1624 }
1625
1626 /// Provides a read-only reference to the cursor's parent list.
1627 ///
1628 /// The lifetime of the returned reference is bound to that of the
1629 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1630 /// `CursorMut` is frozen for the lifetime of the reference.
1631 #[must_use]
1632 #[inline(always)]
1633 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1634 pub fn as_list(&self) -> &LinkedList<T, A> {
1635 self.list
1636 }
1637}
1638
1639// Now the list editing operations
1640
1641impl<'a, T> CursorMut<'a, T> {
1642 /// Inserts the elements from the given `LinkedList` after the current one.
1643 ///
1644 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1645 /// inserted at the start of the `LinkedList`.
1646 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1647 pub fn splice_after(&mut self, list: LinkedList<T>) {
1648 unsafe {
1649 let Some((splice_head, splice_tail, splice_len)) = list.detach_all_nodes() else {
1650 return;
1651 };
1652 let node_next = match self.current {
1653 None => self.list.head,
1654 Some(node) => node.as_ref().next,
1655 };
1656 self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
1657 if self.current.is_none() {
1658 // The "ghost" non-element's index has changed.
1659 self.index = self.list.len;
1660 }
1661 }
1662 }
1663
1664 /// Inserts the elements from the given `LinkedList` before the current one.
1665 ///
1666 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1667 /// inserted at the end of the `LinkedList`.
1668 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1669 pub fn splice_before(&mut self, list: LinkedList<T>) {
1670 unsafe {
1671 let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1672 Some(parts) => parts,
1673 _ => return,
1674 };
1675 let node_prev = match self.current {
1676 None => self.list.tail,
1677 Some(node) => node.as_ref().prev,
1678 };
1679 self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
1680 self.index += splice_len;
1681 }
1682 }
1683}
1684
1685impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1686 /// Inserts a new element into the `LinkedList` after the current one.
1687 ///
1688 /// If the cursor is pointing at the "ghost" non-element then the new element is
1689 /// inserted at the front of the `LinkedList`.
1690 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1691 pub fn insert_after(&mut self, item: T) {
1692 unsafe {
1693 let spliced_node =
1694 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1695 let node_next = match self.current {
1696 None => self.list.head,
1697 Some(node) => node.as_ref().next,
1698 };
1699 self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
1700 if self.current.is_none() {
1701 // The "ghost" non-element's index has changed.
1702 self.index = self.list.len;
1703 }
1704 }
1705 }
1706
1707 /// Inserts a new element into the `LinkedList` before the current one.
1708 ///
1709 /// If the cursor is pointing at the "ghost" non-element then the new element is
1710 /// inserted at the end of the `LinkedList`.
1711 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1712 pub fn insert_before(&mut self, item: T) {
1713 unsafe {
1714 let spliced_node =
1715 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1716 let node_prev = match self.current {
1717 None => self.list.tail,
1718 Some(node) => node.as_ref().prev,
1719 };
1720 self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
1721 self.index += 1;
1722 }
1723 }
1724
1725 /// Removes the current element from the `LinkedList`.
1726 ///
1727 /// The element that was removed is returned, and the cursor is
1728 /// moved to point to the next element in the `LinkedList`.
1729 ///
1730 /// If the cursor is currently pointing to the "ghost" non-element then no element
1731 /// is removed and `None` is returned.
1732 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1733 pub fn remove_current(&mut self) -> Option<T> {
1734 let unlinked_node = self.current?;
1735 unsafe {
1736 self.current = unlinked_node.as_ref().next;
1737 self.list.unlink_node(unlinked_node);
1738 let unlinked_node = Box::from_raw_in(unlinked_node.as_ptr(), &self.list.alloc);
1739 Some(unlinked_node.element)
1740 }
1741 }
1742
1743 /// Removes the current element from the `LinkedList` without deallocating the list node.
1744 ///
1745 /// The node that was removed is returned as a new `LinkedList` containing only this node.
1746 /// The cursor is moved to point to the next element in the current `LinkedList`.
1747 ///
1748 /// If the cursor is currently pointing to the "ghost" non-element then no element
1749 /// is removed and `None` is returned.
1750 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1751 pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>>
1752 where
1753 A: Clone,
1754 {
1755 let mut unlinked_node = self.current?;
1756 unsafe {
1757 self.current = unlinked_node.as_ref().next;
1758 self.list.unlink_node(unlinked_node);
1759
1760 unlinked_node.as_mut().prev = None;
1761 unlinked_node.as_mut().next = None;
1762 Some(LinkedList {
1763 head: Some(unlinked_node),
1764 tail: Some(unlinked_node),
1765 len: 1,
1766 alloc: self.list.alloc.clone(),
1767 marker: PhantomData,
1768 })
1769 }
1770 }
1771
1772 /// Splits the list into two after the current element. This will return a
1773 /// new list consisting of everything after the cursor, with the original
1774 /// list retaining everything before.
1775 ///
1776 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1777 /// of the `LinkedList` are moved.
1778 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1779 pub fn split_after(&mut self) -> LinkedList<T, A>
1780 where
1781 A: Clone,
1782 {
1783 let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
1784 if self.index == self.list.len {
1785 // The "ghost" non-element's index has changed to 0.
1786 self.index = 0;
1787 }
1788 unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
1789 }
1790
1791 /// Splits the list into two before the current element. This will return a
1792 /// new list consisting of everything before the cursor, with the original
1793 /// list retaining everything after.
1794 ///
1795 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1796 /// of the `LinkedList` are moved.
1797 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1798 pub fn split_before(&mut self) -> LinkedList<T, A>
1799 where
1800 A: Clone,
1801 {
1802 let split_off_idx = self.index;
1803 self.index = 0;
1804 unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
1805 }
1806
1807 /// Appends an element to the front of the cursor's parent list. The node
1808 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1809 ///
1810 /// This operation should compute in *O*(1) time.
1811 // `push_front` continues to point to "ghost" when it adds a node to mimic
1812 // the behavior of `insert_before` on an empty list.
1813 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1814 pub fn push_front(&mut self, elt: T) {
1815 // Safety: We know that `push_front` does not change the position in
1816 // memory of other nodes. This ensures that `self.current` remains
1817 // valid.
1818 self.list.push_front(elt);
1819 self.index += 1;
1820 }
1821
1822 /// Appends an element to the back of the cursor's parent list. The node
1823 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1824 ///
1825 /// This operation should compute in *O*(1) time.
1826 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1827 #[rustc_confusables("push", "append")]
1828 pub fn push_back(&mut self, elt: T) {
1829 // Safety: We know that `push_back` does not change the position in
1830 // memory of other nodes. This ensures that `self.current` remains
1831 // valid.
1832 self.list.push_back(elt);
1833 if self.current().is_none() {
1834 // The index of "ghost" is the length of the list, so we just need
1835 // to increment self.index to reflect the new length of the list.
1836 self.index += 1;
1837 }
1838 }
1839
1840 /// Removes the first element from the cursor's parent list and returns it,
1841 /// or None if the list is empty. The element the cursor points to remains
1842 /// unchanged, unless it was pointing to the front element. In that case, it
1843 /// points to the new front element.
1844 ///
1845 /// This operation should compute in *O*(1) time.
1846 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1847 pub fn pop_front(&mut self) -> Option<T> {
1848 // We can't check if current is empty, we must check the list directly.
1849 // It is possible for `self.current == None` and the list to be
1850 // non-empty.
1851 if self.list.is_empty() {
1852 None
1853 } else {
1854 // We can't point to the node that we pop. Copying the behavior of
1855 // `remove_current`, we move on to the next node in the sequence.
1856 // If the list is of length 1 then we end pointing to the "ghost"
1857 // node at index 0, which is expected.
1858 if self.list.head == self.current {
1859 self.move_next();
1860 }
1861 // An element was removed before (or at) our current position, so
1862 // the index must be decremented. `saturating_sub` handles the
1863 // ghost node case where index could be 0.
1864 self.index = self.index.saturating_sub(1);
1865 self.list.pop_front()
1866 }
1867 }
1868
1869 /// Removes the last element from the cursor's parent list and returns it,
1870 /// or None if the list is empty. The element the cursor points to remains
1871 /// unchanged, unless it was pointing to the back element. In that case, it
1872 /// points to the "ghost" element.
1873 ///
1874 /// This operation should compute in *O*(1) time.
1875 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1876 #[rustc_confusables("pop")]
1877 pub fn pop_back(&mut self) -> Option<T> {
1878 if self.list.is_empty() {
1879 None
1880 } else {
1881 if self.list.tail == self.current {
1882 // The index now reflects the length of the list. It was the
1883 // length of the list minus 1, but now the list is 1 smaller. No
1884 // change is needed for `index`.
1885 self.current = None;
1886 } else if self.current.is_none() {
1887 self.index = self.list.len - 1;
1888 }
1889 self.list.pop_back()
1890 }
1891 }
1892
1893 /// Provides a reference to the front element of the cursor's parent list,
1894 /// or None if the list is empty.
1895 #[must_use]
1896 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1897 #[rustc_confusables("first")]
1898 pub fn front(&self) -> Option<&T> {
1899 self.list.front()
1900 }
1901
1902 /// Provides a mutable reference to the front element of the cursor's
1903 /// parent list, or None if the list is empty.
1904 #[must_use]
1905 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1906 pub fn front_mut(&mut self) -> Option<&mut T> {
1907 self.list.front_mut()
1908 }
1909
1910 /// Provides a reference to the back element of the cursor's parent list,
1911 /// or None if the list is empty.
1912 #[must_use]
1913 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1914 #[rustc_confusables("last")]
1915 pub fn back(&self) -> Option<&T> {
1916 self.list.back()
1917 }
1918
1919 /// Provides a mutable reference to back element of the cursor's parent
1920 /// list, or `None` if the list is empty.
1921 ///
1922 /// # Examples
1923 /// Building and mutating a list with a cursor, then getting the back element:
1924 /// ```
1925 /// #![feature(linked_list_cursors)]
1926 /// use std::collections::LinkedList;
1927 /// let mut dl = LinkedList::new();
1928 /// dl.push_front(3);
1929 /// dl.push_front(2);
1930 /// dl.push_front(1);
1931 /// let mut cursor = dl.cursor_front_mut();
1932 /// *cursor.current().unwrap() = 99;
1933 /// *cursor.back_mut().unwrap() = 0;
1934 /// let mut contents = dl.into_iter();
1935 /// assert_eq!(contents.next(), Some(99));
1936 /// assert_eq!(contents.next(), Some(2));
1937 /// assert_eq!(contents.next(), Some(0));
1938 /// assert_eq!(contents.next(), None);
1939 /// ```
1940 #[must_use]
1941 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1942 pub fn back_mut(&mut self) -> Option<&mut T> {
1943 self.list.back_mut()
1944 }
1945}
1946
1947/// An iterator produced by calling `extract_if` on LinkedList.
1948#[stable(feature = "extract_if", since = "1.87.0")]
1949#[must_use = "iterators are lazy and do nothing unless consumed; \
1950 use `extract_if().for_each(drop)` to remove and discard elements"]
1951pub struct ExtractIf<
1952 'a,
1953 T: 'a,
1954 F: 'a,
1955 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
1956> {
1957 list: &'a mut LinkedList<T, A>,
1958 it: Option<NonNull<Node<T>>>,
1959 pred: F,
1960 idx: usize,
1961 old_len: usize,
1962}
1963
1964#[stable(feature = "extract_if", since = "1.87.0")]
1965impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
1966where
1967 F: FnMut(&mut T) -> bool,
1968{
1969 type Item = T;
1970
1971 fn next(&mut self) -> Option<T> {
1972 while let Some(mut node) = self.it {
1973 unsafe {
1974 self.it = node.as_ref().next;
1975 self.idx += 1;
1976
1977 if (self.pred)(&mut node.as_mut().element) {
1978 // `unlink_node` is okay with aliasing `element` references.
1979 self.list.unlink_node(node);
1980 return Some(Box::from_raw_in(node.as_ptr(), &self.list.alloc).element);
1981 }
1982 }
1983 }
1984
1985 None
1986 }
1987
1988 fn size_hint(&self) -> (usize, Option<usize>) {
1989 (0, Some(self.old_len - self.idx))
1990 }
1991}
1992
1993#[stable(feature = "extract_if", since = "1.87.0")]
1994impl<T, F, A> fmt::Debug for ExtractIf<'_, T, F, A>
1995where
1996 T: fmt::Debug,
1997 A: Allocator,
1998{
1999 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2000 let peek = self.it.map(|node| unsafe { &node.as_ref().element });
2001 f.debug_struct("ExtractIf").field("peek", &peek).finish_non_exhaustive()
2002 }
2003}
2004
2005#[stable(feature = "rust1", since = "1.0.0")]
2006impl<T, A: Allocator> Iterator for IntoIter<T, A> {
2007 type Item = T;
2008
2009 #[inline]
2010 fn next(&mut self) -> Option<T> {
2011 self.list.pop_front()
2012 }
2013
2014 #[inline]
2015 fn size_hint(&self) -> (usize, Option<usize>) {
2016 (self.list.len, Some(self.list.len))
2017 }
2018}
2019
2020#[stable(feature = "rust1", since = "1.0.0")]
2021impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
2022 #[inline]
2023 fn next_back(&mut self) -> Option<T> {
2024 self.list.pop_back()
2025 }
2026}
2027
2028#[stable(feature = "rust1", since = "1.0.0")]
2029impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {}
2030
2031#[stable(feature = "fused", since = "1.26.0")]
2032impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
2033
2034#[stable(feature = "default_iters", since = "1.70.0")]
2035impl<T> Default for IntoIter<T> {
2036 /// Creates an empty `linked_list::IntoIter`.
2037 ///
2038 /// ```
2039 /// # use std::collections::linked_list;
2040 /// let iter: linked_list::IntoIter<u8> = Default::default();
2041 /// assert_eq!(iter.len(), 0);
2042 /// ```
2043 fn default() -> Self {
2044 LinkedList::new().into_iter()
2045 }
2046}
2047
2048#[stable(feature = "rust1", since = "1.0.0")]
2049impl<T> FromIterator<T> for LinkedList<T> {
2050 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
2051 let mut list = Self::new();
2052 list.extend(iter);
2053 list
2054 }
2055}
2056
2057#[stable(feature = "rust1", since = "1.0.0")]
2058impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
2059 type Item = T;
2060 type IntoIter = IntoIter<T, A>;
2061
2062 /// Consumes the list into an iterator yielding elements by value.
2063 #[inline]
2064 fn into_iter(self) -> IntoIter<T, A> {
2065 IntoIter { list: self }
2066 }
2067}
2068
2069#[stable(feature = "rust1", since = "1.0.0")]
2070impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
2071 type Item = &'a T;
2072 type IntoIter = Iter<'a, T>;
2073
2074 fn into_iter(self) -> Iter<'a, T> {
2075 self.iter()
2076 }
2077}
2078
2079#[stable(feature = "rust1", since = "1.0.0")]
2080impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
2081 type Item = &'a mut T;
2082 type IntoIter = IterMut<'a, T>;
2083
2084 fn into_iter(self) -> IterMut<'a, T> {
2085 self.iter_mut()
2086 }
2087}
2088
2089#[stable(feature = "rust1", since = "1.0.0")]
2090impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
2091 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2092 <Self as SpecExtend<I>>::spec_extend(self, iter);
2093 }
2094
2095 #[inline]
2096 fn extend_one(&mut self, elem: T) {
2097 self.push_back(elem);
2098 }
2099}
2100
2101impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> {
2102 default fn spec_extend(&mut self, iter: I) {
2103 iter.into_iter().for_each(move |elt| self.push_back(elt));
2104 }
2105}
2106
2107impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
2108 fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
2109 self.append(other);
2110 }
2111}
2112
2113#[stable(feature = "extend_ref", since = "1.2.0")]
2114impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> {
2115 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2116 self.extend(iter.into_iter().cloned());
2117 }
2118
2119 #[inline]
2120 fn extend_one(&mut self, &elem: &'a T) {
2121 self.push_back(elem);
2122 }
2123}
2124
2125#[stable(feature = "rust1", since = "1.0.0")]
2126impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> {
2127 fn eq(&self, other: &Self) -> bool {
2128 self.len() == other.len() && self.iter().eq(other)
2129 }
2130
2131 fn ne(&self, other: &Self) -> bool {
2132 self.len() != other.len() || self.iter().ne(other)
2133 }
2134}
2135
2136#[stable(feature = "rust1", since = "1.0.0")]
2137impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}
2138
2139#[stable(feature = "rust1", since = "1.0.0")]
2140impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> {
2141 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2142 self.iter().partial_cmp(other)
2143 }
2144}
2145
2146#[stable(feature = "rust1", since = "1.0.0")]
2147impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
2148 #[inline]
2149 fn cmp(&self, other: &Self) -> Ordering {
2150 self.iter().cmp(other)
2151 }
2152}
2153
2154#[stable(feature = "rust1", since = "1.0.0")]
2155impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
2156 fn clone(&self) -> Self {
2157 let mut list = Self::new_in(self.alloc.clone());
2158 list.extend(self.iter().cloned());
2159 list
2160 }
2161
2162 /// Overwrites the contents of `self` with a clone of the contents of `source`.
2163 ///
2164 /// This method is preferred over simply assigning `source.clone()` to `self`,
2165 /// as it avoids reallocation of the nodes of the linked list. Additionally,
2166 /// if the element type `T` overrides `clone_from()`, this will reuse the
2167 /// resources of `self`'s elements as well.
2168 fn clone_from(&mut self, source: &Self) {
2169 let mut source_iter = source.iter();
2170 if self.len() > source.len() {
2171 self.split_off(source.len());
2172 }
2173 for (elem, source_elem) in self.iter_mut().zip(&mut source_iter) {
2174 elem.clone_from(source_elem);
2175 }
2176 if !source_iter.is_empty() {
2177 self.extend(source_iter.cloned());
2178 }
2179 }
2180}
2181
2182#[stable(feature = "rust1", since = "1.0.0")]
2183impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> {
2184 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2185 f.debug_list().entries(self).finish()
2186 }
2187}
2188
2189#[stable(feature = "rust1", since = "1.0.0")]
2190impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
2191 fn hash<H: Hasher>(&self, state: &mut H) {
2192 state.write_length_prefix(self.len());
2193 for elt in self {
2194 elt.hash(state);
2195 }
2196 }
2197}
2198
2199#[stable(feature = "std_collections_from_array", since = "1.56.0")]
2200impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
2201 /// Converts a `[T; N]` into a `LinkedList<T>`.
2202 ///
2203 /// ```
2204 /// use std::collections::LinkedList;
2205 ///
2206 /// let list1 = LinkedList::from([1, 2, 3, 4]);
2207 /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
2208 /// assert_eq!(list1, list2);
2209 /// ```
2210 fn from(arr: [T; N]) -> Self {
2211 Self::from_iter(arr)
2212 }
2213}
2214
2215// Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
2216#[allow(dead_code)]
2217fn assert_covariance() {
2218 fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
2219 x
2220 }
2221 fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
2222 x
2223 }
2224 fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
2225 x
2226 }
2227}
2228
2229#[stable(feature = "rust1", since = "1.0.0")]
2230unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {}
2231
2232#[stable(feature = "rust1", since = "1.0.0")]
2233unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {}
2234
2235#[stable(feature = "rust1", since = "1.0.0")]
2236unsafe impl<T: Sync> Send for Iter<'_, T> {}
2237
2238#[stable(feature = "rust1", since = "1.0.0")]
2239unsafe impl<T: Sync> Sync for Iter<'_, T> {}
2240
2241#[stable(feature = "rust1", since = "1.0.0")]
2242unsafe impl<T: Send> Send for IterMut<'_, T> {}
2243
2244#[stable(feature = "rust1", since = "1.0.0")]
2245unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
2246
2247#[unstable(feature = "linked_list_cursors", issue = "58533")]
2248unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {}
2249
2250#[unstable(feature = "linked_list_cursors", issue = "58533")]
2251unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {}
2252
2253#[unstable(feature = "linked_list_cursors", issue = "58533")]
2254unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {}
2255
2256#[unstable(feature = "linked_list_cursors", issue = "58533")]
2257unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {}