Not a bug, but lists are nearly useless because of speed

[technicorn]

Or better said, because lack of speed.

Try this and you see what I mean:

Code: Select all

EnableExplicit

Define n.l, nEnd.l = 5000
Define i.l, iEnd.l = 10000
Define tStart.l, tExec1.d, tExec2.d

NewList l1.l()

For i = 1 To iEnd
  AddElement(l1())
  l1() = i
Next i

tStart = ElapsedMilliseconds()
For n = 1 To nEnd
  For i = 1 To 10
    SelectElement(l1(), i)
  Next i
Next n
tExec1 = (ElapsedMilliseconds() - tStart) / 1000.0

tStart = ElapsedMilliseconds()
For n = 1 To nEnd
  For i = 9990 To 10000
    SelectElement(l1(), i)
  Next i
Next n
tExec2 = (ElapsedMilliseconds() - tStart) / 1000.0


MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end:   " + StrD(tExec2, 3))

If you have a slow comp, the second part might take some minutes!

I understand that going from one index in the list to another means,
the program has to scan over all items inbetween,
but going, for example, from index 9999 to 10000 should be the same
as using NextElement(), but instead the list is always scanded from the start!!

The linkedlist library already uses a flag to avoid the problem of
using ChangeCurrentElement() (at least it was so in previous versions),
which will make the list index invalide.
But using ListIndex() rescaned the list once and reseted the flag to show
that the index is valide again, so way not use this flag to have a save way
to go from one index of SelectIndex() to another in a faster way?

And before someone suggested to use NextElement() to go from index 9999 to 10000,
this was just an example for the (slow-)speed, it is also true for 7777 to 666

And I would rather not have to use a loop with NextElement() / PreviousElement() to iterate throgh the list,
which is much faster at the moment.

Greatings
technicorn

[Trond]

If you need fast random access use an array.

[technicorn]

That isn't an option if you have a huge count of items, and the
amount of items is constantly changing.

For example a server program, where people log on and off,
or databases.

Using an array for such tasks you
1. Have to redim it, at least for adding items,
2. Keep track of empty entries, or copy all itmes after a removed one down on place
that would be very impractical if the removed one was the first of, say 100000 items.

Or if you have to keep the array sorted that would mean copy 99999 items to higher places,
if the new item has to go in front of all other,
with a list that is just a question of adding one element at the front.

[Derek]

Get a faster computer, only takes 3.4 seconds on mine.

But you are right, there should be a flag to say it is ok to use faster methods of scanning.

[Trond]

That isn't an option if you have a huge count of items, and the
amount of items is constantly changing.

For example a server program, where people log on and off,
or databases.

Using an array for such tasks you
1. Have to redim it, at least for adding items,
2. Keep track of empty entries, or copy all itmes after a removed one down on place
that would be very impractical if the removed one was the first of, say 100000 items.

Or if you have to keep the array sorted that would mean copy 99999 items to higher places,
if the new item has to go in front of all other,
with a list that is just a question of adding one element at the front.

If lists could be as fast as arrays for random access we wouldn't have arrays. And if you could quickly insert items at the start of an array we wouldn't have lists.

That being said, there is absolutely NO reason EVER to use SelectElement(). Everything it does can be done faster with other functions.

[technicorn]

@Derek

Takes 6.8 sec. on mine, just wrote that, so no one with a slower comp. think the program hangs.

@Trond

So what would that faster method be?
Using Previous/NextElement() ?
When I can program that in a loop in PB, why can't the lib do that in asm.

And yes, I could do that in asm myself, but that's beside the point
of having a function like SelectElement() for people who don't want to learn asm,
and it wouldn't be neither cross platform, nor version save,
like some of the userlibs.

[Trond]

@Trond

So what would that faster method be?
Using Previous/NextElement() ?
When I can program that in a loop in PB, why can't the lib do that in asm.

