George M Jempty <gjempty@intergate.com> writes:
[color=blue]
> George M Jempty wrote:[color=green]
> > Is there a good linked list implementation in the public domain? Or
> > that someone on this group has already written that they'd like to
> > put in the public domain, right here on this newsgroup? I've
> > googled and been disappointed.[/color][/color]
[color=blue]
> To be more specific, a doubly-linked list. With pointers to first and
> last, so double-ended.[/color]
Don't know of one, but it can't be too hard to make:
---
// Constructor for list nodes
// DLListNode(elem) - constructor. Creates unlinked node with elem as data
// Interface:
// extract() - unlinks node, linking its predecessor and successor.
// insertAfter(node) - insert node after this node, updating links.
function DLListNode(elem) {
this.elem = elem;
this.prev = this.next = null;
}
DLListNode.prototype.extract = function () {
if (this.prev) {
this.prev.next = this.next;
}
if (this.next) {
this.next.prev = this.prev;
}
this.prev = this.next = null;
}
DLListNode.prototype.insertAfter = function (newNode) {
if (this == newNode) { return; } // don't be daft!
newNode.extract();
newNode.prev = this;
if (this.next) {
newNode.next = this.next;
this.next.prev = newNode;
}
this.next = newNode;
}
// The list itself
// Interface:
// getFirst() - returns first node, or null if none
// getLast() - returns last node, or null if none
// add(elem[,afterNode]) - creates new node with elem as data and
// inserts it at end of list, or optionally
// after afterNode
// foreach(func) - calls func on all elements stored in list
// find(func[,afterNode]) - finds first node in list (optionally after
// afterNode) where func returns true when
// called on the element.
function DLList() {
this.prev = this.next = this;
}
DLList.prototype.insertAfter = DLListNode.prototype.insertAfter;
DLList.prototype.getFirst = function () {
return (this.next == this)?null:this.next;
};
DLList.prototype.getLast = function () {
return (this.prev == this)?null:this.prev;
};
DLList.prototype.add = function (elem,afterNode) {
var newNode = new DLListNode(elem);
if (!afterNode) {
if (this.prev) {
afterNode = this.prev;
} else {
afterNode = this;
}
}
afterNode.insertAfter(newNode);
return newNode;
};
DLList.prototype.foreach = function (func) {
for (var node = this.next;node != this;node = node.next) {
func(node.elem);
}
};
DLList.prototype.find = function (func, startNode) {
if (!startNode) { startNode = this; }
for (var node = startNode.next; node != this;node = node.next) {
if (func(node.elem)) {return node;}
}
};
---
This is a simple double linked list. To avoid the special case of
adding the first node, the ends are linked to the list object itself,
so reaching the end of the list is not checked by "node==null" but
by "node==listObjectRef".
You could skip the list object totally, and work directly with
the node objects. I think I would :)
A test:
---
var l = new DLList();
l.add(1);
l.add(2);
l.add(3);
var n = l.add(4);
l.add(6);
l.add(7);
l.add(5,n);
l.foreach(alert);
var n = null;
while((n=l.find(function(x){return x%2 == 0;},n))) {
alert(n.elem);
}
---
[color=blue]
> There's a C++ example in "TY Data Structures and Algorithms in 21
> Days" that I could modify, but I'm being lazy ;)[/color]
I like lazy! :)
/L
--
Lasse Reichstein Nielsen -
lrn@hotpop.com
Art D'HTML: <URL:http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'
