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