List implementation in ruby?

Question

I'm a bit struggling with the understanding of the Array class in Ruby. I have seen on Google that an Array class is actually more of a list, but I can't seem to find how it actually works.

I am really concerned with performance issues as I have to deal with large sorted lists, and I don't want to step over the whole array to add a single element to it.

So I was wondering if there were any real and clear implementation of a list (as in caml for instance), and I am also looking for a good documentation about how Array's method are implemented, regarding optimization matters.

Thanks!

Solution

A Ruby array offers a full list interface:

• push/<< for adding element at the end
• each provides an iterator for list traversal
• sort lets you sort the items with an optional block for a custom comparator
• ...

So there's no apparent need to have a special List class or Module - take Java for example, we end up using ArrayList if we need a List all the time because it gives us good performance and the additional benefit of accessing elements by their index. So Ruby (similar to other languages such as Python, PHP or Lua) tries to keep things simple with regards to collection types by offering just three types - Array, Hash and Set - therefore with a rich interface that makes it easy to emulate other collection types such as a List, Queue or Deque etc.

If you'd like to know details about the implementation, I would recommend simply downloading the Ruby sources and investigating the corresponding files (for MRI it's array.c in the top-level directory) .