473,320 Members | 2,146 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

In search of a good linked list implementation

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
3 11848
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Darryl B | last post by:
I can not get anywhere on this project I'm tryin to do. I'm not expecting any major help with this but any would be appreciated. The assignment is attached. The problem I'm having is trying to set...
19
by: RAJASEKHAR KONDABALA | last post by:
Hi, Does anybody know what the fastest way is to "search for a value in a singly-linked list from its tail" as oposed to its head? I am talking about a non-circular singly-linked list, i.e.,...
12
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition...
10
by: free2cric | last post by:
Hi, I have a single link list which is sorted. structure of which is like typedef struct mylist { int num; struct mylist *next;
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
0
by: | last post by:
I have a question about spawning and displaying subordinate list controls within a list control. I'm also interested in feedback about the design of my search application. Lots of code is at the...
6
by: Amit Bhatia | last post by:
Hi, I am not sure if this belongs to this group. Anyway, my question is as follows: I have a list (STL list) whose elements are pairs of integers (STL pairs, say objects of class T). When I create...
10
by: AsheeG87 | last post by:
Hello Everyone! I have a linked list and am trying to include a recursive search. However, I am having trouble understanding how I would go about that. I don't quite understand a recursive...
8
by: Jeff Bown | last post by:
Consider implementing a (doubly) linked list. The simplest strategy is to provide functions item_t add_item(item_t predecessor); void delete_item(item_t item); where add_item allocates memory...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.