//! 具有所属节点的双向链表。
//!
//! `LinkedList` 允许在恒定时间内在任一端推送和弹出元素。
//!
//! NOTE: 使用 [`Vec`] 或 [`VecDeque`] 几乎总是更好，因为基于数组的容器通常更快，内存效率更高，并且可以更好地利用 CPU 缓存。
//!
//!
//! [`Vec`]: crate::vec::Vec
//! [`VecDeque`]: super::vec_deque::VecDeque
//!
//!

#![stable(feature = "rust1", since = "1.0.0")]

use core::cmp::Ordering;
use core::fmt;
use core::hash::{Hash, Hasher};
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem;
use core::ptr::{NonNull, Unique};

use super::SpecExtend;
use crate::alloc::{Allocator, Global};
use crate::boxed::Box;

#[cfg(test)]
mod tests;

/// 具有所属节点的双向链表。
///
/// `LinkedList` 允许在恒定时间内在任一端推送和弹出元素。
///
/// 可以从数组初始化具有已知项列表的 `LinkedList`：
///
/// ```
/// use std::collections::LinkedList;
///
/// let list = LinkedList::from([1, 2, 3]);
/// ```
///
/// NOTE: 使用 [`Vec`] 或 [`VecDeque`] 几乎总是更好，因为基于数组的容器通常更快，内存效率更高，并且可以更好地利用 CPU 缓存。
///
///
/// [`Vec`]: crate::vec::Vec
/// [`VecDeque`]: super::vec_deque::VecDeque
///
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")]
#[rustc_insignificant_dtor]
pub struct LinkedList<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    alloc: A,
    marker: PhantomData<Box<Node<T>, A>>,
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: T,
}

/// `LinkedList` 元素上的迭代器。
///
/// 该 `struct` 由 [`LinkedList::iter()`] 创建。
/// 有关更多信息，请参见其文档。
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Iter<'a, T: 'a> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<&'a Node<T>>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Iter")
            .field(&*mem::ManuallyDrop::new(LinkedList {
                head: self.head,
                tail: self.tail,
                len: self.len,
                alloc: Global,
                marker: PhantomData,
            }))
            .field(&self.len)
            .finish()
    }
}

// FIXME(#26925) 删除以支持 `#[derive(Clone)]`
#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter { ..*self }
    }
}

/// `LinkedList` 元素上的可变迭代器。
///
/// 该 `struct` 由 [`LinkedList::iter_mut()`] 创建。
/// 有关更多信息，请参见其文档。
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IterMut<'a, T: 'a> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<&'a mut Node<T>>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("IterMut")
            .field(&*mem::ManuallyDrop::new(LinkedList {
                head: self.head,
                tail: self.tail,
                len: self.len,
                alloc: Global,
                marker: PhantomData,
            }))
            .field(&self.len)
            .finish()
    }
}

/// `LinkedList` 元素上的拥有的迭代器。
///
/// 这个 `struct` 是通过 [`LinkedList`] 上的 [`into_iter`] 方法创建的 (由 [`IntoIterator`] trait 提供)。
/// 有关更多信息，请参见其文档。
///
/// [`into_iter`]: LinkedList::into_iter
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    list: LinkedList<T, A>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("IntoIter").field(&self.list).finish()
    }
}

impl<T> Node<T> {
    fn new(element: T) -> Self {
        Node { next: None, prev: None, element }
    }

    fn into_element<A: Allocator>(self: Box<Self, A>) -> T {
        self.element
    }
}

// private 方法
impl<T, A: Allocator> LinkedList<T, A> {
    /// 将给定节点添加到列表的最前面。
    ///
    /// # Safety
    /// `node` 必须指向一个有效节点，该节点是使用列表分配器的 boxed。
    #[inline]
    unsafe fn push_front_node(&mut self, node: Unique<Node<T>>) {
        // 此方法注意不要对整个节点创建变量引用，以保持 `element` 中的别名指针的有效性。
        //
        unsafe {
            (*node.as_ptr()).next = self.head;
            (*node.as_ptr()).prev = None;
            let node = Some(NonNull::from(node));

            match self.head {
                None => self.tail = node,
                // 不创建新的可变 (unique!) 引用重叠的 `element`。
                Some(head) => (*head.as_ptr()).prev = node,
            }

            self.head = node;
            self.len += 1;
        }
    }

    /// 删除并返回列表前面的节点。
    #[inline]
    fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>> {
        // 此方法注意不要对整个节点创建变量引用，以保持 `element` 中的别名指针的有效性。
        //
        self.head.map(|node| unsafe {
            let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
            self.head = node.next;

            match self.head {
                None => self.tail = None,
                // 不创建新的可变 (unique!) 引用重叠的 `element`。
                Some(head) => (*head.as_ptr()).prev = None,
            }

            self.len -= 1;
            node
        })
    }

    /// 将给定节点添加到列表的后面。
    ///
    /// # Safety
    /// `node` 必须指向一个有效节点，该节点是使用列表分配器的 boxed。
    #[inline]
    unsafe fn push_back_node(&mut self, node: Unique<Node<T>>) {
        // 此方法注意不要对整个节点创建变量引用，以保持 `element` 中的别名指针的有效性。
        //
        unsafe {
            (*node.as_ptr()).next = None;
            (*node.as_ptr()).prev = self.tail;
            let node = Some(NonNull::from(node));

            match self.tail {
                None => self.head = node,
                // 不创建新的可变 (unique!) 引用重叠的 `element`。
                Some(tail) => (*tail.as_ptr()).next = node,
            }

            self.tail = node;
            self.len += 1;
        }
    }

    /// 删除并返回列表后面的节点。
    #[inline]
    fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>> {
        // 此方法注意不要对整个节点创建变量引用，以保持 `element` 中的别名指针的有效性。
        //
        self.tail.map(|node| unsafe {
            let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
            self.tail = node.prev;

            match self.tail {
                None => self.head = None,
                // 不创建新的可变 (unique!) 引用重叠的 `element`。
                Some(tail) => (*tail.as_ptr()).next = None,
            }

            self.len -= 1;
            node
        })
    }

