Linked list with removal function in Rust

Question

I know there are other structures which are better than the linked list, but I want to implement a singly linked list which has a remove function for study.

After struggling for a few hours, I wrote this code.

use std::rc::Rc;
use std::cell::RefCell;
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
 elem: T,
 next: Link<T>,
}
impl<T> Node<T> {
 fn new(elem: T) -> Rc<RefCell<Self>> {
 Rc::new(RefCell::new(Node {
 elem: elem,
 next: None,
 }))
 }
}
pub struct List<T> {
 head: Link<T>,
}
impl<T: Eq> List<T> {
 pub fn new() -> Self {
 List { head: None }
 }
 pub fn push(&mut self, elem: T) {
 let new_head = Node::new(elem);
 match self.head.take() {
 Some(old_head) => {
 new_head.borrow_mut().next = Some(old_head);
 self.head = Some(new_head);
 }
 None => {
 self.head = Some(new_head);
 }
 }
 }
 pub fn remove(&mut self, elem: T) {
 let mut head = self.head.clone().unwrap();
 if head.borrow().elem == elem {
 self.head = head.borrow().next.clone();
 return;
 }
 loop {
 let next = head.borrow().next.clone();
 match next {
 None => return,
 Some(ref node) => {
 if node.borrow().elem == elem {
 head.borrow_mut().next = node.borrow().next.clone();
 }
 head = node.clone();
 }
 }
 }
 }
}
fn main() {
 let mut list = List::new();
 list.push(3);
 list.push(2);
 list.push(1);
 list.remove(2);
 let head = list.head.unwrap().clone();
 assert_eq!(head.borrow().elem, 1);
 let next = head.borrow().next.clone().unwrap();
 assert_eq!(next.borrow().elem, 3);
}

To iterate this list, I implemented a iterator.

pub struct Iter<T> {
 next: Link<T>
}
impl<T> Iterator for Iter<T> {
 type Item = Rc<RefCell<Node<T>>>;
 fn next(&mut self) -> Option<Self::Item> {
 let next = self.next.clone();
 let next_next = next.clone();
 self.next = match next_next {
 Some(node) => {
 node.borrow().next.clone()
 }
 None => {
 None
 }
 };
 next
 }
}
impl<T: Eq> List<T> {
 pub fn iter(&self) -> Iter<T> {
 Iter { next: self.head.clone() }
 }
}
fn main() {
 let mut list = List::new();
 list.push(3);
 list.push(2);
 list.push(1);
 list.remove(2);
 let mut it = list.iter();
 let next_node = it.next().unwrap();
 assert_eq!(next_node.borrow().elem, 1);
 let next_node = it.next().unwrap();
 assert_eq!(next_node.borrow().elem, 3);
 let next_node = it.next();
 assert_eq!(next_node.is_none(), true);
}

I'm not sure this code is good, because I think

• there are too many clone() or borrow() calls.
• code is long and not simple. (is using Rc and RefCell good?)

Are there easier or simpler ways?

Even if this code is not so bad, are there weak or dangerous points?

Answer 1

1. Read Learning Rust With Entirely Too Many Linked Lists.

2. Your code has compilation errors with Rust 1.18.0.

   error[E0446]: private type `Node<T>` in public interface
    --> src/main.rs:82:5
    |
   82 | type Item = Rc<RefCell<Node<T>>>;
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ can't leak private type
   

3. I derive Debug on almost every struct.

4. push can have all conditionals removed from it because doing nothing is the same as setting None as the next value.

5. remove panics when called on a newly-created list.

6. pushing 1, 1, 1, 1, 2 and then removing 1 results in the list 2->1->1 which doesn't seem any flavor of correct. I assume you wanted to remove the first match.

7. It's way easier to get the code right when it operates on the same level of abstraction. I've created a method that removes on a &mut Link<T> because that's the shared type between List and Link.

8. Honestly, it's also easier to get this right with recursive code as well.

9. Doesn't make sense to return the Rc<RefCell<...>> as the iterator type - people care about the values, not the collection.

10. Can simplify the iterator by just taking the value out of the iterator state and putting a new value in sometimes.

use std::rc::Rc;
use std::cell::RefCell;
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
#[derive(Debug)]
pub struct Node<T> {
 elem: T,
 next: Link<T>,
}
impl<T> Node<T> {
 fn new(elem: T) -> Rc<RefCell<Self>> {
 Rc::new(RefCell::new(Node {
 elem: elem,
 next: None,
 }))
 }
}
#[derive(Debug)]
pub struct List<T> {
 head: Link<T>,
}
impl<T: Eq> List<T> {
 pub fn new() -> Self {
 List { head: None }
 }
 pub fn push(&mut self, elem: T) {
 let new_head = Node::new(elem);
 new_head.borrow_mut().next = self.head.take();
 self.head = Some(new_head);
 }
 pub fn remove(&mut self, elem: T) {
 fn remove_inner<T: Eq>(node: &mut Link<T>, elem: T) {
 if let Some(ref mut n) = node.clone() {
 if elem == n.borrow().elem {
 *node = n.borrow_mut().next.take();
 return
 }
 remove_inner(&mut n.borrow_mut().next, elem);
 }
 }
 remove_inner(&mut self.head, elem)
 }
}
fn main1() {
 let mut list = List::new();
 list.push(3);
 list.push(2);
 list.push(1);
 list.remove(2);
 let head = list.head.unwrap().clone();
 assert_eq!(head.borrow().elem, 1);
 let next = head.borrow().next.clone().unwrap();
 assert_eq!(next.borrow().elem, 3);
 let mut list = List::new();
 list.remove(2);
 let mut list = List::new();
 list.push(1);
 list.push(1);
 list.push(1);
 list.push(1);
 list.push(2);
 list.remove(1);
 println!("{:?}", list);
}
pub struct Iter<T> {
 next: Link<T>,
}
impl<T> Iterator for Iter<T> {
 type Item = Rc<RefCell<Node<T>>>;
 fn next(&mut self) -> Option<Self::Item> {
 match self.next.take() {
 Some(next) => {
 self.next = next.borrow().next.clone();
 Some(next)
 }
 None => None,
 }
 }
}
impl<T: Eq> List<T> {
 pub fn iter(&self) -> Iter<T> {
 Iter { next: self.head.clone() }
 }
}
fn main2() {
 let mut list = List::new();
 list.push(3);
 list.push(2);
 list.push(1);
 list.remove(2);
 let mut it = list.iter();
 let next_node = it.next().unwrap();
 assert_eq!(next_node.borrow().elem, 1);
 let next_node = it.next().unwrap();
 assert_eq!(next_node.borrow().elem, 3);
 let next_node = it.next();
 assert_eq!(next_node.is_none(), true);
}
fn main() {
 main1();
 main2();
}

Frankly, I don't know why you used Rc and RefCell — they aren't needed to implement a singly linked list. There's no need for complicated shared ownership (no need for Rc) and there's no need for interior mutability (no need for RefCell).

• okeigo: Thank you for careful review. I think remove function need to change the next in Node, so I used RefCell. Can I implement it without RefCell?