And yes, I could do that in asm myself, but that's beside the point
of having a function like SelectElement() for people who don't want to learn asm,
and it wouldn't be neither cross platform, nor version save,
like some of the userlibs.

I don't understand the problem. Just avoid SelectElement(). You don't need it, ever. The reason for that, is that the following uses covers everything possible:
- If you want to access every element of the list going forwards you use a ForEach() loop.
- If you want to access every element of the list going backwards, you use a LastElement() followed by a For loop with PreviousElement().
- If you want to access a subrange of the list you should use one SelectElement() before a For loop with a NextElement() (or a PreviousElement() depending on which order you want to access the lements).
- If you want to access one particular element by ID you use ChangeCurrentElement().

That covers every use possible of the linked list, and you don't need (or want!!!!!!!!!!!!!!) SelectElement(). Where exactly is the problem? Did you read the manual?

[pcfreak]

here you have some workaround, btw you can't select the last element of a linkedlist with 10000 items by selecting position 10000 as the index is zero-based (possible values from 0 to 9999)

Code: Select all

Enumeration
 ;creates the linked list
 #DLL_CREATE_LIST
 ;adds an element to the end of the linked list
 #DLL_ADD_ELEMENT
 ;adds an element to the position of the current selected element
 #DLL_INSERT_ELEMENT
 ;deletes the currently selected element
 #DLL_DEL_ELEMENT
 ;moves the pointer to the next element
 #DLL_NEXT_ELEMENT
 ;moves the pointer to the previous element
 #DLL_PRIOR_ELEMENT
 ;moves the pointer to the first element
 #DLL_FIRST_ELEMENT
 ;moves the pointer to the last element
 #DLL_LAST_ELEMENT
 ;returns the index of the current element (-1 = no element selected, 0 = first element)
 #DLL_GET_INDEX
 ;moves the pointer to the element defined
 #DLL_SELECT_ELEMENT
 ;returns the number of elements in the linked list
 #DLL_COUNT_ELEMENTS
 ;resets to pointer
 #DLL_RESET_LIST
 ;deletes all elements of the linked list
 #DLL_CLEAR_LIST
 ;deletes all elements of the linked list and the linked list itself, returns 0 if successful
 #DLL_DELETE
EndEnumeration

Macro CreateDoublyLinkedListClass(dataVariable, dataType)
CompilerIf Defined(DoublyLinkedList_#dataType, #PB_Procedure)=#False
 Structure DOUBLY_LINKED_LIST_STRUC_#dataType
  size.l
  index.l
  *first.DOUBLY_LINKED_LIST_ENTRY_#dataType
  *last.DOUBLY_LINKED_LIST_ENTRY_#dataType
  *current.DOUBLY_LINKED_LIST_ENTRY_#dataType
 EndStructure
 
 Structure DOUBLY_LINKED_LIST_ENTRY_#dataType
  *after.DOUBLY_LINKED_LIST_ENTRY_#dataType
  *before.DOUBLY_LINKED_LIST_ENTRY_#dataType
  dataVariable#.dataType#
 EndStructure
 
 Procedure.l DoublyLinkedList_#dataType#(option.l, *handle.DOUBLY_LINKED_LIST_STRUC_#dataType = 0, flag.l = 0)
  Select option
   Case #DLL_CREATE_LIST
    *handle = 0
    *handle.DOUBLY_LINKED_LIST_STRUC_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_STRUC_#dataType))
    If *handle<>0
     *handle\size    = 0
     *handle\index   = -1
     *handle\first   = 0
     *handle\last    = 0
     *handle\current = 0
    EndIf
   Case #DLL_ADD_ELEMENT
    If *handle<>0
     *newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
     If *newEntry
      *handle\index = *handle\size
      *handle\size + 1
      If *handle\last=0
       *handle\first   = *newEntry
       *handle\last    = *newEntry
      Else
       *newEntry\before   = *handle\last
       *handle\last\after = *newEntry
       *handle\last       = *newEntry
      EndIf
      *handle\current = *newEntry
     EndIf
    EndIf
   Case #DLL_INSERT_ELEMENT
    If *handle<>0
     *newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
     If *newEntry
      *handle\size + 1
      If *handle\current = 0
       *handle\index = -1
       If *handle\first=0
        *handle\first   = *newEntry
        *handle\last    = *newEntry
       Else
        *newEntry\after      = *handle\first
        *handle\first\before = *newEntry
        *handle\first        = *newEntry
       EndIf
      Else
       If *handle\current\before=*handle\first
        *newEntry\after      = *handle\first
        *handle\first\before = *newEntry
        *handle\first        = *newEntry
        *handle\current      = *newEntry
       Else
        *newEntry\after              = *handle\current
        *newEntry\before             = *handle\current\before
        *handle\current\before\after = *newEntry
        *handle\current\before       = *newEntry
        *handle\current              = *newEntry
       EndIf
      EndIf
     EndIf
    EndIf
   Case #DLL_DEL_ELEMENT
    If *handle<>0
     If *handle\current<>0
      *handle\size - 1
      If *handle\current=*handle\first And *handle\current=*handle\last
       FreeMemory(*handle\current)
       *handle\first   = 0
       *handle\last    = 0
       *handle\current = 0
       *handle\index   = -1
      ElseIf *handle\current=*handle\first
       *handle\first        = *handle\first\after
       *handle\first\before = 0
       FreeMemory(*handle\current)
       *handle\current      = *handle\first
      ElseIf *handle\current=*handle\last
       *handle\last       = *handle\last\before
       *handle\last\after = 0
       FreeMemory(*handle\current)
       *handle\current    = *handle\last
       *handle\index      - 1
      Else
       *newCurrent.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle\current\after
       *handle\current\before\after                   = *handle\current\after
       *handle\current\after\before                   = *handle\current\before
       FreeMemory(*handle\current)
       *handle\current                                = *newCurrent
      EndIf
     EndIf
    EndIf
   Case #DLL_NEXT_ELEMENT
    If *handle<>0
     If *handle\current=0
      *handle\current = *handle\first
      *handle\index   = 0
     ElseIf *handle\current=*handle\last
      *handle\current = 0
      *handle\index   = -1
     Else
      *handle\current = *handle\current\after
      *handle\index   + 1
     EndIf
    EndIf
   Case #DLL_PRIOR_ELEMENT
    If *handle<>0
     If *handle\current=0
      *handle\current = *handle\last
      *handle\index   = *handle\size - 1
     ElseIf *handle\current=*handle\first
      *handle\current = 0
      *handle\index   = -1
     Else
      *handle\current = *handle\current\before
      *handle\index   - 1
     EndIf
    EndIf
   Case #DLL_FIRST_ELEMENT
    If *handle<>0
     *handle\current = *handle\first
     *handle\index   = 0
    EndIf
   Case #DLL_LAST_ELEMENT
    If *handle<>0
     *handle\current = *handle\last
     *handle\index   = *handle\size - 1
    EndIf
   Case #DLL_GET_INDEX
    If *handle<>0
     ProcedureReturn *handle\index
    EndIf
   Case #DLL_SELECT_ELEMENT
    If *handle<>0
     If flag<0 Or flag>=*handle\size
      *handle\current = 0
      *handle\index   = -1
     ElseIf flag=0 And *handle\first
      *handle\current = *handle\first
      *handle\index   = 0
     ElseIf flag=*handle\size-1
      *handle\current = *handle\last
      *handle\index   = *handle\size - 1
     ElseIf flag<*handle\index
      If flag<*handle\index-flag
       *handle\current = *handle\first
       For i=1 To flag
        *handle\current = *handle\current\after
       Next
       *handle\index = flag
      Else
       While *handle\index > flag
        *handle\current = *handle\current\before
        *handle\index   - 1
       Wend
      EndIf
     ElseIf flag>*handle\index
      If *handle\current=0
       If flag<(*handle\size-1)-flag
        *handle\current = *handle\first
        For i=1 To flag
         *handle\current = *handle\current\after
        Next
        *handle\index = flag
       Else
        *handle\current = *handle\last
        *handle\index   = *handle\size - 1
        While *handle\index > flag
         *handle\current = *handle\current\before
         *handle\index   - 1
        Wend
       EndIf
      Else
       If (*handle\size-1)-flag<flag-*handle\index
        *handle\current = *handle\last
        *handle\index   = *handle\size - 1
        While *handle\index > flag
         *handle\current = *handle\current\before
         *handle\index   - 1
        Wend
       Else
        While *handle\index < flag
         *handle\current = *handle\current\after
         *handle\index   + 1
        Wend
       EndIf
      EndIf
     EndIf
    EndIf
   Case #DLL_COUNT_ELEMENTS
    If *handle<>0
     ProcedureReturn *handle\size
    EndIf
   Case #DLL_RESET_LIST
    If *handle<>0
     *handle\current = 0
     *handle\index   = -1
    EndIf
   Case #DLL_CLEAR_LIST
    If *handle<>0
     If *handle\size<>0
      *handle\current = *handle\first
      *nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
      While *handle\current<>0
       *nextElement    = *handle\current\after
       FreeMemory(*handle\current)
       *handle\current = *nextElement
      Wend
      *handle\first   = 0
      *handle\last    = 0
      *handle\current = 0
      *handle\index   = -1
     EndIf
    EndIf
   Case #DLL_DELETE
    If *handle<>0
     If *handle\size<>0
      *handle\current = *handle\first
      *nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
      While *handle\current<>0
       *nextElement    = *handle\current\after
       FreeMemory(*handle\current)
       *handle\current = *nextElement
      Wend
      FreeMemory(*handle)
      *handle = 0
     EndIf
    EndIf
  EndSelect
  ProcedureReturn *handle
 EndProcedure
CompilerEndIf
EndMacro

Macro InitDoublyLinkedListSortField(dataType, id, field, caseSensitive=1)
CompilerIf Defined(SortDoublyLinkedListByField_#dataType#id, #PB_Procedure)=#False
 Procedure.l SortDoublyLinkedListByField_#dataType#id#(*handle1.DOUBLY_LINKED_LIST_STRUC_#dataType, option=0)
  If *handle1<>0
   If *handle1\size>1
    *handle2.DOUBLY_LINKED_LIST_STRUC_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_STRUC_#dataType))
    If *handle2<>0
     *handle2\size    = *handle1\size
     For i=1 To *handle1\size
      *newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
      If *newEntry<>0
       If *handle2\current=0
        *handle2\current = *newEntry
        *handle2\first   = *newEntry
       Else
        *newEntry\before       = *handle2\current
        *handle2\current\after = *newEntry
        *handle2\current       = *newEntry
       EndIf
      EndIf
     Next
     *handle2\last = *handle2\current
     ;sort here >>
     left.l = 1
     right.l = 1
     start.l = 0
     sortLen = 1
     length.l = *handle1\size
     While left <= length
      sortLen << 1
      start = 0
      *handle2\current = *handle2\first
      *pointerL.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle1\first
      *pointerR.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle1\first
      changedOrder.l = #False
      While start < length
       If (length - start) < sortLen
        If (length - start) > (sortLen >> 1)
         left = sortLen >> 1
         right = length - start - left
        Else
         left = length - start
         right = 0
        EndIf
       EndIf
       posL.l = start
       posR.l = start + left
       posM.l = 0
       If start=0
        For i=1 To left
         *pointerR = *pointerR\after
        Next
       Else
        For i=1 To sortLen>>1
         *pointerL = *pointerL\after
        Next
        *pointerR = *pointerL
        For i=1 To left
         *pointerR = *pointerR\after
        Next
       EndIf
       While (posL < (start + left)) And (posR < (start + left + right))
        CompilerIf caseSensitive=1
         If option = 0
          If *pointerL\field# <= *pointerR\field#
           CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerL = *pointerL\after
           posL + 1
          Else
           CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerR = *pointerR\after
           posR + 1
           changedOrder = #True
          EndIf
         Else
          If *pointerL\field# >= *pointerR\field#
           CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerL = *pointerL\after
           posL + 1
          Else
           CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerR = *pointerR\after
           posR + 1
           changedOrder = #True
          EndIf
         EndIf
        CompilerElse
         If option = 0
          If LCase(*pointerL\field#) <= LCase(*pointerR\field#)
           CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerL = *pointerL\after
           posL + 1
          Else
           CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerR = *pointerR\after
           posR + 1
           changedOrder = #True
          EndIf
         Else
          If LCase(*pointerL\field#) >= LCase(*pointerR\field#)
           CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerL = *pointerL\after
           posL + 1
          Else
           CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
           *pointerR = *pointerR\after
           posR + 1
           changedOrder = #True
          EndIf
         EndIf
        CompilerEndIf
        *handle2\current = *handle2\current\after
        posM + 1
       Wend
       While (posL < (start + left))
        *nextEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle2\current\after
        CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
        *pointerL = *pointerL\after
        *handle2\current = *handle2\current\after
        posL + 1
        posM + 1
       Wend
       While (posR < (start + left + right))
        *nextEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle2\current\after
        CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
        *pointerR = *pointerR\after
        *handle2\current = *handle2\current\after
        posR + 1
        posM + 1
       Wend
       start = start + sortLen
      Wend
      Swap *handle1, *handle2
      left  = sortLen
      right = sortLen
      If changedOrder = #False
       Break
      EndIf
     Wend
     *handle2\current = *handle2\first
     *nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
     While *handle2\current<>0
      *nextElement     = *handle2\current\after
      FreeMemory(*handle2\current)
      *handle2\current = *nextElement
     Wend
     ;sort here <<
     FreeMemory(*handle2)
    EndIf
   EndIf
   *handle1\current =  0
   *handle1\index   = -1
  EndIf
  ProcedureReturn *handle1
 EndProcedure
CompilerEndIf
EndMacro

Macro SortDoublyLinkedListByField(dataType, id, handle, option=0)
 SortDoublyLinkedListByField_#dataType#id#(handle, option)
EndMacro

Macro DefineDoublyLinkedList(variable, dataType)
 variable#.DOUBLY_LINKED_LIST_STRUC_#dataType
EndMacro

Macro DoublyLinkedList(dataType, option, handle=0, flag=0)
 DoublyLinkedList_#dataType#(option, handle, flag)
EndMacro

Macro DLLForEach(handle)
 If handle#\first
  handle#\current = handle#\first
  handle#\index   = 0
  While handle#\current<>0
EndMacro

Macro DLLNext(handle)
   handle#\current = handle#\current\after
   handle#\index   + 1
  Wend
  handle#\index=-1
 EndIf
EndMacro



CreateDoublyLinkedListClass(value, l)
InitDoublyLinkedListSortField(l, 1, value)
DefineDoublyLinkedList(*list1, l)

*list1 = DoublyLinkedList(l, #DLL_CREATE_LIST)
For a = 0 To 10000
 *list1 = DoublyLinkedList(l, #DLL_ADD_ELEMENT, *list1)
 *list1\current\value = a
Next


tStart.l = ElapsedMilliseconds()
For n = 1 To 5000
 For i = 1 To 10
  *list1 = DoublyLinkedList(l, #DLL_SELECT_ELEMENT, *list1, i)
 Next
Next
tExec1.d = (ElapsedMilliseconds() - tStart) / 1000.0


tStart = ElapsedMilliseconds()
For n = 1 To 5000
 For i = 9990 To 10000
  *list1 = DoublyLinkedList(l, #DLL_SELECT_ELEMENT, *list1, i)
 Next
Next
tExec2.d = (ElapsedMilliseconds() - tStart) / 1000.0


*list1 = DoublyLinkedList(l, #DLL_DELETE, *list1)


MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end:   " + StrD(tExec2, 3))

[Fred]

SelectElement() isn't optimized for speed, it is a convenience function. You have to use Previous/NextElement() to iterate through the list with maximum speed.

BTW, rewriting SelectElement() in asm won't change anything, it's an algorithm problem.

[Ollivier]

Else you can create a temporary array during the treatment.

Code: Select all

Procedure Map(Lst() ) 
  max.L = CountList(Lst() ) 
  Global Dim *Ptr(max) 
  n.L = 0 
  ResetList(Lst())          
  While NextElement(Lst())  
    *Ptr(n) = @Lst() 
    n + 1 
  Wend      
EndProcedure 

Procedure EndMap() 
  Global Dim *Ptr(0) 
EndProcedure 

Define n.l, nEnd.l = 5000 
Define i.l, iEnd.l = 10000 
Define tStart.l, tExec1.d, tExec2.d 

NewList l1.l() 

For i = 1 To iEnd 
  AddElement(l1()) 
  l1() = i 
Next i 

Map(l1() ) 
  tStart = ElapsedMilliseconds() 
  For n = 1 To nEnd 
    For i = 1 To 10 
      ;SelectElement(l1(), i) 
      ChangeCurrentElement(l1(), *Ptr(i) ) 
    Next i 
  Next n 
  tExec1 = (ElapsedMilliseconds() - tStart) / 1000.0 

  tStart = ElapsedMilliseconds() 
  For n = 1 To nEnd 
    For i = 9990 To 10000 
      ;SelectElement(l1(), i) 
      ChangeCurrentElement(l1(), *Ptr(i) ) 
    Next i 
  Next n 
tExec2 = (ElapsedMilliseconds() - tStart) / 1000.0 
EndMap() 


MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end:   " + StrD(tExec2, 3)) 

[technicorn]

Thanks pcfreak and Ollivier,
but I want to stick with the PB lists, because they can be viewed with the debugger,
and already using an algorithm to get faster to the wanted index by avoiding SelectElement().

@Fred
I was just surprised that SelectElement() isn't using the same flag that ListIndex() does to select an internal prev/next algo to get to the selected element.
I'll simply avoid using SelectElement() now that I know that.

[Ollivier]

I don't understand what do you really want : 'stick with the PB list'
What is the goal?

[nco2k]

SelectElement() isn't optimized for speed, it is a convenience function. You have to use Previous/NextElement() to iterate through the list with maximum speed.

fred, the problem is that SelectElement() ignores the current index position and always starts to search from the beginning of the list. it would be much faster, if it would behave like in this example by Deem2031:

Code: Select all

EnableASM

Structure PB_LinkedListData_Struc 
  *FirstElement.PB_LinkedListElement_Struc ; FirstElement(LL()): = @LL()-8 
  *LastElement.PB_LinkedListElement_Struc ; LastElement(LL()): = @LL()-8 
  SizeofElement.l ; (Structure + *NextElement.l and *PrevElement.l (8 Byte)) 
  AmountofElements.l ; = CountList() 
  NumberofCurrentElement.l ; = ListIndex() + 1 (with the normal PB 3.92 LL-Library NumberofCurrentElement.l is equal to the result of ListIndex(), with the new one from purebasic.com/beta its bigger by 1) 
  StructureMap.l ; "the StructureMap is the address of the structure associated with the list, so if there is string in it they can be freed easily" by AlphaSND (explained at the end of the file) 
  IsSetNumberofCurrentElement.l ; Is NumberofCurrentElement saving the correct value? (0=yes,other=no) 
EndStructure 

Structure PB_LinkedListElement_Struc 
  *NextElement.l 
  *PrevElement.l 
  ;[...] Content 
EndStructure 

Structure PB_LinkedList_Struc 
  *PB_LinkedListData.PB_LinkedListData_Struc 
  *CurrentElement.PB_LinkedListElement_Struc 
EndStructure 

Global NewList Liste() 

DisableDebugger 
Procedure SelectElement2(LinkedList(),Position) 
  Protected *LL.PB_LinkedList_Struc 
  MOV *LL, Eax ;LinkedList() 
  
  LastElement = *LL\PB_LinkedListData\AmountofElements - 1 
  
  WaytoLast = LastElement - Position 
  If WaytoLast < 0 Or Position < 0 
    ;invalid position 
    ProcedureReturn #False 
  EndIf 
  WaytoFirst = Position 
    
  If *LL\PB_LinkedListData\IsSetNumberofCurrentElement = 0 ;We know the index of the current element 
    CurrentElement = *LL\PB_LinkedListData\NumberofCurrentElement - 1 
    
    WaytoCurrent = Position - CurrentElement 
    
    If Abs(WaytoCurrent) < WaytoLast And Abs(WaytoCurrent) < WaytoFirst ; The distance from the current element to element at 'position' is smaller than to the first or last element 
      While WaytoCurrent < 0 ;so we go back if WaytoCurrent < 0 ... 
        PreviousElement(LinkedList()) 
        WaytoCurrent + 1 
      Wend 
      While WaytoCurrent > 0 ;or forward to reach 'position' 
        NextElement(LinkedList()) 
        WaytoCurrent - 1 
      Wend 
    ElseIf WaytoLast < WaytoFirst 
      LastElement(LinkedList()) 
      While WaytoLast 
        PreviousElement(LinkedList()) 
        WaytoLast - 1 
      Wend 
    Else 
      FirstElement(LinkedList()) 
      While WaytoFirst 
        NextElement(LinkedList()) 
        WaytoFirst - 1 
      Wend 
    EndIf 
  Else ; We dont know it :) 
    If WaytoLast < WaytoFirst 
      LastElement(LinkedList()) 
      While WaytoLast 
        PreviousElement(LinkedList()) 
        WaytoLast - 1 
      Wend 
    Else 
      FirstElement(LinkedList()) 
      While WaytoFirst 
        NextElement(LinkedList()) 
        WaytoFirst - 1 
      Wend 
    EndIf 
  EndIf 
  ProcedureReturn @LinkedList() 
EndProcedure 
EnableDebugger 

Debug "Liste füllen" 
Start = ElapsedMilliseconds() 
For a = 0 To 20000 
  AddElement(Liste()) 
  Liste() = a 
Next 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------" 

Debug "Mit PreviousElement()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While ListIndex(Liste()) <> 0 
  PreviousElement(Liste()) 
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------" 

ListenEnde = CountList(Liste()) - 1 
Debug "Mit SelectElement()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While pos <> 0 
  SelectElement(Liste(), pos) 
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------" 

ListenEnde = CountList(Liste()) - 1 
Debug "Mit SelectElement2()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While pos <> 0 
  SelectElement2(Liste(), pos) 
  If ListIndex(Liste()) <> pos 
    MessageRequester(Str(ListIndex(Liste())),Str(pos),16) 
    End 
  EndIf 
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------"

a position dependent SelectElement() was requested many times, i dont understand why it hasnt been changed yet.

c ya,
nco2k

[Trond]

a position dependent SelectElement() was requested many times, i dont understand why it hasnt been changed yet.

World peace was also requested quite a few times. Besides, as I said above, you never need SelectElement().

[Ollivier]

It's clear! I'm ok with Trond : using an array is the best solution, I posted the code above. If you want to know where there is a bug, you create a 2nd array. Each element of this second array can contain flags and values allowing tracability. It's speed. If there's a problem of available memory, you could use a memory area instead of these arrays.

I think 'SelectElement' was created to avoid allocating too much memory!

Nice coding