RES: [Javascript] Data Structure implementation

[Hakan M (Backbase)]

A direct reference is also *always* faster than hash lookup. We use 
linked lists a lot in our application since it's many, many times faster 
than using arrays.

Example:

You have your posts in the array aPosts. In one operation, you want to 
change the current post, AND modify the previous and next post. With an 
array, you'd have to figure out which index you are at, and then access 
them by aPosts[nThisIndex+1] and aPosts[nThisIndex-1]. This is expensive.

Using a linked list, you'd simply do oPost.nextPost and 
oPost.previousPost. Being a direct reference, this is much faster.

I have a pretty nice LinkList class for JavaScript somewhere. If you 
need it, I can try to dig it up for you.

Regards,
H

Allard Schripsema wrote:
> As you already said, arrays are a good substitute for linked lists.
> 
> But using objects you can create your own linked list structure if you wish.
> 
> I can imagine a situation where you may want to implement a list not as an
> array, but as objects:
> When the number of elements in the chain is changed a lot you would delete
> and update faster with objects than using an array:
> imagine inserting a new element at position 2 os an array of 10000 elements.
> The linked list would be so much faster.....
> 
> Allard Schripsema
> 
> -----Mensagem original-----
> De: javascript-bounces at LaTech.edu
> [mailto:javascript-bounces at LaTech.edu]Em nome de Matt Warden
> Enviada em: segunda-feira, 4 de abril de 2005 13:48
> Para: [JavaScript List]
> Assunto: Re: [Javascript] Data Structure implementation
> 
> 
> James,
> 
> On Apr 4, 2005 11:29 AM, james <james at southspace.org> wrote:
> 
>>So that is easy enough. But in C one reason to use link-lists is to
>>overcome the problems of storing a dynamic number of elements in a
>>fixed contiguos array. Since Javascript uses hash tables to implement
>>an array data structure it's Array's are not contigous or fixed. So
>>is there every any reason to implement a Link-List in JavaScript?
> 
> 
> Most hash tables are implemented using arrays. You seem to be implying
> this is not the case with Javascript. Do you have information
> supporting this?
> 
> 
>>Has anyone imlemented a link-lists in their JavaScript? If so what
>>were the reasons for your choice of datastructure?
> 
> 
> I think the reasons for using a linked-list apply pretty much
> regardless of the language being used.
> 
> --
> Matt Warden
> Miami University
> Oxford, OH, USA
> http://mattwarden.com
> 
> 
> This email proudly and graciously contributes to entropy.
> _______________________________________________
> Javascript mailing list
> Javascript at LaTech.edu
> https://lists.LaTech.edu/mailman/listinfo/javascript
> 
> 
> _______________________________________________
> Javascript mailing list
> Javascript at LaTech.edu
> https://lists.LaTech.edu/mailman/listinfo/javascript
> 
>