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