...

View Full Version : Linked List



gizmo1650
07-31-2011, 06:25 AM
I am trying to implement a linked list in javascript. So far i have:

function linkedList(){
var llNode=function(value){
this.next=null;
this.previues=null;
this.value=value;
}
var that=this;
this.length=0;
this.head=null;
this.tail=null;
this.add=function(value){
if(length==0){
var tmp=new llNode(value)
that.head=tmp;
that.tail=tmp;
}
else{
var tmp=new llNode(value);
tmp.previues=that.tail;
that.tail.next=tmp;
that.tail=that.tail.next;
}
that.length++;
}
}
}

When I use:

var ll=new linkedList();
ll.add(1);
ll.add(2);
both the head and tail of ll point to the node whose value is to, and the next and previues pointer on that node are both null.

rnd me
07-31-2011, 08:23 AM
you need to define length, at least...

you can also simply use elements: they have nextSibling, firstChild, parentNode, insertBefore, appendChild, removeChild, and all the other methods you want in this sort of thing.
plus, you can use all sort of dom methods to search nodes, including css queries...

siberia-man
07-31-2011, 09:46 AM
rnd me
He uses the length property already.

gizmo1650
The problem is here -- missing keyword:


if(this.length==0){

siberia-man
07-31-2011, 09:59 AM
gizmo1650

I would implement the add method simpler:


NodeList.prototype.append = function(node)
{
node.prev = this.tail;
this.tail = node;
if ( this.length == 0 ) {
this.head = node;
} else {
node.prev.next = node;
}
return this.length++;
};

DaveyErwin
08-01-2011, 02:48 AM
I am trying to implement a linked list in javascript. So far i have:

function linkedList(){
var llNode=function(value){
this.next=null;
this.previues=null;
this.value=value;
}
var that=this;
this.length=0;
this.head=null;
this.tail=null;
this.add=function(value){
if(length==0){
var tmp=new llNode(value)
that.head=tmp;
that.tail=tmp;
}
else{
var tmp=new llNode(value);
tmp.previues=that.tail;
that.tail.next=tmp;
that.tail=that.tail.next;
}
that.length++;
}
}
}

When I use:

var ll=new linkedList();
ll.add(1);
ll.add(2);
both the head and tail of ll point to the node whose value is to, and the next and previues pointer on that node are both null.

Here is a quick off the cuff example
of one way to implement an
doulble linked list in javascript ....



<script>

(function(){
var length = 0;
var prev;
var Node = function(a){
this.getLength = function(){return length};
this.prev = prev;
this.next;
this.data = a;
this.addToTail = function(a){
length++;
return new Node(a)};
this.addBefore = function(a,b){
length++;
a.prev.next = new Node(b);
a.prev = a.prev.next;
a.prev.next = a;
return a.prev;
}
if(prev)prev.next = this;
prev = this;
}
LInkedList = function(a){
length++;
return new Node(a);
}
})()
n = new LInkedList('myData');
n1 = n.addToTail('myData2');
n2 = n.addToTail('myData3');
n3 = n1.addBefore(n1,"myData1")
//alert(n.data);
//alert(n1.prev.data);
//alert(n1.data);
//alert(n1.next.data);
//alert(n.getLength())
for(var i = n.getLength(); i--;){
alert(n.data);
n = n.next;
}

</script>
of course it needs an addAfter and an addToHead
and others
well the way it is you can only have
one LinkedList cause of the vars length and prev

DaveyErwin
08-01-2011, 02:55 AM
you need to define length, at least...

you can also simply use elements: they have nextSibling, firstChild, parentNode, insertBefore, appendChild, removeChild, and all the other methods you want in this sort of thing.
plus, you can use all sort of dom methods to search nodes, including css queries...

What if there is no dom ?
Like maybe if you are not
running in a browser ?

< ^ ;

rnd me
08-01-2011, 10:06 PM
What if there is no dom ?
Like maybe if you are not
running in a browser ?

< ^ ;

then you can still use a dom library. i use node.js and libxml-js (https://github.com/polotek/libxmljs/wiki) provides those methods...



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum