[Javascript] Data Structure implementation

[Matt Warden]

Jenni,

On Apr 4, 2005 1:50 PM, james <james at southspace.org> wrote:
> I am not really as much of an expert on this as I would like to be
> but I would say the reasons for using a linked list structure if for
> example you were using C are:
> 
> easy insertions
> easy joins
> no risk of overflow (so you can for example easily implement a queue)
> 
> the downsides being:
> 
> no direct but only sequential access

Well, you are assuming this is a downside. For abstraction and
encapsulation purposes, it is often a very desireable consequence. If
I pass a method/function a list node, it doesn't have to know anything
about the node's position in the list. I have seen many javascript
applications that fall all over themselves trying to keep track of
indeces, because the developer never thought about anything but an
array.

I could just as easily turn the question around and ask you why you
would ever want an array, and you would likely say: there are
situations where direct access is important. But, if you are in a
situation where only relative access is important, you are wasting
resources if you use an array over a linked list.

Then, of course, it is rather difficult to efficiently model a tree
structure and similar nonlinear structures in an array. In fact, you
waste quite a bit of space in an array implementation unless your tree
is full.

> but this is in comparison to classic C Arrays, whereas in comparison
> to a Hash Table for everything approach of JavaScript, and when you
> have compiled into the Javascript interpreter methods like
> Array.Splice(), I'm not sure what the benefits are of implementing
> such an structure....

Yes, I cannot speak to the efficiency of Array.splice(). Maybe do some tests?

My point with the "well, hashtables are usually arrays" comment was
only that I don't see how the fact that in JS 'arrays' are hashtables
in any way encroaches on the usefulness of linked lists.

> (oh, and aplogies, I am using a friend's account, my name is Jenny, not James!)

It would seem *I* owe the apologies :)

-- 
Matt Warden
Miami University
Oxford, OH, USA
http://mattwarden.com


This email proudly and graciously contributes to entropy.