Basic linked list stack implementation with go

Question

Here goes my first stack implementation with go

New to the go language and it's been ages since I implemented a stack

Would love to discuss the data structure implementation itself and how "goish" the code looks.

package stack
import "errors"
var (
 errEmptyStack = errors.New("Stack is empty")
)
type node struct {
 next *node
 Value interface{}
}
// Stack implementation
type Stack struct {
 head *node
 Count int // O(1) count
}
// Push value at the top of the stack
func (stack *Stack) Push(value interface{}) {
 var node = node{Value: value}
 if stack.head == nil {
 stack.head = &node
 } else {
 node.next = stack.head
 stack.head = &node
 }
 stack.Count++
}
// Pop value from the top of the stack
func (stack *Stack) Pop() (value interface{}, err error) {
 if stack.head == nil {
 return nil, errEmptyStack
 }
 var node = stack.head
 stack.head = node.next
 stack.Count--
 return node.Value, nil
}
// Peek element at the top of the stack without changing the stack
func (stack *Stack) Peek() (value interface{}, err error) {
 if stack.head == nil {
 return nil, errEmptyStack
 }
 return stack.head.Value, nil
}

Answer 1

Your code is a fairly good representation of a Stack, but has some issues. Some issues are in the technicalities of how your program is written, but others are in how you've used the tools available in Go.

Technicals

The exported Count value on the Stack is OK, but it should be named Size or something - Count is an ambiguous name.

There's no reason to have a capital Value. It's not an exported struct, so the field can't be exported either.

Given that you have the Count, though, you should probably use that instead of the pointer dereferences to check for an empty list.... for example, this code:

if stack.head == nil {
 return nil, errEmptyStack
}

can be

if stack.Count == 0 {
 return nil, errEmptyStack
}

Another nit-pick is that this code has redundancies:

var node = node{Value: value}
if stack.head == nil {
 stack.head = &node
} else {
 node.next = stack.head
 stack.head = &node
}

That could be written as:

stack.head = &node{Value: value, next: stack.head}

A common practice in Go is to use a boolean to indicate a success (receive on channels & values in maps). You are using an error instead. I would have written your signatures as:

func (stack *Stack) Pop() (value interface{}, ok bool)

When you have named return values in Go you should have a value-less return statement. Your Pop and Peek methods declare output parameters of value and err.... but you return specific values return nil, errEmptyStack and return stack.head.Value, nil.

You should instead have code like:

// Pop value from the top of the stack
func (stack *Stack) Pop() (value interface{}, err error) {
 if stack.head == nil {
 err = errEmptyStack
 return
 }
 var node = stack.head
 stack.head = node.next
 stack.Count--
 value = node.Value
 return
}

I would actually have bool outputs, and have.... (the zero-value for a bool is false):

// Pop value from the top of the stack
func (stack *Stack) Pop() (value interface{}, ok bool) {
 if stack.head == nil {
 return
 }
 var node = stack.head
 stack.head = node.next
 stack.Count--
 value = node.Value
 ok = true
 return
}

Go native structures

Now, the bigger issues with your stack is really about using the struct at all....

Because Go is statically typed, and has no forms of "generics" or "templates", you are forced to use interface{} as the value type. This is awkward, and requires lots of casting to use the output values from Pop and Peek.

Writing a stack on top of a Slice is what I would do.... and not have the Stack code at all. You peek the stack by reading the last element value := stack[len(stack) - 1] and push with stack = append(stack, value)

• GLlompart: This is exactly what I was looking for @rolfl. Loved what you found and I have a few questions if you don't mind. From the top of my head: My tests are using the Pop and Peek functions without having any explicit casting, I guess I'm missing something? Are you not losing a lot of information from the consumer class if you change the error to a boolean (thinking different errors scenario)? I assume also the return nil could lead to "nil checking issues" and that's why you are pointing it out?. I guess your last paragraph explains why there isn't a stack implementation in the go packages
• rolfl: Your tests probably did not inspect the values themselves - perhaps you just did == type operations to check the success. If the values were int values, though, how would you add stack.Pop() + stack.Pop() ? As for the bool returns. See the last paragraphs of the section: golang.org/ref/spec#Index_expressions - note how the second value is ok. What other error conditions could exist in Pop/Peek other than no-such-value? Also see channel receive: golang.org/ref/spec#Receive_operator Note that the value would be nil still, and ok is false.