[Unicon-group] Slow Insertion in List

[Majorinc, Kazimir]

Dear colleagues,

Icon (and Unicon) advantages over lists implemented through pointers, i.e. 
direct access using integers as indexes seems to have a price: some tests I 
did recently suggest that linear time is required for the insertion (and 
perhaps deletition) of elements with known index from list (using built in 
functions or list concatenation). Am I right about that?

Is there a convenient way around, or a new data structure that allows 
direct access (with enumerable i.e. integer indexes) in const or log time 
and fast (const or log time) insertion is required? (Using tables it 
appears one can have both integer indexes and insertion in a linear time, 
but not both in the same time) I guess that some kind of a balanced tree 
(perhaps table with some extensions) can do that. Did anyone implemented 
such a data structure or operations already?

Furthermore, what is the worst case running time of other list operation? 
One could expect that (if n=*L)

     put, get, push and pull require O(1) time
     L[i]   requires O(log n) time
     every L[1 to n] requires O(n log n) time
     every !L  requires  O(n) time
     sort and sortf require O(n log n) time
Is some of the mentioned operations significantly slower?

Thanks,

----
Kazimir Majorinc, Zagreb, Croatia