Page 1 of 1
Quickly concatenating linked lists?
Posted: Fri Aug 13, 2010 10:28 am
by Little John
Hi,
I'd like to be able to quickly concatenate linked lists (of the same type, of course).
I know I can do something like this:
Code: Select all
;-- Step 1: create two lists
NewList a()
For i = 1 To 3
AddElement(a())
a() = i
Next
NewList b()
For i = 4 To 10
AddElement(b())
b() = i
Next
;-- Step 2: "move" all elements from list b() to list a()
FirstElement(b())
While ListSize(b()) > 0
AddElement(a())
a() = b()
DeleteElement(b(), 1)
Wend
;-- Step 3: show new lists
ForEach a()
Debug a()
Next
Debug "-----"
ForEach b() ; b() is empty now
Debug b()
Next
Debug "-----"
If list b() is long, the above step 2 can take quite a long time.
Is there a way to do the same thing faster? Maybe something like this (pseudocode):
Code: Select all
pointer of last element in a(), that points to next element = address of first element in b()
delete any internal information about b()
Regards, Little John
Re: Quickly concatenating linked lists?
Posted: Fri Aug 13, 2010 2:13 pm
by Demivec
Here's a slight improvement:
Code: Select all
;-- Step 2: "move" all elements from list b() to list a()
ResetList(b())
While NextElement(b())
AddElement(a())
a() = b()
Wend
ClearList(b())
Regarding your pseudocode, that would be the fastest but it's limited to using PB internals (which may change at any time

). A internal representation of sorts for a linked-list's data used to be included in the manual but has been removed several revisions ago.
I'm looking in to a way to accomplish it using 'legitimate' means. I'll post it if I come up with anything.
Re: Quickly concatenating linked lists?
Posted: Fri Aug 13, 2010 7:16 pm
by Demivec
Here's a hack to concatenate two lists. It works but has one major flaw, it doesn't update the ListSize. I'll make a feature request for this to be made natively as ConcatList(sourceList(), destList()).
Code: Select all
;-- Step 2: "move" all elements from list b() to list a()
Structure links ;in reverse order and used for reference offsets, clumsy I know :)
ElementData.i
*prevEl.i
*nextEl.i
EndStructure
If ListSize(b())
FirstElement(b())
LastElement(a())
;create a copy of source list's first element
AddElement(a())
a() = b()
If NextElement(b())
;update links for concatenation
PokeI(@a() - OffsetOf(links\nextEl), @b() - OffsetOf(links\nextEl)) ;a() now links to remainder of b()
PokeI(@b() - OffsetOf(links\prevEl), @a() - OffsetOf(links\nextEl)) ;remainder of b() now links to previous a()
FirstElement(b())
PokeI(@b() - OffsetOf(links\nextEl), #Null) ;correct first link in b() *extEl to point to #Null
AddElement(a())
DeleteElement(a())
EndIf
EndIf
;a() now contains the previous ListSize(a()) + previous ListSize(b()
;The ListSize will be reported wrong, there is now way To update the ListSize for a() with this hack
ClearList(b())
Re: Quickly concatenating linked lists?
Posted: Fri Aug 13, 2010 11:10 pm
by Little John
Hi,
thanks for your reply.
A internal representation of sorts for a linked-list's data used to be included in the manual but has been removed several revisions ago.
I'm glad you wrote that, since I recalled something like that, but couldn't find that information in the docs anymore. So I actually wasn't sure whether or not I could trust my memory.
Code: Select all
;create a copy of source list's first element
AddElement(a())
a() = b()
Is it required to do so?
I came up with the following code, which seems to work, too:
Code: Select all
;-- Step 2: "move" all elements from list b() to list a()
;-----------------------------
Structure Element
*next.Element
*prev.Element
value.i
EndStructure
off = OffsetOf(Element\value)
;-----------------------------
If ListSize(a()) > 0 And ListSize(b()) > 0
LastElement(a())
FirstElement(b())
PokeI(@a()-off, @b()-off) ; last element of a() -> first element of b()
PokeI(@b()-off/2, @a()-off) ; last element of a() <- first element of b()
ClearList(b())
EndIf
It works but has one major flaw, it doesn't update the ListSize.
Oh, yes. I didn't think of ListSize() at all.

Thanks again for your commitment!
Regards, Little John
Re: Quickly concatenating linked lists?
Posted: Sat Aug 14, 2010 5:32 am
by Demivec
Little John wrote:Code: Select all
;create a copy of source list's first element
AddElement(a())
a() = b()
Is it required to do so?
I came up with the following code, which seems to work, too:
Well, the way I figured it there are two parts to each list, the header and the data elements. The first element of a list is linked to by the list's header. I duplicate this element as part of the concatenation so that I can modify links to it without modifying the header.
In your code for instance, when you use ClearList(b()), the elements of b() are still linked to by the header and to each other. This means they will be freed. They are still accessible for the moment because they are put back into the pool of free elements (and so can be read) but if more elements are added they will be overwritten and relinked.
In my example I could modify the first element to point to #Null after I detached the rest of the list, resulting in a short list pointed to by the list's header. This allowed ClearList() to place just the first and now only element of b() into the free pool without bothering any of the others.
Re: Quickly concatenating linked lists?
Posted: Sat Aug 14, 2010 9:23 am
by Little John
I see now, that's a good trick. Thank you for the detailed explanation.
I found
a post with code that deals with the header of a list. I'll be out of town for a few days, when I'm back I'll have a closer look at it.
But there actually should be a native implemantation of this in PB, since it can be very useful (e.g. for a MergeSort routine), and also concatenation IMHO is a "natural" operation on lists, which comes at almost no cost.
Thanks again, Little John
Re: Quickly concatenating linked lists?
Posted: Sat Aug 14, 2010 9:33 am
by KJ67
@Demivec:
If asking for concatenation function for lists, should it now also be a SplitList() to complete this functionality?
Re: Quickly concatenating linked lists?
Posted: Sat Aug 14, 2010 1:09 pm
by Demivec
KJ67 wrote:@Demivec:
If asking for concatenation function for lists, should it now also be a SplitList() to complete this functionality?
@KJ67: How would that function? Feel free to add to the feature request thread I started for joining lists ... I know there are at least a few missing functions that shouldn't be hard to implement. The main question is whether it is considered worthwhile or not.
Since these functions involve manipulating the links as well as the list's header it makes sense to implement them as native functions. As you can see from the solutions above, if it involves manipulating the list's header it's not going to work with any solutions that I or anyone else comes up with.
I was reminded of the need for some of these functions as I was working on some of the solutions for Rosetta Code.

Re: Quickly concatenating linked lists?
Posted: Sun Aug 15, 2010 11:58 pm
by freak
Do not mix up the contents of different lists like that. You will get in trouble if you use ClearList() or one of the lists goes out of scope (and is destroyed).
Re: Quickly concatenating linked lists?
Posted: Mon Aug 16, 2010 4:13 am
by Demivec
freak wrote:Do not mix up the contents of different lists like that. You will get in trouble if you use ClearList() or one of the lists goes out of scope (and is destroyed).
@freak: The contents were mixed up on purpose. It was clearly stated that it was just an imperfect hack that resulted in a non-up-to-date list header. Notwistanding that, ClearList() was used and no harm seem to come from it. Please look favorably on the corresponding feature request that resulted.
Re: Quickly concatenating linked lists?
Posted: Sun Aug 29, 2010 4:46 pm
by Little John
Little John wrote:I found
a post with code that deals with the header of a list. I'll be out of town for a few days, when I'm back I'll have a closer look at it.
In the
current help for ResetList() it reads:
This function does not return any value.
Well, using PB 4.51 RC 2 x86 on Windows, it
does return a value here.
However, I couldn't manage to run the code from the link mentioned above properly with the current PB version.
Regards, Little John