How do you implement a container for different types in Go?

Issue

The following code implements a List of ints in Go:

package main

import "fmt"

type List struct {
    Head int
    Tail *List
}

func tail(list List) *List {
    return list.Tail
}

func main() {
    list := List{Head: 1, Tail: 
         &List{Head: 2, Tail:
         &List{Head: 3, Tail:
         nil}}}
    fmt.Println(tail(list).Head)
}

Problem is this only works for int. If I wanted a list of strings, I’d need to re-implement every list method (such as tail) again! That’s obviously not practical, so, this can be solved by using an empty interface:

type List struct {
  Head interface{} // Now works for any type!
  Tail *List
}

Problem is, 1. this seems to be much slower because of type casts, 2. it throws aways type safety, allowing one to type-check anything:

// This type-checks!
func main() {
    list := List{Head: 123456789 , Tail:
         &List{Head: "covfefe" , Tail:
         &List{Head: nil       , Tail:
         &List{Head: []int{1,2}, Tail:
         nil}}}}
    fmt.Println(tail(list).Head)

Obviously that program should not type-check in a statically typed language.

How can I implement a List type which doesn’t require me to re-implement all List methods for each contained type, but which keeps the expected type safety and performance?

Solution

Go doesn’t have generic types, so you’re stuck with the options you listed. Sorry.

Meanwhile, Go’s built-in maps and slices, plus the ability to use the empty interface to construct containers (with explicit unboxing) mean in many cases it is possible to write code that does what generics would enable, if less smoothly.

If you know more about the elements you want to store in the container, you may use a more specialized interface type (instead of the empty interface interface{}), which

  • could help you avoid using type assertions (keep good performance)
  • and still keep type safety
  • and it can be used for all types that (implicitly) implement your interface (code “re-usability”, no need to duplicate for multiple types).

But that’s about it. See an example of this here: Why are interfaces needed in Golang?

Also just in case you missed it, the standard library already has a doubly linked list implementation in the container/list package (which also uses interface{} type for the values).

Answered By – icza

Answer Checked By – David Goodson (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.