OrderedDict in Golang

Elijah Wilson
Jan 10 · 2 min read

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.

Elijah Wilson

Written by

Software Developer from Michigan. New posts on https://blog.elijahwilson.me/

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade