在Rust的单个链接列表中实现.pop()的更好方法是什么? [英] What would be a better way to implement .pop() in my single linked list in Rust?
问题描述
我已经在Rust中实现了自己的单链接列表版本，这是我学习它的挑战之一，除了.pop()方法之外，我对自己拥有的所有内容都感到满意.使用2个while循环非常丑陋且效率低下，但是我发现没有其他方法可以克服将索引为len()的节点设置为2(无)(弹出列表)并使用索引处的节点的数据的问题.len()-1(表示Some(data)返回值)(返回弹出的元素).
I've implemented my own version of a singly linked list in Rust as one of the challenges for me to learn it, and I'm satisfied with everything I have there except for the .pop() method. Using 2 while loops is very ugly and inefficient, but I found no other way to overcome the problem of setting the node at the index len() - 2 to None (popping the list), and using the data from the node at the index len() - 1 for the Some(data) return value (returns the element that was popped).
pub struct SimpleLinkedList<T> {
head: Option<Box<Node<T>>>,
}
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
impl<T> Default for SimpleLinkedList<T> {
fn default() -> Self {
SimpleLinkedList { head: None }
}
}
impl<T: Copy> Clone for SimpleLinkedList<T> {
fn clone(&self) -> SimpleLinkedList<T> {
let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
let mut cur = &self.head;
while let Some(node) = cur {
cur = &node.next;
out.push(node.data)
}
out
}
}
impl<T> SimpleLinkedList<T> {
pub fn new() -> Self {
Default::default()
}
pub fn len(&self) -> usize {
let mut c = 0;
let mut cur = &self.head;
while let Some(node) = cur {
cur = &node.next;
c += 1;
}
c
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn push(&mut self, _element: T) {
let mut cur = &mut self.head;
match cur {
Some(_) => {
while let Some(node) = cur {
cur = &mut node.next;
}
}
None => (),
}
*cur = Some(Box::from(Node {
data: _element,
next: None,
}));
}
pub fn pop(&mut self) -> Option<T>
where
T: Copy,
{
let length = &self.len();
let mut cur = &mut self.head;
let mut out = None;
match cur {
Some(_) if *length > 1usize => {
let mut c = 0usize;
while let Some(node) = cur {
cur = &mut node.next;
if c >= length - 1 {
out = Some(node.data);
break;
}
c += 1;
}
c = 0usize;
cur = &mut self.head;
while let Some(node) = cur {
cur = &mut node.next;
if c == length - 2 {
break;
}
c += 1;
}
}
Some(node) => out = Some(node.data),
None => (),
}
*cur = None;
out
}
pub fn peek(&self) -> Option<&T> {
let cur = &self.head;
match cur {
Some(node) => Some(&node.data),
None => None,
}
}
}
impl<T: Copy> SimpleLinkedList<T> {
pub fn rev(&self) -> SimpleLinkedList<T> {
let mut clone = self.clone();
let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
while let Some(val) = clone.pop() {
out.push(val)
}
out
}
}
impl<'a, T: Copy> From<&'a [T]> for SimpleLinkedList<T> {
fn from(_item: &[T]) -> Self {
let mut out: SimpleLinkedList<T> = SimpleLinkedList::new();
for &e in _item.iter() {
out.push(e);
}
out
}
}
impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
fn into(self) -> Vec<T> {
let mut out: Vec<T> = Vec::new();
let mut cur = self.head;
while let Some(node) = cur {
cur = node.next;
out.push(node.data)
}
out
}
}
推荐答案
通过跟踪在执行过程中看到的最后一个元素(然后在末尾进行更新)，可以避免重新遍历列表.
You can avoid re-traversing the list by keeping track of the last element you saw as you go (and then updating that at the end).
如果您天真地怎么做，就会遇到麻烦；您的上一个"指针将保留列表其余部分的所有权，而借阅检查器将不允许这样做.诀窍是随行断开该链接-为此，您可以使用 mem :: replace 函数.完成此操作后，必须重新放回原先的位置.
If you are naive about how you do that, you will run into trouble; your "previous" pointer retains ownership of the rest of the list and the borrow checker won't allow that. The trick is to break that link as you go - and to do that you can use the mem::replace function. Once you've done that, you have to put it back before you lose track of your previous node again.
以下是全部内容(您必须原谅我对 unwrap 的自由使用-我认为这使事情更清楚了):
Here's what that could look like in full (you'll have to forgive my liberal use of unwrap - I do think it makes things clearer):
pub fn pop(&mut self) -> Option<T>
where T : Copy,
{
use std::mem::replace;
let curr = replace(&mut self.head, None);
if curr.is_none() { // list started off empty; nothing to pop
return None;
}
let mut curr = curr.unwrap(); // safe because of the check above
if let None = curr.next { // popped the last element
return Some(curr.data);
}
let mut prev_next = &mut self.head;
while curr.next.is_some() {
// Take ownership of the next element
let nnext = replace(&mut curr.next, None).unwrap();
// Update the previous element's "next" field
*prev_next = Some(curr);
// Progress to the next element
curr = nnext;
// Progress our pointer to the previous element's "next" field
prev_next = &mut prev_next.as_mut().unwrap().next;
}
return Some(curr.data);
}
顺便说一句，如果您愿意稍微更改界面，以便每次我们都返回一个新"列表(在 pop 函数中获得所有权)，所有这些指针改组将大大简化)，或像在完全学习Rust一样，使用持久性数据结构链接列表过多(已在评论中提及):
As an aside, all this pointer shuffling simplifies a lot if you're willing to change the interface a little so that we return a "new" list each time (taking ownership in the pop function), or use a persistent datastructure, as they do in Learning Rust with entirely too many linked lists (already mentioned in a comment):
pub fn pop_replace(self) -> (Option<T>, Self) {
// freely mutate self and all the nodes
}
您将使用哪种方式:
let elem, list = list.pop();
这篇关于在Rust的单个链接列表中实现.pop()的更好方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
