How would you implement a bi-directional linked list in Rust?

Question

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: 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

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.

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?

(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)

Answer 1

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

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() {
}

Playground