1

Is it possible to implement a dynamically-typed linked list in safe Rust?

The meaning of dynamically-typed linked list:

Node(56.7) -> Node("hello") -> Node(77) -> ...

I am doing this as an exercise, have tried different approaches to no avail, using Traits. Therefore doubting the possibility of doing this in Safe Rust.

3
  • 1
    Implementing a linked list is probably not a very good exercise. rust-unofficial.github.io/too-many-lists/index.html (But the "handle different types for values" part might teach you something useful.) Commented Jan 1, 2023 at 9:13
  • There being a whole dedicated tutorial about implementing linked lists seems contrary to your point @Caesar, but I think that you got a point somewhere, focus on the different tasks separately rather than merging both at the same time. Develop a linked list for a specific type, develop a dynamic type, only if you got both you should attempt a dynamically-typed linked list. Commented Jan 1, 2023 at 9:40
  • I'd rather call the too many linked lists series a cautionary tale than a tutorial Commented Jan 1, 2023 at 16:10

1 Answer 1

3

If your list has to work with any type

You can use the Any trait or better yet another object-safe trait which has the functionality you need from items in the list.

enum Node {
    Nil,
    Node {
        value: Box<dyn std::any::Any>,
        next: Box<Node>,
    },
}

impl std::fmt::Debug for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        match self {
            Node::Nil => write!(f, "Nil"),
            Node::Node { value, next } => {
                if let Some(value) = value.downcast_ref::<f64>() {
                    write!(f, "Node({value}) -> {next:?}")
                } else if let Some(value) = value.downcast_ref::<i32>() {
                    write!(f, "Node({value}) -> {next:?}")
                } else if let Some(value) = value.downcast_ref::<&str>() {
                    write!(f, "Node({value:?}) -> {next:?}")
                } else {
                    write!(f, "Node(<unknown type>) -> {next:?}")
                }
            }
        }
    }
}

fn main() {
    let list = Node::Node {
        value: Box::new(56.7),
        next: Box::new(Node::Node {
            value: Box::new("hello"),
            next: Box::new(Node::Node {
                value: Box::new(77),
                next: Box::new(Node::Nil),
            }),
        }),
    };
    dbg!(list);
}

will output something like [src/main.rs:39] list = Node(56.7) -> Node("hello") -> Node(77) -> Nil to stderr.

Pros

  • Works with any object (implementing the trait).
  • Every Node has the size of two Boxes no matter the types you put into the list.

Cons

  • Using downcast* can become very awkward fast, and there isn't really much you can do with a dyn Any otherwise.
  • Necessary additional indirection of Box.

If you know the types that end up in the list

You can use an enum with every possible type:

#[derive(Debug)]
enum DynamicType {
    Float(f64),
    Int(i32),
    Str(&'static str),
}
enum Node {
    Nil,
    Node {
        value: DynamicType,
        next: Box<Node>,
    },
}

impl std::fmt::Debug for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        match self {
            Node::Nil => write!(f, "Nil"),
            Node::Node { value, next } => write!(f, "Node({value:?}) -> {next:?}"),
        }
    }
}

fn main() {
    use DynamicType::*;
    let list = Node::Node {
        value: Float(56.7),
        next: Box::new(Node::Node {
            value: Str("hello"),
            next: Box::new(Node::Node {
                value: Int(77),
                next: Box::new(Node::Nil),
            }),
        }),
    };
    dbg!(list);
}

Pros

  • You can match and know instantly what type you're dealing with.
  • No indirection, the data is stored directly in the Nodes.

Cons

  • If the DynamicType contains a variety of sizes you might end up wasting a lot of space on Nodes.
  • You have to know every type to put in up front.
Sign up to request clarification or add additional context in comments.

2 Comments

Does using Any have a lot of benefits over using something like serde_json::Value? In the end, you need a "switch" statement somewhere that handles the different possible types.
An enum requires upstream adding an explicit case for each supported type. Any gives the user control over the internal values, though at the cost of gnarlier and less efficient retrieval (bunch of downcast_ref), as well as the boxing requirement.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.