    /// 从当前列表中取消指定节点的链接。
    ///
    /// 警告：这不会检查提供的节点是否属于当前列表。
    ///
    /// 此方法注意不要对 `element` 创建变量引用，以保持别名指针的有效性。
    ///
    #[inline]
    unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
        let node = unsafe { node.as_mut() }; // 现在这是我们的，我们可以创建一个 &mut。

        // 不创建新的可变 (unique!) 引用重叠的 `element`。
        match node.prev {
            Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
            // 这个节点是头节点
            None => self.head = node.next,
        };

        match node.next {
            Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
            // 这个节点是尾节点
            None => self.tail = node.prev,
        };

        self.len -= 1;
    }

    /// 在两个现有节点之间拼接一系列节点。
    ///
    /// 警告：这不会检查提供的节点是否属于两个现有列表。
    #[inline]
    unsafe fn splice_nodes(
        &mut self,
        existing_prev: Option<NonNull<Node<T>>>,
        existing_next: Option<NonNull<Node<T>>>,
        mut splice_start: NonNull<Node<T>>,
        mut splice_end: NonNull<Node<T>>,
        splice_length: usize,
    ) {
        // 此方法注意不要同时对整个节点创建多个变量引用，以保持 `element` 中的别名指针的有效性。
        //
        if let Some(mut existing_prev) = existing_prev {
            unsafe {
                existing_prev.as_mut().next = Some(splice_start);
            }
        } else {
            self.head = Some(splice_start);
        }
        if let Some(mut existing_next) = existing_next {
            unsafe {
                existing_next.as_mut().prev = Some(splice_end);
            }
        } else {
            self.tail = Some(splice_end);
        }
        unsafe {
            splice_start.as_mut().prev = existing_prev;
            splice_end.as_mut().next = existing_next;
        }

        self.len += splice_length;
    }

    /// 将一个链表中的所有节点分离为一系列节点。
    #[inline]
    fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
        let head = self.head.take();
        let tail = self.tail.take();
        let len = mem::replace(&mut self.len, 0);
        if let Some(head) = head {
            // SAFETY: 在 LinkedList 中，要么头部和尾部都是 None 因为列表是空的，或者头部和尾部都是 Some 因为列表被填充。
            //
            // 由于我们已经验证了头部是 Some，我们确定尾部也是 Some。
            let tail = unsafe { tail.unwrap_unchecked() };
            Some((head, tail, len))
        } else {
            None
        }
    }

    #[inline]
    unsafe fn split_off_before_node(
        &mut self,
        split_node: Option<NonNull<Node<T>>>,
        at: usize,
    ) -> Self
    where
        A: Clone,
    {
        // 拆分节点是第二部分的新头节点
        if let Some(mut split_node) = split_node {
            let first_part_head;
            let first_part_tail;
            unsafe {
                first_part_tail = split_node.as_mut().prev.take();
            }
            if let Some(mut tail) = first_part_tail {
                unsafe {
                    tail.as_mut().next = None;
                }
                first_part_head = self.head;
            } else {
                first_part_head = None;
            }

            let first_part = LinkedList {
                head: first_part_head,
                tail: first_part_tail,
                len: at,
                alloc: self.alloc.clone(),
                marker: PhantomData,
            };

            // 修复第二部分的头部 ptr
            self.head = Some(split_node);
            self.len = self.len - at;

            first_part
        } else {
            mem::replace(self, LinkedList::new_in(self.alloc.clone()))
        }
    }

    #[inline]
    unsafe fn split_off_after_node(
        &mut self,
        split_node: Option<NonNull<Node<T>>>,
        at: usize,
    ) -> Self
    where
        A: Clone,
    {
        // 拆分节点是第一部分的新尾节点，并拥有第二部分的头。
        //
        if let Some(mut split_node) = split_node {
            let second_part_head;
            let second_part_tail;
            unsafe {
                second_part_head = split_node.as_mut().next.take();
            }
            if let Some(mut head) = second_part_head {
                unsafe {
                    head.as_mut().prev = None;
                }
                second_part_tail = self.tail;
            } else {
                second_part_tail = None;
            }

            let second_part = LinkedList {
                head: second_part_head,
                tail: second_part_tail,
                len: self.len - at,
                alloc: self.alloc.clone(),
                marker: PhantomData,
            };

            // 修复第一部分的尾部点
            self.tail = Some(split_node);
            self.len = at;

            second_part
        } else {
            mem::replace(self, LinkedList::new_in(self.alloc.clone()))
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Default for LinkedList<T> {
    /// 创建一个空的 `LinkedList<T>`。
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T> LinkedList<T> {
    /// 创建一个空的 `LinkedList`。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let list: LinkedList<u32> = LinkedList::new();
    /// ```
    #[inline]
    #[rustc_const_stable(feature = "const_linked_list_new", since = "1.39.0")]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[must_use]
    pub const fn new() -> Self {
        LinkedList { head: None, tail: None, len: 0, alloc: Global, marker: PhantomData }
    }

    /// 将所有元素从 `other` 移动到列表的末尾。
    ///
    /// 这将重用 `other` 中的所有节点并将它们移到 `self` 中。
    /// 完成此操作后，`other` 变为空。
    ///
    /// 此操作应在 *O*(1) 时间和 *O*(1) 内存中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut list1 = LinkedList::new();
    /// list1.push_back('a');
    ///
    /// let mut list2 = LinkedList::new();
    /// list2.push_back('b');
    /// list2.push_back('c');
    ///
    /// list1.append(&mut list2);
    ///
    /// let mut iter = list1.iter();
    /// assert_eq!(iter.next(), Some(&'a'));
    /// assert_eq!(iter.next(), Some(&'b'));
    /// assert_eq!(iter.next(), Some(&'c'));
    /// assert!(iter.next().is_none());
    ///
    /// assert!(list2.is_empty());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn append(&mut self, other: &mut Self) {
        match self.tail {
            None => mem::swap(self, other),
            Some(mut tail) => {
                // `as_mut` 在这里没问题，因为我们可以独占访问两个列表的全部内容。
                //
                if let Some(mut other_head) = other.head.take() {
                    unsafe {
                        tail.as_mut().next = Some(other_head);
                        other_head.as_mut().prev = Some(tail);
                    }

                    self.tail = other.tail.take();
                    self.len += mem::replace(&mut other.len, 0);
                }
            }
        }
    }
}

impl<T, A: Allocator> LinkedList<T, A> {
    /// 创建一个空的 `LinkedList<T, A>`。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(allocator_api)]
    ///
    /// use std::alloc::System;
    /// use std::collections::LinkedList;
    ///
    /// let list: LinkedList<u32, _> = LinkedList::new_in(System);
    /// ```
    #[inline]
    #[unstable(feature = "allocator_api", issue = "32838")]
    pub const fn new_in(alloc: A) -> Self {
        LinkedList { head: None, tail: None, len: 0, alloc, marker: PhantomData }
    }
    /// 提供一个正向迭代器。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut list: LinkedList<u32> = LinkedList::new();
    ///
    /// list.push_back(0);
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let mut iter = list.iter();
    /// assert_eq!(iter.next(), Some(&0));
    /// assert_eq!(iter.next(), Some(&1));
    /// assert_eq!(iter.next(), Some(&2));
    /// assert_eq!(iter.next(), None);
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
    }

    /// 提供具有可变引用的正向迭代器。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut list: LinkedList<u32> = LinkedList::new();
    ///
    /// list.push_back(0);
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// for element in list.iter_mut() {
    ///     *element += 10;
    /// }
    ///
    /// let mut iter = list.iter();
    /// assert_eq!(iter.next(), Some(&10));
    /// assert_eq!(iter.next(), Some(&11));
    /// assert_eq!(iter.next(), Some(&12));
    /// assert_eq!(iter.next(), None);
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
    }

    /// 在前元素处提供游标。
    ///
    /// 如果列表为空，则游标指向 "ghost" 非元素。
    #[inline]
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn cursor_front(&self) -> Cursor<'_, T, A> {
        Cursor { index: 0, current: self.head, list: self }
    }

    /// 在前面的元素上为游标提供编辑操作。
    ///
    /// 如果列表为空，则游标指向 "ghost" 非元素。
    #[inline]
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A> {
        CursorMut { index: 0, current: self.head, list: self }
    }

    /// 在 back 元素上提供游标。
    ///
    /// 如果列表为空，则游标指向 "ghost" 非元素。
    #[inline]
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn cursor_back(&self) -> Cursor<'_, T, A> {
        Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
    }

    /// 在 back 元素上为游标提供编辑操作。
    ///
    /// 如果列表为空，则游标指向 "ghost" 非元素。
    #[inline]
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A> {
        CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
    }

    /// 如果 `LinkedList` 为空，则返回 `true`。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    /// assert!(dl.is_empty());
    ///
    /// dl.push_front("foo");
    /// assert!(!dl.is_empty());
    /// ```
    #[inline]
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    /// 返回 `LinkedList` 的长度。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    ///
    /// dl.push_front(2);
    /// assert_eq!(dl.len(), 1);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.len(), 2);
    ///
    /// dl.push_back(3);
    /// assert_eq!(dl.len(), 3);
    /// ```
    #[inline]
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn len(&self) -> usize {
        self.len
    }

    /// 从 `LinkedList` 删除所有元素。
    ///
    /// 此运算应在 *O*(*n*) 时间中计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    ///
    /// dl.push_front(2);
    /// dl.push_front(1);
    /// assert_eq!(dl.len(), 2);
    /// assert_eq!(dl.front(), Some(&1));
    ///
    /// dl.clear();
    /// assert_eq!(dl.len(), 0);
    /// assert_eq!(dl.front(), None);
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn clear(&mut self) {
        // 我们需要丢弃节点，同时保留 self.alloc 我们可以通过将 (head, tail, len) 移动到一个新的列表中来做到这一点，借用 self.alloc
        //
        drop(LinkedList {
            head: self.head.take(),
            tail: self.tail.take(),
            len: mem::take(&mut self.len),
            alloc: &self.alloc,
            marker: PhantomData,
        });
    }

    /// 如果 `LinkedList` 包含等于给定值的元素，则返回 `true`。
    ///
    ///
    /// 此操作应在 *O*(*n*) 时间内线性计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut list: LinkedList<u32> = LinkedList::new();
    ///
    /// list.push_back(0);
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// assert_eq!(list.contains(&0), true);
    /// assert_eq!(list.contains(&10), false);
    /// ```
    #[stable(feature = "linked_list_contains", since = "1.12.0")]
    pub fn contains(&self, x: &T) -> bool
    where
        T: PartialEq<T>,
    {
        self.iter().any(|e| e == x)
    }

    /// 提供对前元素的引用，如果列表为空，则为 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    /// assert_eq!(dl.front(), None);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.front(), Some(&1));
    /// ```
    #[inline]
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front(&self) -> Option<&T> {
        unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
    }

    /// 提供对前元素的可变引用，如果列表为空，则为 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    /// assert_eq!(dl.front(), None);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.front(), Some(&1));
    ///
    /// match dl.front_mut() {
    ///     None => {},
    ///     Some(x) => *x = 5,
    /// }
    /// assert_eq!(dl.front(), Some(&5));
    /// ```
    #[inline]
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
    }

    /// 提供对 back 元素的引用，如果列表为空，则提供 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    /// assert_eq!(dl.back(), None);
    ///
    /// dl.push_back(1);
    /// assert_eq!(dl.back(), Some(&1));
    /// ```
    #[inline]
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back(&self) -> Option<&T> {
        unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
    }

    /// 提供对 back 元素的可变引用，如果列表为空，则为 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    /// assert_eq!(dl.back(), None);
    ///
    /// dl.push_back(1);
    /// assert_eq!(dl.back(), Some(&1));
    ///
    /// match dl.back_mut() {
    ///     None => {},
    ///     Some(x) => *x = 5,
    /// }
    /// assert_eq!(dl.back(), Some(&5));
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
    }

    /// 首先在列表中添加一个元素。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut dl = LinkedList::new();
    ///
    /// dl.push_front(2);
    /// assert_eq!(dl.front().unwrap(), &2);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.front().unwrap(), &1);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn push_front(&mut self, elt: T) {
        let node = Box::new_in(Node::new(elt), &self.alloc);
        let node_ptr = Unique::from(Box::leak(node));
        // SAFETY: node_ptr 是指向我们 boxed 和 self.alloc 的节点的唯一指针
        unsafe {
            self.push_front_node(node_ptr);
        }
    }

    /// 删除第一个元素并返回它; 如果列表为空，则返回 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut d = LinkedList::new();
    /// assert_eq!(d.pop_front(), None);
    ///
    /// d.push_front(1);
    /// d.push_front(3);
    /// assert_eq!(d.pop_front(), Some(3));
    /// assert_eq!(d.pop_front(), Some(1));
    /// assert_eq!(d.pop_front(), None);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn pop_front(&mut self) -> Option<T> {
        self.pop_front_node().map(Node::into_element)
    }

    /// 将元素追加到列表的后面。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut d = LinkedList::new();
    /// d.push_back(1);
    /// d.push_back(3);
    /// assert_eq!(3, *d.back().unwrap());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn push_back(&mut self, elt: T) {
        let node = Box::new_in(Node::new(elt), &self.alloc);
        let node_ptr = Unique::from(Box::leak(node));
        // SAFETY: node_ptr 是指向我们 boxed 和 self.alloc 的节点的唯一指针
        unsafe {
            self.push_back_node(node_ptr);
        }
    }

    /// 从列表中删除最后一个元素并返回它; 如果它为空，则返回 `None`。
    ///
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut d = LinkedList::new();
    /// assert_eq!(d.pop_back(), None);
    /// d.push_back(1);
    /// d.push_back(3);
    /// assert_eq!(d.pop_back(), Some(3));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn pop_back(&mut self) -> Option<T> {
        self.pop_back_node().map(Node::into_element)
    }

    /// 在给定的索引处将列表分为两部分。
    /// 返回给定索引之后的所有内容，包括索引。
    ///
    /// 此运算应在 *O*(*n*) 时间中计算。
    ///
    /// # Panics
    ///
    /// 如果为 `at > len`，就会出现 panics。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let mut d = LinkedList::new();
    ///
    /// d.push_front(1);
    /// d.push_front(2);
    /// d.push_front(3);
    ///
    /// let mut split = d.split_off(2);
    ///
    /// assert_eq!(split.pop_front(), Some(1));
    /// assert_eq!(split.pop_front(), None);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>
    where
        A: Clone,
    {
        let len = self.len();
        assert!(at <= len, "Cannot split off at a nonexistent index");
        if at == 0 {
            return mem::replace(self, Self::new_in(self.alloc.clone()));
        } else if at == len {
            return Self::new_in(self.alloc.clone());
        }

        // 在下面，我们从头到尾迭代第 i-1 个节点，具体取决于哪个会更快。
        //
        let split_node = if at - 1 <= len - 1 - (at - 1) {
            let mut iter = self.iter_mut();
            // 无需跳过使用 .skip() (它会创建一个新的结构体) 的方法，而是手动跳过，因此我们可以访问 head 字段，而无需依赖于 Skip 的实现细节
            //
            //
            for _ in 0..at - 1 {
                iter.next();
            }
            iter.head
        } else {
            // 从头开始更好
            let mut iter = self.iter_mut();
            for _ in 0..len - 1 - (at - 1) {
                iter.next_back();
            }
            iter.tail
        };
        unsafe { self.split_off_after_node(split_node, at) }
    }

    /// 删除给定索引处的元素并返回它。
    ///
    /// 此运算应在 *O*(*n*) 时间中计算。
    ///
    /// # Panics
    /// 如果 >= len 就会出现 panics
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(linked_list_remove)]
    /// use std::collections::LinkedList;
    ///
    /// let mut d = LinkedList::new();
    ///
    /// d.push_front(1);
    /// d.push_front(2);
    /// d.push_front(3);
    ///
    /// assert_eq!(d.remove(1), 2);
    /// assert_eq!(d.remove(0), 3);
    /// assert_eq!(d.remove(0), 1);
    /// ```
    #[unstable(feature = "linked_list_remove", issue = "69210")]
    pub fn remove(&mut self, at: usize) -> T {
        let len = self.len();
        assert!(at < len, "Cannot remove at an index outside of the list bounds");

        // 下面，我们从头到尾迭代给定索引处的节点，具体取决于哪个会更快。
        //
        let offset_from_end = len - at - 1;
        if at <= offset_from_end {
            let mut cursor = self.cursor_front_mut();
            for _ in 0..at {
                cursor.move_next();
            }
            cursor.remove_current().unwrap()
        } else {
            let mut cursor = self.cursor_back_mut();
            for _ in 0..offset_from_end {
                cursor.move_prev();
            }
            cursor.remove_current().unwrap()
        }
    }

    /// 创建一个迭代器，该迭代器使用闭包确定是否应删除元素。
    ///
    /// 如果闭包返回 true，则删除并生成元素。
    /// 如果闭包返回 false，则该元素将保留在列表中，并且不会由迭代器产生。
    ///
    /// 请注意，无论选择保留还是删除 `drain_filter`，您都可以对过滤器闭包中的每个元素进行可变的。
    ///
    ///
    /// # Examples
    ///
    /// 将列表分成偶数和几率，重新使用原始列表：
    ///
    /// ```
    /// #![feature(drain_filter)]
    /// use std::collections::LinkedList;
    ///
    /// let mut numbers: LinkedList<u32> = LinkedList::new();
    /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
    ///
    /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
    /// let odds = numbers;
    ///
    /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
    /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
    /// ```
    ///
    #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
    pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A>
    where
        F: FnMut(&mut T) -> bool,
    {
        // 避免借用问题。
        let it = self.head;
        let old_len = self.len;

        DrainFilter { list: self, it, pred: filter, idx: 0, old_len }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> {
    fn drop(&mut self) {
        struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>);

        impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
            fn drop(&mut self) {
                // 继续执行以下相同的循环。这仅在析构函数崩溃时运行。
                // 如果另一个 panics 了，则会中止。
                while self.0.pop_front_node().is_some() {}
            }
        }

        // 包装 self，以便如果析构函数出现 panic，我们可以尝试继续循环
        let guard = DropGuard(self);
        while guard.0.pop_front_node().is_some() {}
        mem::forget(guard);
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| unsafe {
                // 需要无限的生命周期来获得
                let node = &*node.as_ptr();
                self.len -= 1;
                self.head = node.next;
                &node.element
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<&'a T> {
        self.next_back()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|node| unsafe {
                // 需要无限的生命周期来获得
                let node = &*node.as_ptr();
                self.len -= 1;
                self.tail = node.prev;
                &node.element
            })
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> ExactSizeIterator for Iter<'_, T> {}

#[stable(feature = "fused", since = "1.26.0")]
impl<T> FusedIterator for Iter<'_, T> {}

#[stable(feature = "default_iters", since = "1.70.0")]
impl<T> Default for Iter<'_, T> {
    /// 创建一个空的 `linked_list::Iter`。
    ///
    /// ```
    /// # use std::collections::linked_list;
    /// let iter: linked_list::Iter<'_, u8> = Default::default();
    /// assert_eq!(iter.len(), 0);
    /// ```
    fn default() -> Self {
        Iter { head: None, tail: None, len: 0, marker: Default::default() }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| unsafe {
                // 需要无限的生命周期来获得
                let node = &mut *node.as_ptr();
                self.len -= 1;
                self.head = node.next;
                &mut node.element
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<&'a mut T> {
        self.next_back()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<&'a mut T> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|node| unsafe {
                // 需要无限的生命周期来获得
                let node = &mut *node.as_ptr();
                self.len -= 1;
                self.tail = node.prev;
                &mut node.element
            })
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> ExactSizeIterator for IterMut<'_, T> {}

#[stable(feature = "fused", since = "1.26.0")]
impl<T> FusedIterator for IterMut<'_, T> {}

#[stable(feature = "default_iters", since = "1.70.0")]
impl<T> Default for IterMut<'_, T> {
    fn default() -> Self {
        IterMut { head: None, tail: None, len: 0, marker: Default::default() }
    }
}

