你将如何在 Rust 中实现双向链表? [英] How would you implement a bi-directional linked list in Rust?

问题描述

请注意，此问题指的是 Rust 1.0 之前的 Rust 版本.尽管语法发生了变化，但概念仍然有效.

Note that this question refers to a version of Rust before Rust 1.0. Although the syntax has changed, the concepts are still valid.

您可以使用自有指针轻松实现仅前向链表，例如:

You can easily implement a forwards only linked list using owned pointers, something like:

struct Node<T> {
  next: Option<~Node<T>>,
  data: T
}

想象一下，如果你想有效地实现一个支持四种基本操作的队列:

Imagine, though, if you want to efficiently implement a queue that supports four basic operations:

• push:添加到列表末尾
• pop:从列表末尾移除并返回
• unshift:添加到列表前面
• shift:从列表末尾移除并返回

• push: add to end of list
• pop: remove and return from the end of the list
• unshift: add to the front of the list
• shift: remove and return from the end of the list

在具有普通指针的语言中，您可以使用双向链表和一个存储 first 和 last 指向第一个和最后一个指针的根对象来实现它列表中的元素.

In a language with normal pointers you might implement this with a bi-directional linked list, and a root object that stores first and last pointers to the first and last elements in the list.

我看不出你将如何在 Rust 中实现这一点.

I can't see how you would implement this in Rust.

我可以模糊地猜测您会使用一堆参考资料，也许是这样的:

I can sort of vaguely guess that you'd use a bunch of references, and perhaps something like:

struct Node<T> {
  next: Option<&Node<T>>,
  prev: Option<&Node<T>>,
  data: T
}

...但我看不出你是如何管理这些变量的生命周期范围的.

...but I can't see how you'd manage the lifetime scope of these variables.

谁能指出我的方向，或者类似的例子，它涉及复杂的生命周期和对象之间的引用?

Can anyone point me in the direction of this, or a similar example which involves complex lifetimes with references between objects?

(这种代码风格的另一个典型示例是观察者模式，其中许多对象必须将事件更新发布到单个位置，例如.UINode <>---- EventObserver <>---- EventCore <>---- UINodes; 复杂层次结构中的多个对象共享指针，其中事件从叶节点传播下降到某个核心，然后被推送到不同的叶节点)

(Another typical example of this style of code would be the observer pattern where many objects must publish event updates to a single location, eg. UINode <>---- EventObserver <>---- EventCore <>---- UINodes; multiple objects in a complex hierarchy sharing pointers, where events propagate from leaf nodes down to some core and then get pushed out to different leaf nodes)

推荐答案

我建议你看看 Rust 模式，由 Lars Bergstrom 编写.

I recommend you to take a look at Rust patterns, written by Lars Bergstrom.

这是实现双向链表的代码，从@Yurume 为 Rust 1.12 更新，(未完全测试)

Here's the code for implementing a doubly linked list, updated for Rust 1.12 from @Yurume, (not fully tested)

use std::mem;
use std::ptr;

pub struct List<T> {
    list_head: Option<Box<Node<T>>>,
    list_tail: Rawlink<Node<T>>,
}

struct Rawlink<T> { p: *mut T }

impl<T> Copy for Rawlink<T> {}

impl<T> Clone for Rawlink<T> {
    fn clone(&self) -> Self { Rawlink { p: self.p } }
}

pub struct Node<T> {
    next: Option<Box<Node<T>>>,
    prev: Rawlink<Node<T>>,
    value: T,
}

impl<T> List<T> {
    pub fn is_empty(&self) -> bool {
        self.list_head.is_none()
    }

    pub fn len(&self) -> usize {
        let mut node = &self.list_head;
        let mut i = 0;
        loop {
            match *node {
                Some(ref n) => {
                    i+=1;
                    node=&n.next;
                }
                None => {
                    return i;
                }
            }
        }
    }

    /// Create an empty DList
    pub fn new() -> List<T> {
        List{list_head: None, list_tail: Rawlink::none()}
    }

    pub fn push_front(&mut self, elt: T) {
        self.push_front_node(Box::new(Node::new(elt)))
    }

    pub fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
        match self.list_head {
            None => {
                self.list_tail = Rawlink::some(&mut new_head);
                new_head.prev = Rawlink::none();
                self.list_head = Some(new_head);
            }
            Some(ref mut head) => {
                new_head.prev = Rawlink::none();
                head.prev = Rawlink::some(&mut new_head);
                mem::swap(head, &mut new_head);
                head.next = Some(new_head);
            }
        }
    }

    /// Provide a forward iterator
    #[inline]
    pub fn iter<'a>(&'a self) -> ListIterator<'a, T> {
        ListIterator{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
    }
}

impl<T> Node<T> {
    fn new(v: T) -> Node<T> {
        Node{value: v, next: None, prev: Rawlink::none()}
    }
}

/// Rawlink is a type like Option<T> but for holding a raw pointer
impl<T> Rawlink<T> {
    /// Like Option::None for Rawlink
    fn none() -> Rawlink<T> {
        Rawlink{p: ptr::null_mut()}
    }

    /// Like Option::Some for Rawlink
    fn some(n: &mut T) -> Rawlink<T> {
        Rawlink{p: n as *mut T}
    }

    /// Convert the `Rawlink` into an Option value
    fn resolve_immut<'a>(&self) -> Option<&'a T> {
        unsafe { self.p.as_ref() }
    }

    /// Convert the `Rawlink` into an Option value
    fn resolve<'a>(&mut self) -> Option<&'a mut T> {
        unsafe { self.p.as_mut() }
    }

    /// Return the `Rawlink` and replace with `Rawlink::none()`
    fn take(&mut self) -> Rawlink<T> {
        mem::replace(self, Rawlink::none())
    }
}

pub struct ListIterator<'a, T: 'a> {
    head: &'a Option<Box<Node<T>>>,
    tail: Rawlink<Node<T>>,
    nelem: usize,
}

impl<'a, A> Iterator for ListIterator<'a, A> {
    type Item = &'a A;

    #[inline]
    fn next(&mut self) -> Option<&'a A> {
        if self.nelem == 0 {
            return None;
        }
        self.head.as_ref().map(|head| {
            self.nelem -= 1;
            self.head = &head.next;
            &head.value
        })
    }

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

impl<'a, A> DoubleEndedIterator for ListIterator<'a, A> {
    #[inline]
    fn next_back(&mut self) -> Option<&'a A> {
        if self.nelem == 0 {
            return None;
        }
        let tmp = self.tail.resolve_immut();
        tmp.as_ref().map(|prev| {
            self.nelem -= 1;
            self.tail = prev.prev;
            &prev.value
        })
    }
}

fn main() {
}

游乐场

这篇关于你将如何在 Rust 中实现双向链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！