To get the best suggestions on alternative data structures you should say a little more about wha your program does and thus needs. However if all you're interested in is adding to the back and removing from the front, that is a queue, you can implement one using two lists without mutating the lists. One list represents the front and you can cdr down it efficiently, the other list represents the back in reverse and you cons elements onto it to add elements to the back of the queue. Whenever the front list becomes empty you reverse the back list to form the new front and the back becomes empty. This way you get a queue with O(1) amortized enqueue and dequeue operations.
That's an interesting approach, thanks for suggesting it, Marijn. I just wonder about the penalty of the reversal part and how it figures in?... I guess that it could be more or less neglectable provided there are few queues in which there are typically more adds than removals. However, in the application I'm working on (it's actually an emulation of an operating system using queues to manage task schedulers, event managers, interrupts and so on) there is no prediction whatsoever about the runtime behavior of the queues - there'll be nested queues, large queues, small queues, frequently accessed vs. mostly idle queues, queues more heavily removing than adding items and vice versa and so on. So in some of the queues there may be hefty swapping of queue fragments and efficiency may again become an issue. Another thing is that again quite some heavy burden is left on the garbage collector in this architecture which I'd like to avoid.
I'll implement both techniques (as Matthias pointed out, a good interface definition allows for easy replacement) and see if I can run some meaningful comparison tests.
____________________ Racket Users list: http://lists.racket-lang.org/users
