By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,516 Members | 1,148 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,516 IT Pros & Developers. It's quick & easy.

In search of a good linked list implementation

P: n/a
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.

TIA

George

Jul 20 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
George M Jempty wrote:
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.


To be more specific, a doubly-linked list. With pointers to first and
last, so double-ended.

This is for the improved auto-tabbing solution. I think such lists will
be useful to traverse BOTH keystrokes AND text fields.

There's a C++ example in "TY Data Structures and Algorithms in 21 Days"
that I could modify, but I'm being lazy ;)

TIA

George

Jul 20 '05 #2

P: n/a
George M Jempty <gj*****@intergate.com> writes:
George M Jempty wrote:
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.
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
--
Lasse Reichstein Nielsen - lr*@hotpop.com
Art D'HTML: <URL:http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'
Jul 20 '05 #3

P: n/a
Lasse Reichstein Nielsen wrote:
George M Jempty <gj*****@intergate.com> writes:

George M Jempty wrote:
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.


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


Very nice. I end here just to compare the above with how this is
implemented in Java, straight from the source (I decided this should be
even better than the code from my data structures book):

/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
Jul 20 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.