/// `LinkedList` 上的游标。
///
/// `Cursor` 类似于迭代器，不同之处在于它可以自由地来回查找。
///
/// 游标始终位于列表中的两个元素之间，并以逻辑循环的方式进行索引。
/// 为了适应这一点，有一个 "ghost" 非元素在列表的开头和结尾之间产生 `None`。
///
///
/// 创建后，游标从列表的开头开始，如果列表为空，则从 "ghost" 非元素开始。
#[unstable(feature = "linked_list_cursors", issue = "58533")]
pub struct Cursor<
    'a,
    T: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    index: usize,
    current: Option<NonNull<Node<T>>>,
    list: &'a LinkedList<T, A>,
}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
impl<T, A: Allocator> Clone for Cursor<'_, T, A> {
    fn clone(&self) -> Self {
        let Cursor { index, current, list } = *self;
        Cursor { index, current, list }
    }
}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
    }
}

/// 带有编辑操作的 `LinkedList` 上的游标。
///
/// `Cursor` 类似于迭代器，不同之处在于它可以自由地来回查找，并且可以在迭代过程中安全地修改列表。
/// 这是因为其产生的引用的生命周期与其自身的生命周期相关联，而不仅仅是底层列表。
/// 这意味着游标不能一次产生多个元素。
///
/// 游标始终位于列表中的两个元素之间，并以逻辑循环的方式进行索引。
/// 为了适应这一点，有一个 "ghost" 非元素在列表的开头和结尾之间产生 `None`。
///
///
#[unstable(feature = "linked_list_cursors", issue = "58533")]
pub struct CursorMut<
    'a,
    T: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    index: usize,
    current: Option<NonNull<Node<T>>>,
    list: &'a mut LinkedList<T, A>,
}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
    }
}

