Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #27878 > unrolled thread

Implement linked list in JavaScript?

Back to article view | Back to comp.lang.javascript

Contents

  Implement linked list in JavaScript? "Robert Crandal" <noreplytome@yahoo.com> - 2015-05-26 03:23 -0700
    Re: Implement linked list in JavaScript? "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-05-26 13:25 +0200
    Re: Implement linked list in JavaScript? Steven D'Aprano <steve@pearwood.info> - 2015-05-26 22:35 +1000
      Re: Implement linked list in JavaScript? Scott Sauyet <scott.sauyet@gmail.com> - 2015-05-26 07:17 -0700
        Re: Implement linked list in JavaScript? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2015-05-30 06:11 -0700
          Re: Implement linked list in JavaScript? Scott Sauyet <scott.sauyet@gmail.com> - 2015-06-04 19:22 -0700
            Re: Implement linked list in JavaScript? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2015-06-10 18:42 -0700
              Re: Implement linked list in JavaScript? Scott Sauyet <scott.sauyet@gmail.com> - 2015-06-11 05:57 -0700
    Re: Implement linked list in JavaScript? Denis McMahon <denismfmcmahon@gmail.com> - 2015-05-26 21:33 +0000
    Re: Implement linked list in JavaScript? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2015-05-27 20:01 -0700

#27878 — Implement linked list in JavaScript?

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?

[toc] | [next] | [standalone]

#27881

"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)

[toc] | [prev] | [next] | [standalone]

#27882

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

[toc] | [prev] | [next] | [standalone]

#27891

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

[toc] | [prev] | [next] | [standalone]

#27926

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...

[toc] | [prev] | [next] | [standalone]

#27986

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

[toc] | [prev] | [next] | [standalone]

#28076

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-fingertree.html>

[toc] | [prev] | [next] | [standalone]

#28081

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-fingertree.html>

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/FingerTree.html>

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

Cheers,

  -- Scott

[toc] | [prev] | [next] | [standalone]

#27902

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/Reference/
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

[toc] | [prev] | [next] | [standalone]

#27909

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_JavaScript>

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;
})();

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web