CODEWITHSUNDEEP
rustdynamiclinked-list
Jim
Jim

Reputation: 769

Possible to implement dynamically-typed linked list in safe Rust?

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.

Upvotes: 1

Views: 227

Answers (1)

cafce25
cafce25

Reputation: 27533

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.

Upvotes: 3

Related Questions