Linked list of different types

Continuing the discussion from The idea behind a recursive struct:

I have seen that people use enums for additive types, but how you choose to implement it as a enum or as a struct??

For example, I'm more used to c - Is it possible to have a linked list of different data types? - Stack Overflow which (are structs) implements for example a linked list of different data types, thought maybe a rare question?? how you will implement such a list and act based on the content-type?

In general, when you need to be able to handle multiple types in one place, you have two choices:

  1. Use boxed trait objects (e.g. Box<Iterator>). The upshot is that you can store anything that implements Iterator. The downside is that (1) you have to allocate it on the heap because you don't know how big the struct implementing iterator will be (it could be anything), (2) the compiler will have to use dynamic dispatch when calling methods (it will have to look the methods up in a table) because it can't know the actual type at compile time, and (3) there can be no inlining of method calls (for the same reason as (2)). These will all make your program somewhat slower.

  2. Use an enum. The advantage is that (1) the compiler will know what a type can be at compile time so you won't have to put your object on the heap (the size is known), (2) function calls to the underlying objects still require introspection but this introspection is limited and can be better optimized, and (3) the compiler can perform inlining. The disadvantages are that (1) if you have a really big type and a really small type, the enum will be the size of the really big type (plus a flag to specify which type it is) and (2) you have to know all possible types at compile time.

So the question really isn't enum or struct but enum or trait object.


I also found this one Learning Rust With Entirely Too Many Linked Lists on another post around here or there.