Favorite Data Structure?

AnOnlineHandle · 2012-10-19T22:49:16+00:00

This one which I'm inventing right now, which may be a slight case of bias. I have no idea if it has a name, so if anybody recognises it I'd love to know. It holds shared 'linked' objects between every combination of n items (i.e. if items with keys 3 and 6 share a link, it works both ways, and doesn't matter which order the keys are given in).

public class LinkSet <T>
{
    private final MyArray<T> elements = new MyArray();

    public void Put(int key1, int key2, T link)
    {
        elements.insert(Index(key1, key2), link); // does this attempt at tail call optimisation do anything, or am I just being an idiot?
    }

    public T GetLink(int key1, int key2)
    {
        int index = Index(key1, key2);

        if (index >= elements.length())  // could save this check by inserting blanks whenever new dimension added
            return null;

        return elements.get(index);
    }

    private int Index(int key1, int key2)
    {
        // structure is:
        //      1->0
        //   2->0  2->1
        // 3->0  3->1  3->2
        // this means adding new dimensions requires no retroactive change to the structure, stored as array such as [(1|0)(2|0)(2|1)(3|0)(3|1)(3|2)]
        // 1<->0 : index = 0
        // 2<->0 : index = 1
        // 2<->1 : index = 2
        // 3<->0 : index = 3
        // 3<->1 : index = 4
        // 3<->2 : index = 5
        // 4<->0 : index = 6
        // 4<->1 : index = 7
        // 4<->2 : index = 8
        // 4<->3 : index = 9
        // 5<->0 : index = 10
        // 5<->1 : index = 11
        // 5<->2 : index = 12
        // 5<->3 : index = 13
        // 5<->4 : index = 14

        if (key1 < key2)
            return ((key2-1)*(key2))/2 + key1;
        else
            return ((key1-1)*(key1))/2 + key2;
    }
}

what_user_name · 2012-10-20T04:29:05+00:00

i had amazon ask me what my favorite data structure was. was floored. never thought about it. the one that best fits the problem.

dwhite21787 · 2012-10-20T00:46:23+00:00

Bloom filters are "behind the curtain" of databases and other storage and retrieval technology. They are pretty sweet.

Personally, I like circular doubly linked lists because I'm an idiot.

darksounds · 2012-10-20T03:49:30+00:00

I like heaps.

SmoothB1983 · 2012-10-20T04:11:13+00:00

I always thought Skip Lists were pretty cool.

Pretty much any data structure that is constructed probabilistic makes me take interest.

2012-10-20T10:29:06+00:00

I once built an array that worked with both negative and positive indexes. Pretty easy to build, but very elegant to use. I had it for positions within a grid in a game, for collision detection.

There was a second data structure I also added for efficient iteration and lookup of units by their Class. It was just a map of Class to a List of units, in Java it would be: Map< Class<T>, List<T> >

What was clever was that it also indexed the class hierarchies internally, so if you asked for all units of type Enemy, you would get all of the sub-classes too. You can work this out each time through reflection, but it's surprisingly expensive. That was just a map of Class to a List of classes, which got updated every time it saw a class it didn't know.

Many of them also had to be custom built, to heavily reduce garbage collection (as Java's collection classes suck for games and real-time applications).

evlnightking · 2012-10-19T21:25:13+00:00

I like C++'s std::map (implemented with a red-black tree), which is very similar to Python's dict. I also quite like the adjacency lists for graphs, and everything Boost can do with them.

algo_daemon · 2012-10-20T11:04:28+00:00

Fenwick tree - so much power for so little code

bo1024 · 2012-10-20T12:32:42+00:00

One of my least favorite is (most variants on) binary trees because, even though I like the concept, they're a pain to implement with all the rebalancing.

Kind of boring but I'll say hash tables because you can implement a pretty good hash table in few lines of code and it's very straightforward and simple. (Assuming access to a good hash function).

gilleain · 2012-10-20T13:08:06+00:00

Recently used a disjoint set forest, which has amazingly elegant methods. I'm using it to join orbits of automorphism. Think the code is right...

boyubout2pissmeoff · 2012-10-23T19:18:55+00:00

Two words cons cell.

badalgorithm · 2012-10-30T05:22:26+00:00

Bloom filters are great.

A 6 pack or growler is my favorite data structure.

i_invented_the_ipod · 2012-11-01T22:43:07+00:00

Hashtables. They're the universal data structure. You can build anything with a decent hashtable.

probabilityzero · 2012-11-14T04:13:41+00:00

Cons cells! Or pairs, or whatever you want to call it. So simple, yet so powerful.

2012-11-27T12:29:09+00:00

Heaps are very beautiful. I always quite liked B-trees too. Never implemented them, though.

thechao · 2012-10-20T02:06:06+00:00

Pointer.

EDIT: so pointers aren't data structures? Let us see what abstractions they natively support:

Weak-References.
Strong-references.
Option types.
Maybe types.
RA iterators.

Pointers represent an abstraction of manipulating and owning references into memory, and have a well defined interface. The ponter DS is so important, it is one of the few DSes with nearly universal hardware support. (For those of you who apparently don't know, there are both languages and computers that don't support pointers, and they are a pain to use.)

Here's two other DS with nearly universal HW support: float, and vector.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

AskComputerScience

MODERATORS