Support a doubly-linked list module similar to LL

[Robert Hodge]

The current Linked List module LL is clearly implemented as a singly-linked list.

I would like to see a doubly-linked list supported. The advantages would be ease of inserting and deleting nodes at any point, and efficiently adding nodes either at the beginning or end of the list that would work equally fast. Right now, to add at the end may require a search from a current node to the end, or else keeping a separate pointer to the end. Also, determining a "previous" node requires a search from the beginning in LL, while for a doubly-linked list no search is required.

For the name of this module, Doubly Linked List suggests a name of DLL. While this is possible, and hasn't been used yet, DLL *might* get confused with a Dynamic Link Library module. The confusion could be overcome with good documentation. Otherwise, we could pick a different name, like LLD, LL2 or L2L. I do kind of like DLL though.

If the current source for LL is available, I would consider writing the module, probably adapting it from the existing LL code. I don't see it as feasible or advisable to alter the LL to support double links, if for no other reason than not to break existing code.

[ErosOlmi]

Ciao Robert,

some thinBasic versions ago (I do not remember exactly in which version) I added some nice data structures directly into thinBasic Core engine without the need to have separated modules:
https://www.thinbasic.com/public/products/thinBasic/help/html/index.html?datastructures.htm

Double Linked Lists: https://www.thinbasic.com/public/products/thinBasic/help/html/linked_list.htm
Hash tables (my preferrend data structure): https://www.thinbasic.com/public/products/thinBasic/help/html/hash_table.htm
AVL Tree: https://www.thinbasic.com/public/products/thinBasic/help/html/avl_tree.htm

Please check if it is what you need or something is missing.

Ciao
Eros

[Robert Hodge]

Hello Eros,

The Linked List support in the data structure feature you refer to does nearly everything I might need. I have a few issues:

1. The feature doesn't appear in the current TB release. I assume it was dropped some time ago? Did no one want it, or didn't it work right, or was there some other problem?

2. The feature needs a little more documentation. For instance, getting a "next" node pointer doesn't say what you get at the end of the list. Is it 0? Do I have to call that "valid" function? It doesn't say.

3. I wish I could do more than just store a string. Maybe a UDT? Maybe another string to support key + data? Other possibilities?

4. I wish there were some "list management" functions. Things like:

(a) ability to "swap" two nodes
(b) ability to reverse the link-order of a range of nodes
(c) ability to "snip" out a range of nodes
(d) ability to insert one list, or a range within one list, into another list (list merging)
(e) ability to copy a list or range of one, to make a new list that did not share node memory
(f) possibly have the size of the list stored in the list container so that it was not necessary to enumerate over all of them to determine its size.

Those are the sorts of things I had in mind. Speaking of "sort", wouldn't it be interesting, if you had a key, to sort a list by key?

Things like that. I am not sure how much of these "extra" features are feasible; you'd have to tell me.

If this feature is not implemented now, what would it take to "re-install" it?

Thanks,

Robert

[ErosOlmi]

Install lates thinBasic beta release at https://www.thinbasic.com/community/showthread.php?12949-thinBasic-1-11-x-x
Version 1.11.6
Then check few examples in \thinBasic\SampleScripts\DataStructures\



1. The feature doesn't appear in the current TB release. I assume it was dropped some time ago? Did no one want it, or didn't it work right, or was there some other problem?

I improve thinBasic with new features by personal needs or by user requests.
Usually I do not remove anything after it is developed regardless of user interest. I try to never remove backward compatibility.



2. The feature needs a little more documentation. For instance, getting a "next" node pointer doesn't say what you get at the end of the list. Is it 0? Do I have to call that "valid" function? It doesn't say.

Maybe I will improve it a little but when you see "pointer" ... nothing = 0 and 0 = nothing



3. I wish I could do more than just store a string. Maybe a UDT? Maybe another string to support key + data? Other possibilities?

Data is data, difference is how you interpret it. Inside thinBasic dynamic strings you can store whatever: a full UDT or pointers to personalized dynamic allocated data.
Key + Data pairs are better handled by Hash Tables o Dictionaries like other programming languages call them.



4. I wish there were some "list management" functions. Things like:

(a) ability to "swap" two nodes
(b) ability to reverse the link-order of a range of nodes
(c) ability to "snip" out a range of nodes
(d) ability to insert one list, or a range within one list, into another list (list merging)
(e) ability to copy a list or range of one, to make a new list that did not share node memory
(f) possibly have the size of the list stored in the list container so that it was not necessary to enumerate over all of them to determine its size.

Usually I implement new detailed features if there is an interest. So try to see if current features are close to what you need and if yes let me know what missed features are important for you and I will try to work on them.

Ciao
Eros

[Robert Hodge]

Thanks for your reply, Eros.

First, the current TB documentation file is in a slightly different order from the one you pointed me to. I thought the current TB release did not have an entry for LList, but it does; somehow I was looking in the wrong place. So, my mistake.

Second, I have a set of enhancements I would like to make, which I believe would be of general interest. Here is what I have in mind:

1. If you would allow me to see the source code for the LList support, I will try to understand how it works. I assume it is written in Power Basic? Or else in C/C++? I know both of them. And I am very familiar with the general concept of linked lists so that part I already know.

2. Once I can determine what enhancements are (a) feasible and (b) likely to be of general interest, I will put together documentation on the proposed functions, along with improved documentation for the existing functions. I can write the documentation in MS Word, unless you have some kind of Help Document authoring software you use. I might have to do the best I can with MS Word and have someone transcribe it for me, to whatever doc software you use.

3. If you approve of my proposal, I will write and test the code, then turn it over to you for integration testing.

Does this sound reasonable?

Robert

[ErosOlmi]

Ciao Robert,

I cannot give source code I used in thinBasic Core engine but I can send you PowerBasic source code I was inspired from.

Code was public domain by Stanley Durham at https://forum.powerbasic.com/forum/user-to-user-discussions/programming/51903-hlib-comments
Unfortunately source code seems disappeared from his web site but I have one old copy I can send to you this evening when back from work.

Ciao
Eros

[Robert Hodge]

Eros, my goal was to enhance the current code and create a complete replacement for it. If you can't make the source available, it wouldn't be possible to ensure backward compatibility.

I think for now it would be best for me to withdraw this proposal.

Thanks for your interest.

Robert

[ErosOlmi]

You can still do it if you like.
I sent you Power Basic sources from which I took inspiration.

If you can add more functionalities in linked list included in the sources, just send me and I will see how to add into thinBasic giving merit into thinBasic help.

Ciao
Eros