OrderedDict in Golang
One of the most interesting data structures Python has built-in is the OrderedDict. It allows for O(1) lookups via a dictionary, while also providing iteration based on the order you inserted items into it. A real use case for this could be a sandwich shop. We want to process customers in order, but if a customer somewhere in the middle of the line leaves, we could iterate through all the items to remove them, but if we have a hash map (or a dictionary in Python) we can remove them in O(1) time. I’ve played around with implementing this myself in Python and it’s not too much code, so I thought I would try it out in Go.
One major caveat is that Go map keys must be comparable and since you cannot implement/override your own comparison methods we are limited by what can be a key.
… comparable types are boolean, numeric, string, pointer, channel, and interface types, and structs or arrays that contain only those types.
To keep things simple, I made the key a string however map[interface{}]interface{} is also valid and would allow us to have “any” value as the key.
The whole file is almost exactly 50 lines of code. The more complicated piece is actually the linked list implementation at just under 70 lines of code.
I also wrote some tests to make sure things actually work and it seems to behave how I would expect. Overall I think this implementation is comparable to the one I wrote in Python.
One of the more interesting parts is the iteration (via .Iterate()); I was doing some reading recently about lazy evaluation in Go and they suggested using channels. I don’t love it, but the interface is clean and the fact that it’s using a channel is mostly hidden.
