Results 1 to 8 of 8

Thread: Support a doubly-linked list module similar to LL

  1. #1

    Support a doubly-linked list module similar to LL

    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.

  2. #2
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    54
    Posts
    8,636
    Blog Entries
    2
    Rep Power
    10
    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/pro...structures.htm

    Double Linked Lists: https://www.thinbasic.com/public/pro...inked_list.htm
    Hash tables (my preferrend data structure): https://www.thinbasic.com/public/pro...hash_table.htm
    AVL Tree: https://www.thinbasic.com/public/pro...l/avl_tree.htm

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

    Ciao
    Eros
    www.thinbasic.com | www.thinbasic.com/community/ | psch.thinbasic.com
    Win10Pro 64bit - 8GB Ram - Intel i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

  3. #3
    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

  4. #4
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    54
    Posts
    8,636
    Blog Entries
    2
    Rep Power
    10
    Install lates thinBasic beta release at https://www.thinbasic.com/community/...Basic-1-11-x-x
    Version 1.11.6
    Then check few examples in \thinBasic\SampleScripts\DataStructures\

    Quote Originally Posted by Robert Hodge View Post
    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.

    Quote Originally Posted by Robert Hodge View Post
    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

    Quote Originally Posted by Robert Hodge View Post
    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.

    Quote Originally Posted by Robert Hodge View Post
    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
    www.thinbasic.com | www.thinbasic.com/community/ | psch.thinbasic.com
    Win10Pro 64bit - 8GB Ram - Intel i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

  5. #5
    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

  6. #6
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    54
    Posts
    8,636
    Blog Entries
    2
    Rep Power
    10
    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/u...-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
    www.thinbasic.com | www.thinbasic.com/community/ | psch.thinbasic.com
    Win10Pro 64bit - 8GB Ram - Intel i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

  7. #7
    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

  8. #8
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    54
    Posts
    8,636
    Blog Entries
    2
    Rep Power
    10
    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
    Last edited by ErosOlmi; 19-06-2020 at 14:49.
    www.thinbasic.com | www.thinbasic.com/community/ | psch.thinbasic.com
    Win10Pro 64bit - 8GB Ram - Intel i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

Similar Threads

  1. sorting the Linked List
    By primo in forum thinBasic General
    Replies: 18
    Last Post: 25-09-2017, 20:41
  2. Idea for new module to support game
    By Petr Schreiber in forum CM contest 2009
    Replies: 10
    Last Post: 14-10-2008, 08:21
  3. Linked List Tool / Helper
    By kryton9 in forum User tools
    Replies: 5
    Last Post: 25-05-2008, 13:39
  4. Replies: 12
    Last Post: 10-07-2007, 17:44
  5. ADO module function list help
    By Reinking in forum thinBasic General
    Replies: 3
    Last Post: 17-11-2005, 11:11

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •