Using Interfaces to Create a Queue for Arbitrary Types

As an exercise for learning Go I am writing a basic Queue data structure. I started learning about interfaces yesterday I thought it would be cool to try and use them for this exercise. What I am trying to accomplish is to have a Queue that can accept any type that implements this interface:

type Queuable interface {
  Next() *Queuable  // This is probably not right
}

Basically what I want is to be able to add any type that has a Next() method to my Queue. So what I tried was:

type Node struct {
	value interface{}
	next  *Queuable
}

// Next gets the next object
func (n *Node) Next() *Queuable {
	return n.next
}

// Job - A job for the queue
type Job struct {
	instruction string
	next        *Queuable
}

// Next gets the next object
func (j *Job) Next() *Queuable {
	return j.next
}

// Queue ...
type Queue struct {
	head *Queuable
	size int
}

And my methods looking like:

func (q *Queue) Enqueue(node *Queuable) {
	...
}

// Dequeue - Remove a Queueable form the Queue
func (q *Queue) Dequeue() *Queuable {
  result := q.head
  q.head = q.head.Next()
  q.size--
  return result
}

I'm getting a ton of these errors (basically on any line with an assignment):

current.Next undefined (type *Queuable is pointer to interface, not interface)

So ultimately what I would like to do would be:

func main() {
  queue := NewQueue()  // Helper function not pictured
  job := &Job{"some instructions", nil}
  node := &Node{5, nil}
  queue.Enqueue(node)  // queue = [node]
  queue.Enqueue(job) // queue = [node, job]
  queue.Dequeue() // node
  queue.Dequeue() // job
}

Don't use pointer to an interface type, just the interface type.

Queuable is an interface type, so everywhere in your code where you used *Queuable, change it to Queuable. For example:

type Queuable interface {
	Next() Queuable
}

type Node struct {
	value interface{}
	next  Queuable
}

// Next gets the next object
func (n *Node) Next() Queuable {
	return n.next
}

...

In Go a value of interface type stores a pair: the concrete value assigned to the variable, and that value's type descriptor.

More about interface's internals: The Laws of Reflection #The representation of an interface

So you almost never need a pointer to interface. An interface contains a key-value pair where the key may be a pointer. The rare case when a pointer to interface makes sense is if you want to modify the value of a variable of interface type passed to another function.

In your example the type *Job implements Queuable because it has a method with receiver type *Job, and so everywhere where a value of Queuable is required, a value of *Job can be used (and an implicit interface value of type Queuable will be created and used).

Getting back to your example:

Your Queuable only defines a method to get the next element in the queue, but not one to enqueue it which will make this solution lose flexibility. A single Next() method only describes that it is "queued" but it is not (necessarily) "queuable".

To be queuable I would also add another method: SetNext(Queuable)

type Queuable interface {
    Next() Queuable
    SetNext(Queuable)
}

Its implementation on Node can be for example:

func (n *Node) SetNext(q Queuable) { n.next = q }

Try it on the Go Playground.

Also note that there is some code duplication in Node and Job, being the next field and Next() and SetNext() methods. We could create a base node implementation, e.g.:

type Base struct {
    next Queuable
}

func (b *Base) Next() Queuable     { return b.next }
func (b *Base) SetNext(q Queuable) { b.next = q }

And now you can embed this Base type in your concrete Node and Job implementations which will "inherit" the next field and Next() and SetNext() methods, so you don't have to define any of these on the Node and Job types.

This is the full implementation of Node and Job, nothing else is required:

type Node struct {
    *Base
    value interface{}
}

type Job struct {
    *Base
    instruction string
}

Try this on the Go Playground.

Never use a pointer to an interface type, this is already a pointer!

So to make the code to work change the *Queuable as Queuable.

type Node struct {
    value interface{}
    next  Queuable
}

// Next gets the next object
func (n *Node) Next() Queuable {
    return n.next
}

// Job - A job for the queue
type Job struct {
    instruction string
    next        Queuable
}

However you can use a method receiver as pointer, depending of the struct complexity. Although if the used struct type is simple, you can define the method to use the struct value, this way allocating a new address in memory. If you use the method receiver as a pointer it will reference the address already occupied by the struct in memory.

The rule about pointers vs. values for receivers is that value methods can be invoked on pointers and values, but pointer methods can only be invoked on pointers.

This rule arises because pointer methods can modify the receiver; invoking them on a value would cause the method to receive a copy of the value, so any modifications would be discarded. The language therefore disallows this mistake.

The rule of thumb is that for consistency is better to stick either with method definition as a pointer or method definition as a value along the whole interface implementation.