A LinkedList where the Nodes are of 'any' type

[jymchng]

Hi, I am trying to build a LinkedList where the Nodes can be of any type, e.g.

Node<i32> -> Node<f64> -> Node<String> -> ...

This is my attempt in doing so: Rust Playground

However, the imperfect part is that I would need to specify the type of the next node at compile time, would there be a way to circumvent that?

Note: I am aware of the Any trait in std::any but would NOT like to use that because I am interested in being able to get value of any type via the say .data() method of the Data trait as written in the Playground.

fn main() {
    
    let mut node_1 = Node::<i32, f64>::new(69);
    let mut node_2 = Node::<f64, i32>::new(69.69);
    let node_3 = Node::<i32, f64>::new(69);
    
    node_1.next = Some(Rc::new(node_2));
    // node_2.next.as_ref().map(|n| Some(Rc::new(node_3)));
    
    println!("{:?} {:?}", node_1.data(), node_1.next().unwrap().data());
    // prints 69 69.69
}

[alice]

The purpose of dyn Trait is to avoid specifying types at compile-time. You can't really get around dyn Trait if that's what you want to do.

[drewtato]

The issue is that the return type of a function has to be a single type.

The most basic and usually sufficient way to do what you want is to make a regular linked list of boxed trait objects. For example, std::collections::LinkedList<Box<dyn Debug>>. A reason you might not want to do this is that it creates two allocations for every node. You can use your design to make a more allocation-efficient linked list.

The issue you have right now is that your list can only alternate. The trait might as well not exist, since your list is essentially this:

struct Node<T, U> {
    inner: T,
    next: Option<Rc<Node<U, T>>>,
}

It looks like you added the associated type to the trait in an attempt to make it object-safe, but it only makes it object-safe because it requires you to specify the return type of data at compile-time. This is not helpful unless the type of every node is known at compile-time (and when you don't want a repeating list, this also means knowing the length of the list), which is usually pretty useless for a linked list. You might as well use a tuple.

There is one main change you need to make. In order to return many types from data, you need to return a trait object.

fn data(&self) -> &dyn Debug

Which trait you use will depend on what you want to do with the data. In your example you're debug-printing it, so I've used Debug. Often this means creating a new trait that describes the actions you want to do to the data.

Here's the change on playground. I've changed the name of the trait to better reflect what it does.

struct BaseNode<T> {
    inner: T,
    next: Option<Rc<dyn Node>>,
}

impl<T> BaseNode<T> {
    fn new(t: T) -> Self {
        Self {
            inner: t,
            next: None,
        }
    }
}

trait Node {
    fn data(&self) -> &dyn Debug;
    
    fn next(&self) -> Option<Rc<dyn Node>>;
}

impl<T> Node for BaseNode<T> where T: Debug {
    fn data(&self) -> &dyn Debug {
        &self.inner
    }
    
    fn next(&self) -> Option<Rc<dyn Node>> {
        self.next.clone()
    }
}

Alternatively, you could put all the logic needed to operate on the data inside this trait, which should be faster than having to return a trait object. While not necessary, the trait (Debug) is still helpful in associating the logic with the data itself instead of the node.

trait Node {
    fn print_data(&self);
    
    fn next(&self) -> Option<Rc<dyn Node>>;
}

impl<T> Node for BaseNode<T> where T: Debug {
    fn print_data(&self) {
        println!("{:?}", self.inner);
    }
    
    fn next(&self) -> Option<Rc<dyn Node>> {
        self.next.clone()
    }
}