[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.javascript

Implement linked list in JavaScript?

Robert Crandal

5/26/2015 10:24:00 AM

I am interested in implementing a doubly linked list data
structure with JavaScript, if it's even possible.

I typically implement my doubly linked list using C or C++,
as a linked list of "nodes". Each node contains previous and
next pointers to nodes that are adjacent. A node is typically
an object or data structure that is allocated at run time.

Typical node operations on my linked list include push, pop,
append, delete, insert (anywhere in list), etc, etc.. I also
have functions that can walk through my list and search for
any node, forwards or backwards, left or right, beginning at
any node index.

I am somewhat new to JavaScript, so I'm not entirely sure
how to go about this. Can my double linked list structure
be simulated as an array of objects? Or is there a different
way to implement this?
10 Answers

Evertjan.

5/26/2015 11:26:00 AM

0

"Robert Crandal" <noreplytome@yahoo.com> wrote on 26 mei 2015 in
comp.lang.javascript:

> I am interested in implementing a doubly linked list data
> structure with JavaScript, if it's even possible.

There are no lists in js. At least the notion escapes me.

> I typically implement my doubly linked list using C or C++,
> as a linked list of "nodes". Each node contains previous and
> next pointers to nodes that are adjacent.

There is only "runtime" in a scripting language.

Any compiling is done virtually at the same time.

> A node is typically an object or data structure
> that is allocated at run time.

Why typically? Is it or isn't it?

The whole idea of allocation is a precompiling thought.

Runtime allocation and deallocation in JS are done automachically.

Allocation being done on-demand,
and deallocation being called garbage-collection.

> Typical node operations on my linked list include push, pop,
> append, delete, insert (anywhere in list), etc, etc.. I also
> have functions that can walk through my list and search for
> any node, forwards or backwards, left or right, beginning at
> any node index.

Sorry, every language has its nuice and its nasy things.
Better learn about a language, than trying to implement the tricks
"out of context".

However, if you want to make an array of objects,
where only objects exist when and where you need them,
those objects having the methods and properties you want them to give,
and if you understand what you are doing, js is a good choice.

If you want to play with pointers, and not think an array as having a
natural order, well that is your choice of programming.

var a = [];
a[1] = [12345,'x'];
a[12345] = [1,'y'];

No hands, mama,
this 'single linked' array has only 2 members "allocated".

> I am somewhat new to JavaScript, so I'm not entirely sure
> how to go about this. Can my double linked list structure

We don't even know what that is, bus seen the above,
it is a simple as .., if again you know what you are doing.

> be simulated as an array of objects?

Here you go again, If you start thinking you are symulating another
language, you will stay "somewhat new to JavaScript" forever and ever.

> Or is there a different way to implement this?

You should not even want to implement such simulation.

It is like speaking a human language by just translating your thought in
your native one "at runtime".

Better learn and trust yourself thinking in that language.

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

Steven D'Aprano

5/26/2015 12:35:00 PM

0

On Tue, 26 May 2015 08:23 pm, Robert Crandal wrote:

> I am interested in implementing a doubly linked list data
> structure with JavaScript, if it's even possible.

I'm sure it's possible. But it may not be a good idea. Doubly-linked lists
tend to be useful in low-level languages with support for pointers as a
first-class value, not high-level languages with a rich set of pre-built
objects and functions. I expect that this will be much slower and less
convenient than using standard Javascript idioms.


> I typically implement my doubly linked list using C or C++,
> as a linked list of "nodes". Each node contains previous and
> next pointers to nodes that are adjacent.

That's the definition of a doubly linked list regardless of the language you
use.

> A node is typically
> an object or data structure that is allocated at run time.

The Javascript equivalent would be something like this:

var first = {prev: null, next: null, data: 23};

That gives you a node carrying payload of 23, with no prev and no next node.
Now we can add some new nodes:


var node = first;
node.next = {prev: node, next: null, data: 42};
node = node.next;
node.next = {prev: node, next: null, data: 99};

gives you a linked list with three nodes. Showing only the data field:

23 <--> 42 <--> 99

Now all you need to do is write functions to operate on the linked list.
Then, as a bonus, you can turn it into a self-contained object, with
methods, instead of stand-alone functions.


> I am somewhat new to JavaScript, so I'm not entirely sure
> how to go about this. Can my double linked list structure
> be simulated as an array of objects? Or is there a different
> way to implement this?

Even FORTRAN 77 can simulate a doubly linked list using an array, so I
daresay that Javascript could do it too using a list:

// untested
var slots = [null, null, null, null, null, null]; // preallocate six slots
var node = {prev: -1, next: -1, data: 23};
var first = 2;
var here = first;
slots[here] = node;

Arggh, that's too fiddly and annoying for me. You can play around with it if
you like, but I haven't had to think in Fortran idioms since the mid 1980s.

Doing this as an exercise to learn Javascript syntax and semantics is
perfectly reasonable, but for actual use, you should learn the JS idioms,
not C idioms.



--
Steven

Scott Sauyet

5/26/2015 2:17:00 PM

0

Steven D'Aprano wrote:
> Robert Crandal wrote:
>
>> I am interested in implementing a doubly linked list data
>> structure with JavaScript, if it's even possible.
>
> I'm sure it's possible. But it may not be a good idea.
> [ ... ]
> Doing this as an exercise to learn Javascript syntax and semantics is
> perfectly reasonable, but for actual use, you should learn the JS idioms,
> not C idioms.

(Most of this excellent answer deleted)

I agree that this can be a good learning exercise. If the OP is simply
interested in using an implmentation, there are plenty of them to be found
with a quick web search.

But I disagree that this is essentially useless. I have had times where it seemed by far the best structure, where I had little need to iterate from the beginning, but often a need to move forward or backward from current node or to insert or delete at the current node. An array-backed structure is not nearly as helpful, even if it would take less memory.

Because these are so easy to write, I've never written myself a normalized doubly-linked list implementation, writing one-offs when needed. I'd be curious to see how my current work with mostly functional JS would make for different code than my earlier OO approaches to this, though.

-- Scott

ram

5/26/2015 5:35:00 PM

0

"Robert Crandal" <noreplytome@yahoo.com> writes:
>I am somewhat new to JavaScript, so I'm not entirely sure
>how to go about this. Can my double linked list structure
>be simulated as an array of objects? Or is there a different
>way to implement this?

You have to know what you want to do:

- Do you want to implement doubly-linked lists?

- Do you want to have the API of a sequential container
including push, pop, append, delete and insert with an
arbitrary implementation?

Both can be done in JavaScript quite easily. If you want to
code it yourself, just go ahead an learn JavaScript first!

Denis McMahon

5/26/2015 9:34:00 PM

0

On Tue, 26 May 2015 03:23:48 -0700, Robert Crandal wrote:

> I am somewhat new to JavaScript, so I'm not entirely sure how to go
> about this. Can my double linked list structure be simulated as an
> array of objects? Or is there a different way to implement this?

What operations do you carry out on a doubly linked list:

1) prepend an element at the start of a list
2) append an element to the end of a list
3) insert one element or a sequence of elements at an arbitrary point in
a list
4) remove an element or sequence of elements from an arbitrary point in a
list
5) walk a list forwards
6) walk a list backwards
7) remove the last element from a list
8) remove the first element from a list
9) delete an element from a list
10) change the value of an element in a list

