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