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)