Hacker News Reader

Linked lists are the one data structure that you never end up wanting a generic version of. They aren't really used as containers. (Except badly.)

View on HN

They’re the easiest stack structure to implement. All your operations are against the head of the list and you either have a thing, don’t have a thing, or add a thing. I’d like to be able to maintain a stack of things whose types I don’t have to manually reify and erase. That’s not a tall order, and it’s certainly not “complexity”. It’s markedly weird that I can’t have that same structure and associated operations be usable regardless of the thing I’m working with.

If you want a stack you'll just use a growable array (in Go, a slice). A linked list is suboptimal.

Linked lists serve a real purpose in some situations where you really do want O(1) behavior. One example is when you are performing the operation while holding a mutex. But it's never the sort of thing where the right tool is a linked list generic container.

I agree linked lists might be suboptimal for a stack implementation, but for a different reason: data locality.

You can have O(1) stack with both implementations. Slice-based will be easier to follow, and will bust the cache less often (less pointer jumps).

Reply on news.ycombinator.com