Re:Generics enabled by default in Go tip
by SamReidHughes on Saturday August 21, 2021 @02:07AM
(#28254636)
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.)
[ Parent
| on HN ]
Re:Generics enabled by default in Go tip
by puddingforears on Saturday August 21, 2021 @02:59AM
(#28254875)
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.
Re:Generics enabled by default in Go tip
by SamReidHughes on Saturday August 21, 2021 @03:17AM
(#28254956)
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.
Re:Generics enabled by default in Go tip
by kroolik on Saturday August 21, 2021 @05:41AM
(#28255593)
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).