3 ms·
Ask HN: How do you learn how to implement data structures?
Just to clarify, I'm not looking for "how do you learn about data structures".
Instead, more precisely, I'm looking for "When you're interested in or reading about a specific data structure, and wish to implement it in your programming language of choice, where would you typically go for a reference implementation?"
I've been wanting to beef up my overall knowledge of data structures (breadth and depth), and the best way I know how is to "do it". So this means I will want to locate (preferably) canonical implementations of data structures. From the searching I've done so far, I was unable to locate an authoritative list anywhere.
Of course I'm sure with enough searching I will come across implementations in libraries scattered across the web. For most things this is probably ok, but given that data structures are such a fundamental part of CS it seems it would be nice to have a single source (if only links to other resources) where I could go knowing I will be directed to what the community considers the defacto implementation of a given data structure.
GitHub seems it would be a perfect place to start compiling such a list.
Also once that list is compiled I imagine another logical step would be to start annotating those in something like [http://genius.com/]
I of course have come across this:
http://en.wikipedia.org/wiki/List_of_data_structures
But it really only gives me a good long list of data structures I may like to write implementations for.
- nostrademons 12y agohttp://www.amazon.com/Introduction-Algorithms-Edition-Thomas-Cormen/dp/0262033844 http://www.amazon.com/Introduction-Algorithms-Edition-Thomas... That's basically your bible of basic data structures & algorithms. There are, of course, many many other domain-specific ones, but that textbook is taught in the vast majority of data structures & algorithms courses, it covers most of what people would expect in an interview or in basic programming, and it teaches you how you might implement them. The book itself uses pseudocode, but if you're a halfway competent programmer you should be able to translate it into your language of choice. (For a fun exercise, it can be interesting to translate them into a programming platform of choice. For example, how would you implement a priority queue with an SQL database? How would you do reservoir sampling? How do you implement sorting on disk, where the dataset is >>> RAM size? How do you implement a graph algorithm on a cluster of 5000 machines? These are the sort of "Google level" problems that you end up facing in industry, but they require a full understanding - not just familiarity - with what the underlying algorithm is doing.)
- datashovel 12y agoThank you for the link. I'm even trying to figure out, for example, maybe I read about a particular data structure in a blog post that I'd like to learn more about. I find the relevant article on Wikipedia, and from there it may or may not take me to specific implementations of that data structure. Perhaps I'm mistaken but my hunch is Wikipedia won't necessarily be exhaustive (in terms of being able to extrapolate from the article what an actual implementation should look like). Maybe that part of the question is more of a fishing expedition, as I imagine it's a small fraction of developers / engineers who are ever actually implementing complex data structures.
- Nadya 12y agoI'm a little confused about what you're asking for, but this might help? http://blog.notdot.net/tag/damn-cool-algorithms http://blog.notdot.net/tag/damn-cool-algorithms
- datashovel 12y agoSorry for the confusion, but I think the link you've provided definitely fits the bill. My original intent was to ask about personal preferences (resources people use) of people who implement (or have implemented data structures). As an aside I was exploring an idea (probably where the confusion set in) that in my ideal world there would be a web page where I could go that would list all data structures. And each item in that list would link to the canonical / reference implementation of that datastructure. And if that didn't exist, then a list of all known implementations (by language) which would link to the source code of each implementation. If something like this doesn't exist I am definitely up for taking a crack at it, but at least wanted to check to see what folks here might have to say, which may be a better idea or to confirm that it doesn't already exist.