impl<'a, T, A: Allocator> Cursor<'a, T, A> {
    /// 返回 `LinkedList` 中的游标位置索引。
    ///
    /// 如果游标当前指向 "ghost" 非元素，则返回 `None`。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn index(&self) -> Option<usize> {
        let _ = self.current?;
        Some(self.index)
    }

    /// 将游标移动到 `LinkedList` 的下一个元素。
    ///
    /// 如果游标指向 "ghost" 非元素，那么它将移动到 `LinkedList` 的第一个元素。
    /// 如果它指向 `LinkedList` 的最后一个元素，那么它将把它移到 "ghost" 非元素。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn move_next(&mut self) {
        match self.current.take() {
            // 我们没有当前的要素； 游标位于开始位置，下一个元素应位于列表的开头
            //
            None => {
                self.current = self.list.head;
                self.index = 0;
            }
            // 我们有一个上一个元素，所以让我们转到下一个元素
            Some(current) => unsafe {
                self.current = current.as_ref().next;
                self.index += 1;
            },
        }
    }

    /// 将游标移动到 `LinkedList` 的上一个元素。
    ///
    /// 如果游标指向 "ghost" 非元素，那么它将移动到 `LinkedList` 的最后一个元素。
    /// 如果它指向 `LinkedList` 的第一个元素，那么它将把它移到 "ghost" 非元素。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn move_prev(&mut self) {
        match self.current.take() {
            // 不是 current。我们位于列表的开头。Yield None 并跳到最后。
            None => {
                self.current = self.list.tail;
                self.index = self.list.len().checked_sub(1).unwrap_or(0);
            }
            // 有上一个。Yield 并转到上一个元素。
            Some(current) => unsafe {
                self.current = current.as_ref().prev;
                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
            },
        }
    }

    /// 返回对游标当前指向的元素的引用。
    ///
    /// 如果游标当前指向 "ghost" 非元素，则返回 `None`。
    ///
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn current(&self) -> Option<&'a T> {
        unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
    }

    /// 返回下一个元素的引用。
    ///
    /// 如果游标指向 "ghost" 非元素，则返回 `LinkedList` 的第一个元素。
    /// 如果它指向 `LinkedList` 的最后一个元素，则返回 `None`。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn peek_next(&self) -> Option<&'a T> {
        unsafe {
            let next = match self.current {
                None => self.list.head,
                Some(current) => current.as_ref().next,
            };
            next.map(|next| &(*next.as_ptr()).element)
        }
    }

    /// 返回上一个元素的引用。
    ///
    /// 如果游标指向 "ghost" 非元素，则返回 `LinkedList` 的最后一个元素。
    /// 如果它指向 `LinkedList` 的第一个元素，则返回 `None`。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn peek_prev(&self) -> Option<&'a T> {
        unsafe {
            let prev = match self.current {
                None => self.list.tail,
                Some(current) => current.as_ref().prev,
            };
            prev.map(|prev| &(*prev.as_ptr()).element)
        }
    }

    /// 提供对游标父列表前元素的引用，如果列表为空，则为 None。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn front(&self) -> Option<&'a T> {
        self.list.front()
    }

    /// 提供对游标父列表的后部元素的引用，如果列表为空，则为 None。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn back(&self) -> Option<&'a T> {
        self.list.back()
    }
}

impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
    /// 返回 `LinkedList` 中的游标位置索引。
    ///
    /// 如果游标当前指向 "ghost" 非元素，则返回 `None`。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn index(&self) -> Option<usize> {
        let _ = self.current?;
        Some(self.index)
    }

    /// 将游标移动到 `LinkedList` 的下一个元素。
    ///
    /// 如果游标指向 "ghost" 非元素，那么它将移动到 `LinkedList` 的第一个元素。
    /// 如果它指向 `LinkedList` 的最后一个元素，那么它将把它移到 "ghost" 非元素。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn move_next(&mut self) {
        match self.current.take() {
            // 我们没有当前的要素； 游标位于开始位置，下一个元素应位于列表的开头
            //
            None => {
                self.current = self.list.head;
                self.index = 0;
            }
            // 我们有一个上一个元素，所以让我们转到下一个元素
            Some(current) => unsafe {
                self.current = current.as_ref().next;
                self.index += 1;
            },
        }
    }

    /// 将游标移动到 `LinkedList` 的上一个元素。
    ///
    /// 如果游标指向 "ghost" 非元素，那么它将移动到 `LinkedList` 的最后一个元素。
    /// 如果它指向 `LinkedList` 的第一个元素，那么它将把它移到 "ghost" 非元素。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn move_prev(&mut self) {
        match self.current.take() {
            // 不是 current。我们位于列表的开头。Yield None 并跳到最后。
            None => {
                self.current = self.list.tail;
                self.index = self.list.len().checked_sub(1).unwrap_or(0);
            }
            // 有上一个。Yield 并转到上一个元素。
            Some(current) => unsafe {
                self.current = current.as_ref().prev;
                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
            },
        }
    }

    /// 返回对游标当前指向的元素的引用。
    ///
    /// 如果游标当前指向 "ghost" 非元素，则返回 `None`。
    ///
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn current(&mut self) -> Option<&mut T> {
        unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
    }

    /// 返回下一个元素的引用。
    ///
    /// 如果游标指向 "ghost" 非元素，则返回 `LinkedList` 的第一个元素。
    /// 如果它指向 `LinkedList` 的最后一个元素，则返回 `None`。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn peek_next(&mut self) -> Option<&mut T> {
        unsafe {
            let next = match self.current {
                None => self.list.head,
                Some(current) => current.as_ref().next,
            };
            next.map(|next| &mut (*next.as_ptr()).element)
        }
    }

    /// 返回上一个元素的引用。
    ///
    /// 如果游标指向 "ghost" 非元素，则返回 `LinkedList` 的最后一个元素。
    /// 如果它指向 `LinkedList` 的第一个元素，则返回 `None`。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn peek_prev(&mut self) -> Option<&mut T> {
        unsafe {
            let prev = match self.current {
                None => self.list.tail,
                Some(current) => current.as_ref().prev,
            };
            prev.map(|prev| &mut (*prev.as_ptr()).element)
        }
    }

    /// 返回指向当前元素的只读游标。
    ///
    /// 返回的 `Cursor` 的生命周期与 `CursorMut` 的生命周期绑定在一起，这意味着它不能超过 `CursorMut` 的生命周期，并且 `CursorMut` 被冻结为 `Cursor` 的生命周期。
    ///
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn as_cursor(&self) -> Cursor<'_, T, A> {
        Cursor { list: self.list, current: self.current, index: self.index }
    }
}

// 现在列表编辑操作

impl<'a, T> CursorMut<'a, T> {
    /// 将给定 `LinkedList` 中的元素插入当前元素之后。
    ///
    /// 如果游标指向 "ghost" 非元素，则新元素将插入 `LinkedList` 的开头。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn splice_after(&mut self, list: LinkedList<T>) {
        unsafe {
            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
                Some(parts) => parts,
                _ => return,
            };
            let node_next = match self.current {
                None => self.list.head,
                Some(node) => node.as_ref().next,
            };
            self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
            if self.current.is_none() {
                // "ghost" 非元素的索引已更改。
                self.index = self.list.len;
            }
        }
    }

    /// 将给定 `LinkedList` 中的元素插入到当前元素之前。
    ///
    /// 如果游标指向 "ghost" 非元素，则新元素将插入 `LinkedList` 的末尾。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn splice_before(&mut self, list: LinkedList<T>) {
        unsafe {
            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
                Some(parts) => parts,
                _ => return,
            };
            let node_prev = match self.current {
                None => self.list.tail,
                Some(node) => node.as_ref().prev,
            };
            self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
            self.index += splice_len;
        }
    }
}

impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
    /// 在当前元素之后将新元素插入 `LinkedList`。
    ///
    /// 如果游标指向 "ghost" 非元素，则将新元素插入 `LinkedList` 的前面。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn insert_after(&mut self, item: T) {
        unsafe {
            let spliced_node = Box::leak(Box::new_in(Node::new(item), &self.list.alloc)).into();
            let node_next = match self.current {
                None => self.list.head,
                Some(node) => node.as_ref().next,
            };
            self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
            if self.current.is_none() {
                // "ghost" 非元素的索引已更改。
                self.index = self.list.len;
            }
        }
    }

    /// 在当前元素之前在 `LinkedList` 中插入一个新元素。
    ///
    /// 如果游标指向 "ghost" 非元素，则将新元素插入 `LinkedList` 的末尾。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn insert_before(&mut self, item: T) {
        unsafe {
            let spliced_node = Box::leak(Box::new_in(Node::new(item), &self.list.alloc)).into();
            let node_prev = match self.current {
                None => self.list.tail,
                Some(node) => node.as_ref().prev,
            };
            self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
            self.index += 1;
        }
    }

    /// 从 `LinkedList` 中删除当前元素。
    ///
    /// 返回已删除的元素，并移动游标以指向 `LinkedList` 中的下一个元素。
    ///
    ///
    /// 如果游标当前指向 "ghost" 非元素，则不删除任何元素，并返回 `None`。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn remove_current(&mut self) -> Option<T> {
        let unlinked_node = self.current?;
        unsafe {
            self.current = unlinked_node.as_ref().next;
            self.list.unlink_node(unlinked_node);
            let unlinked_node = Box::from_raw(unlinked_node.as_ptr());
            Some(unlinked_node.element)
        }
    }

    /// 在不释放列表节点的情况下从 `LinkedList` 中删除当前元素。
    ///
    /// 被删除的节点作为仅包含该节点的新 `LinkedList` 返回。
    /// 游标将移至当前 `LinkedList` 中的下一个元素。
    ///
    /// 如果游标当前指向 "ghost" 非元素，则不删除任何元素，并返回 `None`。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>>
    where
        A: Clone,
    {
        let mut unlinked_node = self.current?;
        unsafe {
            self.current = unlinked_node.as_ref().next;
            self.list.unlink_node(unlinked_node);

            unlinked_node.as_mut().prev = None;
            unlinked_node.as_mut().next = None;
            Some(LinkedList {
                head: Some(unlinked_node),
                tail: Some(unlinked_node),
                len: 1,
                alloc: self.list.alloc.clone(),
                marker: PhantomData,
            })
        }
    }

    /// 在当前元素之后将列表分为两部分。
    /// 这将返回一个新列表，其中包含游标之后的所有内容，而原始列表将保留之前的所有内容。
    ///
    ///
    /// 如果游标指向 "ghost" 非元素，那么将移动 `LinkedList` 的全部内容。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn split_after(&mut self) -> LinkedList<T, A>
    where
        A: Clone,
    {
        let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
        if self.index == self.list.len {
            // "ghost" 非元素的索引已更改为 0.
            self.index = 0;
        }
        unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
    }

    /// 在当前元素之前将列表分为两部分。
    /// 这将返回一个新列表，该列表包含游标之前的所有内容，而原始列表保留之后的所有内容。
    ///
    ///
    /// 如果游标指向 "ghost" 非元素，那么将移动 `LinkedList` 的全部内容。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn split_before(&mut self) -> LinkedList<T, A>
    where
        A: Clone,
    {
        let split_off_idx = self.index;
        self.index = 0;
        unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
    }

    /// 将一个元素追加到游标的父列表的前面。
    /// 游标指向的节点不变，即使是 "ghost" 节点。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    // 当 `push_front` 添加一个节点以模仿 `insert_before` 在空列表上的行为时，它会继续指向 "ghost"。
    //
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn push_front(&mut self, elt: T) {
        // 安全性：我们知道 `push_front` 不会改变其他节点在内存中的位置。
        // 这确保 `self.current` 保持有效。
        //
        self.list.push_front(elt);
        self.index += 1;
    }

    /// 将一个元素追加到游标父列表的后面。
    /// 游标指向的节点不变，即使是 "ghost" 节点。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn push_back(&mut self, elt: T) {
        // 安全性：我们知道 `push_back` 不会改变其他节点在内存中的位置。
        // 这确保 `self.current` 保持有效。
        //
        self.list.push_back(elt);
        if self.current().is_none() {
            // "ghost" 的索引是列表的长度，所以我们只需要增加 self.index 来反映列表的新长度。
            //
            self.index += 1;
        }
    }

    /// 从游标的父列表中删除第一个元素并返回它，如果列表为空，则返回 None。
    /// 游标指向的元素保持不变，除非它指向前面的元素。
    /// 在这种情况下，它指向新的前端元素。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn pop_front(&mut self) -> Option<T> {
        // 我们不能检查 current 是否为空，我们必须直接检查列表。
        // `self.current == None` 和列表可能不为空。
        //
        if self.list.is_empty() {
            None
        } else {
            // 我们不能指向我们弹出的节点。
            // 复制 `remove_current` 的行为，我们移动到序列中的下一个节点。
            // 如果列表的长度为 1，那么我们结束指向索引 0 处的 "ghost" 节点，这是预期的。
            //
            if self.list.head == self.current {
                self.move_next();
            } else {
                self.index -= 1;
            }
            self.list.pop_front()
        }
    }

    /// 从游标的父列表中删除最后一个元素并返回它，如果列表为空，则返回 None。
    /// 游标指向的元素保持不变，除非它指向后面的元素。
    /// 在这种情况下，它指向 "ghost" 元素。
    ///
    /// 此运算应在 *O*(1) 时间中进行计算。
    ///
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn pop_back(&mut self) -> Option<T> {
        if self.list.is_empty() {
            None
        } else {
            if self.list.tail == self.current {
                // 索引现在反映了列表的长度。
                // 它是列表的长度减 1，但现在列表小 1。
                // `index` 不需要更改。
                self.current = None;
            } else if self.current.is_none() {
                self.index = self.list.len - 1;
            }
            self.list.pop_back()
        }
    }

    /// 提供对游标父列表前元素的引用，如果列表为空，则为 None。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn front(&self) -> Option<&T> {
        self.list.front()
    }

    /// 提供对光标父列表的前元素的可变引用，如果列表为空，则为 None。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.list.front_mut()
    }

    /// 提供对游标父列表的后部元素的引用，如果列表为空，则为 None。
    ///
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn back(&self) -> Option<&T> {
        self.list.back()
    }

    /// 提供一个循环引用来返回游标的父列表的元素，如果列表为空，则提供 `None`。
    ///
    /// # Examples
    /// 使用游标构建和可变列表，然后获取返回元素：
    ///
    /// ```
    /// #![feature(linked_list_cursors)]
    /// use std::collections::LinkedList;
    /// let mut dl = LinkedList::new();
    /// dl.push_front(3);
    /// dl.push_front(2);
    /// dl.push_front(1);
    /// let mut cursor = dl.cursor_front_mut();
    /// *cursor.current().unwrap() = 99;
    /// *cursor.back_mut().unwrap() = 0;
    /// let mut contents = dl.into_iter();
    /// assert_eq!(contents.next(), Some(99));
    /// assert_eq!(contents.next(), Some(2));
    /// assert_eq!(contents.next(), Some(0));
    /// assert_eq!(contents.next(), None);
    /// ```
    #[must_use]
    #[unstable(feature = "linked_list_cursors", issue = "58533")]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.list.back_mut()
    }
}