I think all of these can be done in javascript using an array.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/...
Global_Objects/Array

Look at the shift, unshift, pop, push, slice and splice array methods.

walking forwards through an array is easy:

for (i = 0; i < array.length; i++) {
// do something with the ith element
}

and walking backwards:

i = array.length;
while (i--) {
// do something with the ith element
}

--
Denis McMahon, denismfmcmahon@gmail.com

Michael Haufe (\"TNO\")

5/28/2015 3:02:00 AM

0

On Tuesday, May 26, 2015 at 5:23:54 AM UTC-5, Robert Crandal wrote:
> I am interested in implementing a doubly linked list data
> structure with JavaScript, if it's even possible.
>
> I typically implement my doubly linked list using C or C++,
> as a linked list of "nodes". Each node contains previous and
> next pointers to nodes that are adjacent. A node is typically
> an object or data structure that is allocated at run time.
>
> Typical node operations on my linked list include push, pop,
> append, delete, insert (anywhere in list), etc, etc.. I also
> have functions that can walk through my list and search for
> any node, forwards or backwards, left or right, beginning at
> any node index.
>
> I am somewhat new to JavaScript, so I'm not entirely sure
> how to go about this. Can my double linked list structure
> be simulated as an array of objects? Or is there a different
> way to implement this?

If you were able to implement it in C & C++ successfully, then I suspect you have nearly all the requirements you need to accomplish it in JavaScript. Use the same concept of node and methods as you are used to, but understand how to define objects and instances in JavaScript:

<https://developer.mozilla.org/en-US/docs/Web/JavaScript/Introduction_to_Object-Oriented_Java...

Not the best guide, but it's a start and should be sufficient to get a handle on the language if you are already somewhat competent at the languages you mentioned. If you have more specific problems during your implementation, then ask another question here. I think I might still have an implementation laying around somewhere.

Right now at the drop of a hat, here is a skeleton I would build upon and improve if I was to do it again:

var List = (function(){
function Node(value){
this.prev = undefined;
this.value = value;
this.next = undefined;
}

function List(){
this._head = undefined;
this._tail = undefined;
this.length = 0;
}
List.prototype = {
constructor: List,
insertAfter: function(position, value) {
var node = new Node(value);
node.prev = position;
node.next = position.next;
position.next.prev = node;
position.next = node;
this.length++;
},
insertBefore: function(position, value) {
var node = new Node(value);
this.length++;
//TODO: similar to insertAfter
},
insertFirst: function(value) {
var node = new Node(value);
node._prev = this._head;
this.length++;
//TODO: similar to insertAfter
},
insertLast: function(value) {
var node = new Node(value);
this.length++;
//TODO: similar to insertAfter
},
remove: function(position) {
var temp = position.value;
position.prev.next = position.next;
position.next.prev = position.prev;
position.prev = null;
position.next = null;
this.length--;
return temp;
}
}

return List;
})();

Michael Haufe (\"TNO\")

5/30/2015 1:12:00 PM

0

On Tuesday, May 26, 2015 at 9:17:10 AM UTC-5, Scott Sauyet wrote:
> I'd be curious to see how my current work with mostly functional JS would make for different code than my earlier OO approaches to this, though.

I'd suggest trying your hand at creating a JS version of a Finger Tree then. Monoids galore...

Scott Sauyet

6/5/2015 2:23:00 AM

0

Michael Haufe (TNO) wrote:
> Scott Sauyet wrote:
>> I'd be curious to see how my current work with mostly functional JS would
>> make for different code than my earlier OO approaches to this, though.
>
> I'd suggest trying your hand at creating a JS version of a Finger Tree then.
> Monoids galore...

Maybe I will. I've never even heard the term.

Thanks,

-- Scott

Michael Haufe (\"TNO\")

6/11/2015 1:43:00 AM

0

On Thursday, June 4, 2015 at 9:22:42 PM UTC-5, Scott Sauyet wrote:
> Michael Haufe (TNO) wrote:
> > Scott Sauyet wrote:
> >> I'd be curious to see how my current work with mostly functional JS would
> >> make for different code than my earlier OO approaches to this, though.
> >
> > I'd suggest trying your hand at creating a JS version of a Finger Tree then.
> > Monoids galore...
>
> Maybe I will. I've never even heard the term.

One of the better articles on this (outside the original paper):

<http://apfelmus.nfshost.com/articles/monoid-fingertre...

Scott Sauyet

6/11/2015 12:58:00 PM

0

Michael Haufe (TNO) wrote:
> Scott Sauyet wrote:
>> Michael Haufe (TNO) wrote:
>>> Scott Sauyet wrote:
>>>> I'd be curious to see how my current work with mostly functional JS >>>> would make for different code than my earlier OO approaches to this,
>>>> though.
>>>
>>> I'd suggest trying your hand at creating a JS version of a Finger Tree
>>> then.
>>> Monoids galore...
>>
>> Maybe I will. I've never even heard the term.
>
> One of the better articles on this (outside the original paper):
>
> <http://apfelmus.nfshost.com/articles/monoid-fingertre...

That is a much more gentle introduction than the original paper, which I've
been reading. Thanks.

For anyone else curious the original paper is at

<http://staff.city.ac.uk/~ross/papers/FingerTre...

I haven't even begun to consider implementation in JS yet.

Cheers,

-- Scott