Help Wanted Simplest Linked List Implementation


#1

Hi, I want to implement a most common and simplest linked list, but I cannot figure out how to implement it especially the pop_back() part. Note that definition for the linked list and node should not be changed ( except for changing the box type??).

Here is my code:

/**
 * Mutable Lists
 * - Classic Lists
 */
#[derive(Debug)]
struct ClassicList<T> {
    head: Option<Box<ClassicListNode<T>>>,
}
#[derive(Debug)]
struct ClassicListNode<T> {
    data: T,
    next: Option<Box<ClassicListNode<T>>>,
}

impl<T> ClassicList<T> {
    fn new() -> Self {
        ClassicList { head: None }
    }
    fn push_back(&mut self, data: T) {
        let new_tail = Some(Box::new(ClassicListNode {
            data: data,
            next: None,
        }));
        if self.head.is_none() {
            self.head = new_tail;
        } else {
            let mut cur_box_node = self.head.as_mut().unwrap(); // &mut Box<ClassicListNode<T>>
            loop {
                if cur_box_node.next.is_none() {
                    break;
                }
                let temp = cur_box_node;
                cur_box_node = temp.next.as_mut().unwrap();
            }
            cur_box_node.next = new_tail;
        }
    }
    fn pop_back(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        } else {
            //HELP!!!
        }
    }
    fn push_front(&mut self, data: T) {
        let new_front = Some(Box::new(ClassicListNode {
            data: data,
            next: std::mem::replace(&mut self.head, None), // next = self.head
        }));
        self.head = new_front;
    }
    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            //node is Box<T>
            //take on-the-stack value apart
            let pop = *node;
            self.head = pop.next;
            pop.data
        })
    }
    fn concat(suffix: ClassicList<T>) {
        unimplemented!()
    }
    fn equals(rhs: &ClassicList<T>) -> bool {
        unimplemented!()
    }
    fn is_empty(&self) -> bool {
        match self.head {
            Some(_) => true,
            None => false,
        }
    }
    fn clear(&mut self) {
        unimplemented!()
    }
    fn length(&self) -> usize {
        unimplemented!()
    }
}

impl<T> ClassicListNode<T> {
    fn new(new_data: T) -> Self {
        ClassicListNode {
            data: new_data,
            next: None,
        }
    }
}

#2

This forum is for development of Rust itself. You should ask this question on the https://users.rust-lang.org/ forum.


#3

@piping, you may want to check out Learn Rust by writing Entirely Too Many Linked Lists.