/// 通过在 LinkedList 上调用 `drain_filter` 生成的迭代器。
#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
pub struct DrainFilter<
    'a,
    T: 'a,
    F: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> where
    F: FnMut(&mut T) -> bool,
{
    list: &'a mut LinkedList<T, A>,
    it: Option<NonNull<Node<T>>>,
    pred: F,
    idx: usize,
    old_len: usize,
}

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Iterator for DrainFilter<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        while let Some(mut node) = self.it {
            unsafe {
                self.it = node.as_ref().next;
                self.idx += 1;

                if (self.pred)(&mut node.as_mut().element) {
                    // `unlink_node` 可以使用别名 `element` 来引用。
                    self.list.unlink_node(node);
                    return Some(Box::from_raw(node.as_ptr()).element);
                }
            }
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.old_len - self.idx))
    }
}

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Drop for DrainFilter<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,
{
    fn drop(&mut self) {
        struct DropGuard<'r, 'a, T, F, A: Allocator>(&'r mut DrainFilter<'a, T, F, A>)
        where
            F: FnMut(&mut T) -> bool;

        impl<'r, 'a, T, F, A: Allocator> Drop for DropGuard<'r, 'a, T, F, A>
        where
            F: FnMut(&mut T) -> bool,
        {
            fn drop(&mut self) {
                self.0.for_each(drop);
            }
        }

        while let Some(item) = self.next() {
            let guard = DropGuard(self);
            drop(item);
            mem::forget(guard);
        }
    }
}

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
where
    F: FnMut(&mut T) -> bool,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("DrainFilter").field(&self.list).finish()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Iterator for IntoIter<T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.list.pop_front()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.list.len, Some(self.list.len))
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.list.pop_back()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {}

