[Implemented] Merging linked lists

[DarkDragon]

Hello,

I need to merge 2 linked lists and I have no idea how to do this as purebasic doesn't give the possibility to do this. Copying all elements is not the right method to do this, but I'll show you what I mean with this code:

Code: Select all

NewList ListA.i()
NewList ListB.i()

AddElement(ListA()) : ListA() = 1
AddElement(ListA()) : ListA() = 3

AddElement(ListB()) : ListB() = 2

Debug "ListA contains:"
ForEach ListA()
  Debug ListA()
Next
Debug ""

Debug "ListB contains:"
ForEach ListB()
  Debug ListB()
Next
Debug ""
Debug ""

Procedure AddListToList(List Source.i(), List Destination.i())
  ForEach Source()
    AddElement(Destination())
    Destination() = Source()
  Next
  
  ClearList(Source())
EndProcedure

Debug "Concatenating ListB into ListA after the second element"
SelectElement(ListA(), 0)
AddListToList(ListB(), ListA())

Debug "ListA contains:"
ForEach ListA()
  Debug ListA()
Next
Debug ""

Debug "ListB contains:"
ForEach ListB()
  Debug ListB()
Next
Debug ""

It just inserts ListB into ListA after the current element. But ListB shouldn't exist afterwards anymore (So moving pointers would be better than copying elements). Its a typical operation that is missing for linked lists in purebasic (Except self written, but who wants to do this with a large code using pb linked lists?).

[jamirokwai]

It just inserts ListB into ListA after the current element. But ListB shouldn't exist afterwards anymore (So moving pointers would be better than copying elements). Its a typical operation that is missing for linked lists in purebasic (Except self written, but who wants to do this with a large code using pb linked lists?).

Hi DarkDragon,

why don't you trash ListB after the copy-procedure?
Nonetheless, a PB-native list-merging-command would come in handy when needed

[Little John]

(So moving pointers would be better than copying elements). Its a typical operation that is missing for linked lists in purebasic

I absolutely agree.
This has been requested already some months ago.

why don't you trash ListB after the copy-procedure?

It doesn't make sense to copy and then delete (maybe thousands of) elements, when the only thing actually required would be changing the value of two or three pointers.

Regards, Little John

[Seymour Clufley]

why don't you trash ListB after the copy-procedure?

It doesn't make sense to copy and then delete (maybe thousands of) elements, when the only thing actually required would be changing the value of two or three pointers.

Can't you use FreeList(ListB()) ?

[IdeasVacuum]

Copying all elements is not the right method

Well, the right method is the fastest method.

Copying ListB to ListA and Merging two lists might be entirely different operations. A merge could be described as adding only those values from ListB to ListA that do not already exist in ListA. On the other hand, duplicate values in the list could be accepted/required, so that would be a copy or append action. A further possibility is that a value in ListB should overwrite a value in ListA. So, 3 functions for you, depending on requirements.

[DarkDragon]

Maybe this describes it better:

Code: Select all

Structure PathPoint
  x.i
  y.i
EndStructure

Structure OwnLLPathPoint Extends PathPoint
  *nxt.OwnLLPathPoint
EndStructure

#AMOUNT_OF_ELEMENTS_A = 10000
#AMOUNT_OF_ELEMENTS_B = 10000000


Define Time.i

Define k.i

; the pb method
NewList Copy_PathA.PathPoint()
NewList Copy_PathB.PathPoint()

Procedure AddListToList(List Source.PathPoint(), List Destination.PathPoint())
  ForEach Source()
    AddElement(Destination())
    CopyStructure(@Source(), @Destination(), PathPoint)
  Next
 
  ClearList(Source())
EndProcedure

For k = 0 To #AMOUNT_OF_ELEMENTS_A - 1
  AddElement(Copy_PathA())
  Copy_PathA()\x = k
  Copy_PathA()\y = #AMOUNT_OF_ELEMENTS_A - k
Next k

For k = 0 To #AMOUNT_OF_ELEMENTS_B - 1
  AddElement(Copy_PathB())
  Copy_PathB()\x = 0
  Copy_PathB()\y = k
Next k

FirstElement(Copy_PathA())

Time = ElapsedMilliseconds()
AddListToList(Copy_PathB(), Copy_PathA())
Time = ElapsedMilliseconds() - Time
MessageRequester("Copy method", Str(Time) + "ms needed")

Debug "first few elements (copy)"
k = 10
ForEach Copy_PathA()
  k - 1
  If k <= 0
    Break
  EndIf
  
  Debug Str(Copy_PathA()\x) + "  " + Str(Copy_PathA()\y)
Next

; moving pointers method
Define *firstA.OwnLLPathPoint
Define *firstB.OwnLLPathPoint

Define *currentA.OwnLLPathPoint
Define *currentB.OwnLLPathPoint

For k = 0 To #AMOUNT_OF_ELEMENTS_A - 1
  If *currentA <> #Null
    *currentA\nxt = AllocateMemory(SizeOf(OwnLLPathPoint))
    *currentA = *currentA\nxt
  Else
    *currentA = AllocateMemory(SizeOf(OwnLLPathPoint))
  EndIf
  
  *currentA\x = k
  *currentA\y = #AMOUNT_OF_ELEMENTS_A - k
  
  If k = 0
    *firstA = *currentA
  EndIf
Next k

For k = 0 To #AMOUNT_OF_ELEMENTS_B - 1
  If *currentB <> #Null
    *currentB\nxt = AllocateMemory(SizeOf(OwnLLPathPoint))
    *currentB = *currentB\nxt
  Else
    *currentB = AllocateMemory(SizeOf(OwnLLPathPoint))
  EndIf
  
  *currentB\x = 0
  *currentB\y = k
  
  If k = 0
    *firstB = *currentB
  EndIf
Next k

Time = ElapsedMilliseconds()
If *currentB <> #Null
  *currentB\nxt = *firstA\nxt
  *firstA\nxt = *firstB
EndIf
Time = ElapsedMilliseconds() - Time
MessageRequester("Moving pointers method", Str(Time) + "ms needed")

Debug "first few elements (pointer)"
k = 10
*currentA = *firstA
While *currentA <> #Null
  k - 1
  If k <= 0
    Break
  EndIf
  
  Debug Str(*currentA\x) + "  " + Str(*currentA\y)
  *currentA = *currentA\nxt
Wend

I want to have the possibility to use the pointer method in purebasic linkedlists.

It has definately nothing to do with removing duplicates. All I want to do is append the ListB (or parts of it) after the current element of ListA without copying the elements.