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)

Solution 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

Solution 2

Also, for anyone else who finds this question, the clearest and easiest answer to my question is 'use *'.

* is the '4th type of pointer that no one likes to talk about in rust'.

see: http://static.rust-lang.org/doc/0.9/rust.html#pointer-types

That is, a normal pointer than can have NULL values and who's use is 1) unsafe, and 2) has no affect on the lifetime of other objects.

A linked list in both directions would then be implemented as:

struct ListNode<T> {
  _next: Option<~ListNode<T>>,
  _prev: Option<*ListNode<T>>,
  _data: Option<T>
}

Where the _prev value is set using functions like:

// Set the previous pointer
fn set_prev(&mut self, mut prev: &ListNode<T>) {
  unsafe {
    self._prev = Some(prev as *ListNode<T>);
  }
}

// Reset the previous pointer
fn reset_prev(&mut self) {
  self._prev = None::<*ListNode<T>>;
}

// Create a new next node and return it
fn extend_end(&mut self, value:T) {
  let mut next = ~ListNode::<T>::new();
  next.set_data(value);
  next.set_prev(self);
  self._next = Some(next);
}

Obviously this is extremely messy, but it genuinely appears to be the recommended approach for doing things which involve pointers.

The key take away from Lars Bergstrom talk (in the accepted answer) is that doing unsafe operations like this is fine so long as they are written carefully and safely wrapped into the internal implementation of type that continues to expose a 'safe' public api.

Solution 3

There is now a doubly-linked list implementation in the Rust standard library, collections::dlist. It is accompanied by a thorough test suite and is a pleasant read as well as a usable tool.

Here is a link to the source.

As suggested in a comment, here is the source itself (tests omitted for brevity, so please read the link if available):

// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! A doubly-linked list with owned nodes.
//!
//! The `DList` allows pushing and popping elements at either end and is thus
//! efficiently usable as a double-ended queue.

// DList is constructed like a singly-linked list over the field `next`.
// including the last link being None; each Node owns its `next` field.
//
// Backlinks over DList::prev are raw pointers that form a full chain in
// the reverse direction.

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

use core::prelude::*;

use alloc::boxed::Box;
use core::cmp::Ordering;
use core::default::Default;
use core::fmt;
use core::hash::{Writer, Hasher, Hash};
use core::iter::{self, FromIterator};
use core::mem;
use core::ptr;

/// A doubly-linked list.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct DList<T> {
    length: uint,
    list_head: Link<T>,
    list_tail: Rawlink<Node<T>>,
}

type Link<T> = Option<Box<Node<T>>>;

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

impl<T> Copy for Rawlink<T> {}
unsafe impl<T:'static+Send> Send for Rawlink<T> {}
unsafe impl<T:Send+Sync> Sync for Rawlink<T> {}

struct Node<T> {
    next: Link<T>,
    prev: Rawlink<Node<T>>,
    value: T,
}

/// An iterator over references to the items of a `DList`.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Iter<'a, T:'a> {
    head: &'a Link<T>,
    tail: Rawlink<Node<T>>,
    nelem: uint,
}

// FIXME #19839: deriving is too aggressive on the bounds (T doesn't need to be Clone).
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> Clone for Iter<'a, T> {
    fn clone(&self) -> Iter<'a, T> {
        Iter {
            head: self.head.clone(),
            tail: self.tail,
            nelem: self.nelem,
        }
    }
}

/// An iterator over mutable references to the items of a `DList`.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IterMut<'a, T:'a> {
    list: &'a mut DList<T>,
    head: Rawlink<Node<T>>,
    tail: Rawlink<Node<T>>,
    nelem: uint,
}

/// An iterator over mutable references to the items of a `DList`.
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<T> {
    list: DList<T>
}

/// 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}
    }

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

    /// Convert the `Rawlink` into an Option value
    fn resolve<'a>(&mut self) -> Option<&'a mut T> {
        if self.p.is_null() {
            None
        } else {
            Some(unsafe { mem::transmute(self.p) })
        }
    }

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

impl<T> Clone for Rawlink<T> {
    #[inline]
    fn clone(&self) -> Rawlink<T> {
        Rawlink{p: self.p}
    }
}

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

/// Set the .prev field on `next`, then return `Some(next)`
fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
                  -> Link<T> {
    next.prev = prev;
    Some(next)
}

// private methods
impl<T> DList<T> {
    /// Add a Node first in the list
    #[inline]
    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);
                self.list_head = link_with_prev(new_head, Rawlink::none());
            }
            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);
            }
        }
        self.length += 1;
    }

    /// Remove the first Node and return it, or None if the list is empty
    #[inline]
    fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
        self.list_head.take().map(|mut front_node| {
            self.length -= 1;
            match front_node.next.take() {
                Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
                None => self.list_tail = Rawlink::none()
            }
            front_node
        })
    }

    /// Add a Node last in the list
    #[inline]
    fn push_back_node(&mut self, mut new_tail: Box<Node<T>>) {
        match self.list_tail.resolve() {
            None => return self.push_front_node(new_tail),
            Some(tail) => {
                self.list_tail = Rawlink::some(&mut *new_tail);
                tail.next = link_with_prev(new_tail, Rawlink::some(tail));
            }
        }
        self.length += 1;
    }

    /// Remove the last Node and return it, or None if the list is empty
    #[inline]
    fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
        self.list_tail.resolve().map_or(None, |tail| {
            self.length -= 1;
            self.list_tail = tail.prev;
            match tail.prev.resolve() {
                None => self.list_head.take(),
                Some(tail_prev) => tail_prev.next.take()
            }
        })
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Default for DList<T> {
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    fn default() -> DList<T> { DList::new() }
}

impl<T> DList<T> {
    /// Creates an empty `DList`.
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn new() -> DList<T> {
        DList{list_head: None, list_tail: Rawlink::none(), length: 0}
    }

    /// Moves all elements from `other` to the end of the list.
    ///
    /// This reuses all the nodes from `other` and moves them into `self`. After
    /// this operation, `other` becomes empty.
    ///
    /// This operation should compute in O(1) time and O(1) memory.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut a = DList::new();
    /// let mut b = DList::new();
    /// a.push_back(1i);
    /// a.push_back(2);
    /// b.push_back(3i);
    /// b.push_back(4);
    ///
    /// a.append(&mut b);
    ///
    /// for e in a.iter() {
    ///     println!("{}", e); // prints 1, then 2, then 3, then 4
    /// }
    /// println!("{}", b.len()); // prints 0
    /// ```
    pub fn append(&mut self, other: &mut DList<T>) {
        match self.list_tail.resolve() {
            None => {
                self.length = other.length;
                self.list_head = other.list_head.take();
                self.list_tail = other.list_tail.take();
            },
            Some(tail) => {
                // Carefully empty `other`.
                let o_tail = other.list_tail.take();
                let o_length = other.length;
                match other.list_head.take() {
                    None => return,
                    Some(node) => {
                        tail.next = link_with_prev(node, self.list_tail);
                        self.list_tail = o_tail;
                        self.length += o_length;
                    }
                }
            }
        }
        other.length = 0;
    }

    /// Provides a forward iterator.
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter(&self) -> Iter<T> {
        Iter{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
    }

    /// Provides a forward iterator with mutable references.
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter_mut(&mut self) -> IterMut<T> {
        let head_raw = match self.list_head {
            Some(ref mut h) => Rawlink::some(&mut **h),
            None => Rawlink::none(),
        };
        IterMut{
            nelem: self.len(),
            head: head_raw,
            tail: self.list_tail,
            list: self
        }
    }

    /// Consumes the list into an iterator yielding elements by value.
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter{list: self}
    }

    /// Returns `true` if the `DList` is empty.
    ///
    /// This operation should compute in O(1) time.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    /// assert!(dl.is_empty());
    ///
    /// dl.push_front("foo");
    /// assert!(!dl.is_empty());
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn is_empty(&self) -> bool {
        self.list_head.is_none()
    }

    /// Returns the length of the `DList`.
    ///
    /// This operation should compute in O(1) time.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    ///
    /// dl.push_front(2is);
    /// assert_eq!(dl.len(), 1);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.len(), 2);
    ///
    /// dl.push_back(3);
    /// assert_eq!(dl.len(), 3);
    ///
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn len(&self) -> uint {
        self.length
    }

    /// Removes all elements from the `DList`.
    ///
    /// This operation should compute in O(n) time.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    ///
    /// dl.push_front(2is);
    /// dl.push_front(1);
    /// assert_eq!(dl.len(), 2);
    /// assert_eq!(dl.front(), Some(&1is));
    ///
    /// 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 = DList::new()
    }

    /// Provides a reference to the front element, or `None` if the list is
    /// empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    /// assert_eq!(dl.front(), None);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.front(), Some(&1is));
    ///
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front(&self) -> Option<&T> {
        self.list_head.as_ref().map(|head| &head.value)
    }

    /// Provides a mutable reference to the front element, or `None` if the list
    /// is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    /// assert_eq!(dl.front(), None);
    ///
    /// dl.push_front(1);
    /// assert_eq!(dl.front(), Some(&1is));
    ///
    /// match dl.front_mut() {
    ///     None => {},
    ///     Some(x) => *x = 5is,
    /// }
    /// assert_eq!(dl.front(), Some(&5is));
    ///
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.list_head.as_mut().map(|head| &mut head.value)
    }

    /// Provides a reference to the back element, or `None` if the list is
    /// empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    /// assert_eq!(dl.back(), None);
    ///
    /// dl.push_back(1);
    /// assert_eq!(dl.back(), Some(&1is));
    ///
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back(&self) -> Option<&T> {
        self.list_tail.resolve_immut().as_ref().map(|tail| &tail.value)
    }

    /// Provides a mutable reference to the back element, or `None` if the list
    /// is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    /// assert_eq!(dl.back(), None);
    ///
    /// dl.push_back(1);
    /// assert_eq!(dl.back(), Some(&1is));
    ///
    /// match dl.back_mut() {
    ///     None => {},
    ///     Some(x) => *x = 5is,
    /// }
    /// assert_eq!(dl.back(), Some(&5is));
    ///
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.list_tail.resolve().map(|tail| &mut tail.value)
    }

    /// Adds an element first in the list.
    ///
    /// This operation should compute in O(1) time.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut dl = DList::new();
    ///
    /// dl.push_front(2is);
    /// assert_eq!(dl.front().unwrap(), &2is);
    ///
    /// 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) {
        self.push_front_node(box Node::new(elt))
    }

    /// Removes the first element and returns it, or `None` if the list is
    /// empty.
    ///
    /// This operation should compute in O(1) time.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut d = DList::new();
    /// assert_eq!(d.pop_front(), None);
    ///
    /// d.push_front(1is);
    /// 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(|box Node{value, ..}| value)
    }

    /// Appends an element to the back of a list
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut d = DList::new();
    /// d.push_back(1i);
    /// 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) {
        self.push_back_node(box Node::new(elt))
    }

    /// Removes the last element from a list and returns it, or `None` if
    /// it is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut d = DList::new();
    /// assert_eq!(d.pop_back(), None);
    /// d.push_back(1i);
    /// 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(|box Node{value, ..}| value)
    }

    /// Splits the list into two at the given index. Returns everything after the given index,
    /// including the index.
    ///
    /// This operation should compute in O(n) time.
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut d = DList::new();
    ///
    /// d.push_front(1is);
    /// d.push_front(2);
    /// d.push_front(3);
    ///
    /// let mut splitted = d.split_off(2);
    ///
    /// assert_eq!(splitted.pop_front(), Some(1));
    /// assert_eq!(splitted.pop_front(), None);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn split_off(&mut self, at: uint) -> DList<T> {
        let len = self.len();
        assert!(at < len, "Cannot split off at a nonexistent index");
        if at == 0 {
            return mem::replace(self, DList::new());
        }

        // Below, we iterate towards the `i-1`th node, either from the start or the end,
        // depending on which would be faster.
        let mut split_node = if at - 1 <= len - 1 - (at - 1) {
            let mut iter = self.iter_mut();
            // instead of skipping using .skip() (which creates a new struct),
            // we skip manually so we can access the head field without
            // depending on implementation details of Skip
            for _ in 0..at - 1 {
                iter.next();
            }
            iter.head
        }  else {
            // better off starting from the end
            let mut iter = self.iter_mut();
            for _ in 0..len - 1 - (at - 1) {
                iter.next_back();
            }
            iter.tail
        };

        let mut splitted_list = DList {
            list_head: None,
            list_tail: self.list_tail,
            length: len - at
        };

        mem::swap(&mut split_node.resolve().unwrap().next, &mut splitted_list.list_head);
        self.list_tail = split_node;
        self.length = at;

        splitted_list
    }
}

#[unsafe_destructor]
#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Drop for DList<T> {
    fn drop(&mut self) {
        // Dissolve the dlist in backwards direction
        // Just dropping the list_head can lead to stack exhaustion
        // when length is >> 1_000_000
        let mut tail = self.list_tail;
        loop {
            match tail.resolve() {
                None => break,
                Some(prev) => {
                    prev.next.take(); // release Box<Node<T>>
                    tail = prev.prev;
                }
            }
        }
        self.length = 0;
        self.list_head = None;
        self.list_tail = Rawlink::none();
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, A> Iterator for Iter<'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) -> (uint, Option<uint>) {
        (self.nelem, Some(self.nelem))
    }
}

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

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

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, A> Iterator for IterMut<'a, A> {
    type Item = &'a mut A;
    #[inline]
    fn next(&mut self) -> Option<&'a mut A> {
        if self.nelem == 0 {
            return None;
        }
        self.head.resolve().map(|next| {
            self.nelem -= 1;
            self.head = match next.next {
                Some(ref mut node) => Rawlink::some(&mut **node),
                None => Rawlink::none(),
            };
            &mut next.value
        })
    }

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

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, A> DoubleEndedIterator for IterMut<'a, A> {
    #[inline]
    fn next_back(&mut self) -> Option<&'a mut A> {
        if self.nelem == 0 {
            return None;
        }
        self.tail.resolve().map(|prev| {
            self.nelem -= 1;
            self.tail = prev.prev;
            &mut prev.value
        })
    }
}

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

// private methods for IterMut
impl<'a, A> IterMut<'a, A> {
    fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
        // Insert before `self.head` so that it is between the
        // previously yielded element and self.head.
        //
        // The inserted node will not appear in further iteration.
        match self.head.resolve() {
            None => { self.list.push_back_node(ins_node); }
            Some(node) => {
                let prev_node = match node.prev.resolve() {
                    None => return self.list.push_front_node(ins_node),
                    Some(prev) => prev,
                };
                let node_own = prev_node.next.take().unwrap();
                ins_node.next = link_with_prev(node_own, Rawlink::some(&mut *ins_node));
                prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
                self.list.length += 1;
            }
        }
    }
}

impl<'a, A> IterMut<'a, A> {
    /// Inserts `elt` just after the element most recently returned by `.next()`.
    /// The inserted element does not appear in the iteration.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut list: DList<int> = vec![1, 3, 4].into_iter().collect();
    ///
    /// {
    ///     let mut it = list.iter_mut();
    ///     assert_eq!(it.next().unwrap(), &1);
    ///     // insert `2` after `1`
    ///     it.insert_next(2);
    /// }
    /// {
    ///     let vec: Vec<int> = list.into_iter().collect();
    ///     assert_eq!(vec, vec![1i, 2, 3, 4]);
    /// }
    /// ```
    #[inline]
    #[unstable(feature = "collections",
              reason = "this is probably better handled by a cursor type -- we'll see")]
    pub fn insert_next(&mut self, elt: A) {
        self.insert_next_node(box Node::new(elt))
    }

    /// Provides a reference to the next element, without changing the iterator.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::DList;
    ///
    /// let mut list: DList<int> = vec![1, 2, 3].into_iter().collect();
    ///
    /// let mut it = list.iter_mut();
    /// assert_eq!(it.next().unwrap(), &1);
    /// assert_eq!(it.peek_next().unwrap(), &2);
    /// // We just peeked at 2, so it was not consumed from the iterator.
    /// assert_eq!(it.next().unwrap(), &2);
    /// ```
    #[inline]
    #[unstable(feature = "collections",
              reason = "this is probably better handled by a cursor type -- we'll see")]
    pub fn peek_next(&mut self) -> Option<&mut A> {
        if self.nelem == 0 {
            return None
        }
        self.head.resolve().map(|head| &mut head.value)
    }
}

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

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

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

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

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> FromIterator<A> for DList<A> {
    fn from_iter<T: Iterator<Item=A>>(iterator: T) -> DList<A> {
        let mut ret = DList::new();
        ret.extend(iterator);
        ret
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> Extend<A> for DList<A> {
    fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
        for elt in iterator { self.push_back(elt); }
    }
}

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

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

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

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

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

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Clone> Clone for DList<A> {
    fn clone(&self) -> DList<A> {
        self.iter().map(|x| x.clone()).collect()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: fmt::Debug> fmt::Debug for DList<A> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        try!(write!(f, "DList ["));

        for (i, e) in self.iter().enumerate() {
            if i != 0 { try!(write!(f, ", ")); }
            try!(write!(f, "{:?}", *e));
        }

        write!(f, "]")
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> {
    fn hash(&self, state: &mut S) {
        self.len().hash(state);
        for elt in self.iter() {
            elt.hash(state);
        }
    }
}

Disclaimer: I am not the author of this code, it is part of the Rust language standard library. I take no credit (or blame) for it.

Comments

[Doug]

Although, somewhat awkwardly, as per cmr.github.io/blog/2014/02/15/this-week-in-rust "std::ptr saw some more cleanup, most notably every function ending in _ptr has had that suffix removed. to_unsafe_ptr and to_mut_unsafe_ptr have also been removed."

[vvondra]

It would be great if the answer could be updated to use box instead of ~

[ideasman42]

@Yurume on IRC was kind enough to update the example. I've been testing it and seems to work. Linked to it for now.

[rpax]

@ideasman42 Maybe it is better to put the update after the original code, on order to be more complete. Don't you think?

[ideasman42]

@rpax, dont have a strong opinion, original code is very out of date and needed significant edits to work at all. So don't think it will be very useful to anyone in its current form. Moved the link, but added note on the original code that its not 1.0 compatible.

[Qqwy]

Note that the link to 'Rust Patterns' is now broken (404).

[ptpaterson]

dlist is nolonger a part of std and the link does not point at a valid page.