#[stable(feature = "fused", since = "1.26.0")]
impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}

#[stable(feature = "default_iters", since = "1.70.0")]
impl<T> Default for IntoIter<T> {
    /// 创建一个空的 `linked_list::IntoIter`。
    ///
    /// ```
    /// # use std::collections::linked_list;
    /// let iter: linked_list::IntoIter<u8> = Default::default();
    /// assert_eq!(iter.len(), 0);
    /// ```
    fn default() -> Self {
        LinkedList::new().into_iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> FromIterator<T> for LinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = Self::new();
        list.extend(iter);
        list
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
    type Item = T;
    type IntoIter = IntoIter<T, A>;

    /// 将列表消耗到迭代器中，该迭代器按值产生元素。
    #[inline]
    fn into_iter(self) -> IntoIter<T, A> {
        IntoIter { list: self }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        <Self as SpecExtend<I>>::spec_extend(self, iter);
    }

    #[inline]
    fn extend_one(&mut self, elem: T) {
        self.push_back(elem);
    }
}

impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> {
    default fn spec_extend(&mut self, iter: I) {
        iter.into_iter().for_each(move |elt| self.push_back(elt));
    }
}

impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
    fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
        self.append(other);
    }
}

#[stable(feature = "extend_ref", since = "1.2.0")]
impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> {
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.extend(iter.into_iter().cloned());
    }

    #[inline]
    fn extend_one(&mut self, &elem: &'a T) {
        self.push_back(elem);
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> {
    fn eq(&self, other: &Self) -> bool {
        self.len() == other.len() && self.iter().eq(other)
    }

    fn ne(&self, other: &Self) -> bool {
        self.len() != other.len() || self.iter().ne(other)
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.iter().partial_cmp(other)
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
    #[inline]
    fn cmp(&self, other: &Self) -> Ordering {
        self.iter().cmp(other)
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
    fn clone(&self) -> Self {
        let mut list = Self::new_in(self.alloc.clone());
        list.extend(self.iter().cloned());
        list
    }

    fn clone_from(&mut self, other: &Self) {
        let mut iter_other = other.iter();
        if self.len() > other.len() {
            self.split_off(other.len());
        }
        for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
            elem.clone_from(elem_other);
        }
        if !iter_other.is_empty() {
            self.extend(iter_other.cloned());
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self).finish()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        state.write_length_prefix(self.len());
        for elt in self {
            elt.hash(state);
        }
    }
}

#[stable(feature = "std_collections_from_array", since = "1.56.0")]
impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
    /// 将 `[T; N]` 转换为 `LinkedList<T>`。
    ///
    /// ```
    /// use std::collections::LinkedList;
    ///
    /// let list1 = LinkedList::from([1, 2, 3, 4]);
    /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
    /// assert_eq!(list1, list2);
    /// ```
    fn from(arr: [T; N]) -> Self {
        Self::from_iter(arr)
    }
}

// 确保 `LinkedList` 及其只读迭代器的类型参数是协变的。
#[allow(dead_code)]
fn assert_covariance() {
    fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
        x
    }
    fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
        x
    }
    fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
        x
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Sync> Send for Iter<'_, T> {}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Sync> Sync for Iter<'_, T> {}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Send> Send for IterMut<'_, T> {}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Sync> Sync for IterMut<'_, T> {}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {}

#[unstable(feature = "linked_list_cursors", issue = "58533")]
unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {}