doubly_linked_list.rs

mod memory {
    use std::marker::PhantomData;

    #[derive(Clone, Copy)]
    pub struct Ptr<T> {
        offset: usize,
        phantom: PhantomData<T>
    }

    impl<T> Ptr<T> {
        fn new(offset: usize) -> Self {
            Self {
                offset,
                phantom: PhantomData::default()
            }
        }

        pub fn deref<'a>(&self, memory: &'a Memory<T>) -> &'a T {
            &memory.buffer[self.offset]
        }

        pub fn deref_mut<'a>(&self, memory: &'a mut Memory<T>) -> &'a mut T {
            &mut memory.buffer[self.offset]
        }
    }

    pub struct Memory<T> {
        buffer: Vec<T>
    }

    impl<T> Memory<T> {
        pub fn new() -> Self {
            Self {
                buffer: Vec::new()
            }
        }

        pub fn alloc(&mut self, init: T) -> Ptr<T> {
            self.buffer.push(init);
            Ptr::new(self.buffer.len() - 1)
        }

        pub fn clear(&mut self) {
            self.buffer.clear();
        }
    }
}

use memory::*;

#[derive(Clone, Copy)]
struct Node<T> {
    value: T,
    prev: Option<Ptr<Node<T>>>,
    next: Option<Ptr<Node<T>>>,
}

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

struct List<T> {
    begin: Option<Ptr<Node<T>>>,
    end: Option<Ptr<Node<T>>>,
}

impl<T: Copy> List<T> {
    fn new() -> Self {
        Self {
            begin: None,
            end: None
        }
    }

    // ø       ø <- [node] -> <- [node] -> ø
    //              ^
    //              begin
    //                              ^
    //                              end
    fn push_back(&mut self, value: T, memory: &mut Memory<Node<T>>) {
        if self.end.is_none() {
            assert!(self.begin.is_none());
            let node = memory.alloc(Node::new(value));
            self.begin = Some(node);
            self.end = Some(node);
        } else {
            assert!(self.begin.is_some());
            let node = memory.alloc(Node::new(value));
            self.end.unwrap().deref_mut(memory).next = Some(node);
            node.deref_mut(memory).prev = self.end;
            self.end = Some(node);
        }
    }
}

fn main() {
    let mut memory = Memory::new();
    let mut list = List::<i32>::new();

    for i in 0..10 {
        list.push_back(i, &mut memory);
    }

    let mut iter = list.end;
    while iter.is_some() {
        println!("{}", iter.unwrap().deref(&mut memory).value);
        iter = iter.unwrap().deref(&mut memory).prev;
    }
}