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