Quickly concatenating linked lists?

[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

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

[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())

[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

[Demivec]

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.

[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

[KJ67]

@Demivec:
If asking for concatenation function for lists, should it now also be a SplitList() to complete this functionality?

[Demivec]

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

[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).

[Demivec]

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.

[Little John]

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