Tip of the Week #3: Data Structures

This week JustSid took the time to write a nice little article about the pro's and con's of common data structures:

http://www.opserver.de/wiki/index.php/Tip_of_the_Week

Thank you, JustSid!

i feel dumb but what is 0(1) and 0(N). im trying to glean from the context but all ive gotten that 0(1)~=good/easy/effcient and 0(N)~=bad.

Edit: other than that, not a bad read. for more tip ideas i was thinking a more in depth explaination on pointers and functional uses for them. also I got the idea while reading this that it might be good at some point to have a small article about the different ways to modify a data structure (que's, deque's, stack's, popping, pulling, etc.)

That is the big O notation, see here:
http://en.wikipedia.org/wiki/Big_O_notation

It's the common way to describe the complexity of operations and algorithms. Example:

O(1) means that your algorithm always takes a constant amount of operations, no matter how big n (the dimension) is. 6, 10, 89078 are all elements of the set O(1), because they are constant multiples of "1".

O(n) means that the cost of your algorithm/ operation increases linearly with the size of your "problem". n, 4/3n, 4n+5 and the like are all elements of O(n).

n^2, n^2 - 3n + 7 are elements of O(n^2) and so on.

So basically a "How to implement data structure X efficiently"?

yeah, something like that would be cool.

I guess I will write the next four tips of the week covering the implementation of the mentioned data structures. But a pointer tutorial... Dunno, I'm currently trying to write one in german and its already hard to explain without going too deep in low-level stuff.

Quite a good read

How about heap trees and graphs? The heap tree is a nice link to the BST and array, and graphs are important for AI.

Maybe after you've documented the data structures, it might be a good idea for you (or someone else) to document some of the algorithms we can use on these structures.

Thank you for that great article. I'd also like to see some more advanced data structures like DJBMASTER pointed out.

Doing a little nitpicking here, but you describe a binary tree as a tree made "..out of a root node which links to one or more child nodes which...". However, in a binary tree any node can not have more than two child nodes or else it isn't a binary tree anymore.

Thanks guys

@DJBMASTER: Yes, there are a lot of data structures missing (eg. I had also liked to add a skip list section), but my time budget was very limited (Superku asked me ~12 hours before if I could write it and it was already around midnight when I started writing + I had to sleep a bit too) so I focused on the four, imo, most useful data structures.

I will add other data structures in random order to the article, so if you have any suggestions, let me hear them (skip lists and heap trees are on my list!).


About common algorithms, yes, I wanted to add those as well for the in depth implementation guides, for example how to sort an array efficiently and how to calculate a good hash for a hash table from binary data and such things. Of course it can't cover everything, but the most useful stuff will make it. And again, if you have suggestions, let me hear them


Yes, you are totally right there, thanks for catching this! The chapter started was first intended to be a trees in general chapter but this was way too much so I later changed this to just a balanced binary tree chapter but forgot to change the quoted sentence. But the rest (as well as the ASCII art) assumes just two child nodes.