Page 1 of 1
[Implemented] Merging linked lists
Posted: Thu Dec 23, 2010 10:59 am
by 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?).
Re: Merging linked lists
Posted: Thu Dec 23, 2010 1:54 pm
by jamirokwai
DarkDragon wrote: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
Re: Merging linked lists
Posted: Thu Dec 23, 2010 3:33 pm
by Little John
DarkDragon wrote:(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.
jamirokwai wrote: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
Re: Merging linked lists
Posted: Fri Dec 24, 2010 12:47 am
by Seymour Clufley
Little John wrote:jamirokwai wrote: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()) ?
Re: Merging linked lists
Posted: Fri Dec 24, 2010 1:21 am
by 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.
Re: Merging linked lists
Posted: Fri Dec 24, 2010 10:59 am
by 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.