Javascript: I need a good data structure to keep a sorted list

views:

answers:

+1 Q:

Javascript: I need a good data structure to keep a sorted list

This would probably be implemented as a tree or something? My point is it needs to be efficient.

I don't know where to find good implementations of data structures for Javascript for something like this, though. I don't want to have to roll my own if I can avoid it.

Help appreciated.

+1 A:

How about a simple array, sorted after each update?

Hans B PUFAL 2010-09-28 05:03:41

That would get expensive I think.

Hamster 2010-09-28 05:05:44

I would think an [insertion sort](http://en.wikipedia.org/wiki/Insertion_sort) wouldn't get too expensive.

Casey Hope 2010-09-28 05:08:11

Unless you have a very large array (or insert a heck of a lot), it should be trivial. If it IS very large, or inserted to a lot, I would be wondering why on earth you need to.

Luke Schafer 2010-09-28 05:11:41

Web application managing long lists of data.

Hamster 2010-09-28 05:13:43

Yeah, but simply saying 'web application' doesn't say anything about the scale of usage. I can have a web application that lets you add friends to a sorted list that may need to handle 5 names at once, or an app that lets you manage all employees in a corporation of 5,000... bit of a difference in scale. EDIT... ok so you added 'long lists of data'... but how long is long? And how often?

Luke Schafer 2010-09-28 05:15:34

EDIT: Actually it might be relevant. Long is potentially thousands, and often is as often as a user would interact with the lists, which is frequently.

Hamster 2010-09-28 05:17:39

Of course it's relevant. There's always an implementation, maintenance, and performance (in this case, bandwidth) implication of including third party code - especially when it's not part of a well supported framework, in lieu of using a much simpler, though maybe slightly less efficient implementation (assuming it's not TOO inefficient), and using the more complex solution would be an example of premature optimization.

Luke Schafer 2010-09-28 05:21:37

+1 A:

Depends why you need it. For instance, if you only need the top element, this binary heap might be okay for you. Otherwise, implement a binarySearch and insertSorted functions for arrays, should not be more than ten-fifteen lines. Unless you plan on having thousands upon thousands of elements; then it makes more sense to just insert in bulk and then sort using the builtin.

Amadan 2010-09-28 05:08:21

This ought to work. Thanks.

Hamster 2010-09-28 05:18:16

ansaurus

tags:

views:

answers:

Javascript: I need a good data structure to keep a sorted list

related questions