To be more specific, a doubly-linked list. With pointers to first and
last, so double-ended.
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);
}
---
There's a C++ example in "TY Data Structures and Algorithms in 21
Days" that I could modify, but I'm being lazy
I like lazy!
/L
