A better way to traverse a list.

Right now I have a function that goes something like this...

integer i;
for (i = 0; i < llGetListLength(traverse_me); i++) {
   string curr_element = llList2String(traverse_me, i);
   process_element (curr_element);
}

Is there... a better way? This looks O(n^2) to me, and there really should be a O(n) way to do this.

integer i;
for (i = 0; i < llGetListLength(traverse_me); i++) {
   string curr_element = llList2String(traverse_me, i);
   process_element (curr_element);
}

I dare say that's how it's done!
It's not as tidy as yer basic thing[index] notation, but it gets the job done. And there's no reason to think that it's O(n^2).

You could find out using llGetTime() if you're curious.
also...

integer n = llGetListLength(traverse_me);
for(i = 0; i < n; i++) { ...

...might be polite.

a better way is to do

for (i = (llGetListLength(traverse_me) - 1); i >= 0; i -= 1) {

because it only uses llGetListLength(traverse_me) once rather than on each iteration. But, that also steps through the list last first.

if you need to go from the start to the end then:

integer list_length = llGetListLength(traverse_me);
integer i;
for (i = 0; i < list_length; i += 1) {

Good optimisation, Davan and Rickard - and one which ppl frequently forget.

For a single lookup, Davan, you're quite right.
Normal arrays usually have constant time lookup T(n)=c, while linked-lists (which I think is what LSL uses) are usually O(n), i.e. T(n)=cn.

But to iterate through the entire list, as Ethyl shows, requires T(1) for the first item plus T(2) for the second item ... up to T(n) for the nth. The complete loop takes T(1)+T(2)+...+T(n), or c+2c+...+cn, which is (1+2+...+n)c

You'll probably remember from school that 1+2+...+n = (n^2+n)/2, which is why it would indeed be O(n^2)

If Ben is gonna get all algorithmic...

There is llListSort but no binary search and any binary search you would write would be hampered by llList2String being O(n), but you'd have fewer compares.

However, llListFindList is a single LSL call and as the LSL call overhead is high compared to LSL intrinsics, you may find that the commentary in llListFindList is more efficient than the samples above.

Using a linked list to implement an LSL list would be crazy!
IF they did that, THEN they are crazy AND traversing a list is indeed always and tragically n^2.

But I hope not. Experiments are needed.

(And yeah, as Introvert mentions, the apparent overhead of LSL in general seems to overwhelm the costs of particular calls. The highest I usually see for sim "Instructions Per Second" is around 20,000, in Alice. This is a number which can be safely characterized as "Not very many."

Cheers! Hooray for coding!