What data structure are Ruby arrays?

Question

I am learning about Arrays and Linked List in my computer science class. My professor says that Arrays cannot have elements added or removed from the end so instead we use linked list.

I know the implementation of Arrays in Python, Ruby, and JavaScript all allow me to modify an arrays length all I want. Do these languages really implement a linked list or some other data structure and call it an array?

What is going on under the hood? And if it is not a true array, why do they call it one?

You can look at the code for all those array implementations. You should also be wary of statements like "let you modify arrays length all you want"--just because you can make an array longer doesn't mean you're not incurring a memory copy when you do so. — Dave Newton
– Dave Newton, Commented Oct 7, 2014 at 15:50
In high-level languages like Ruby and Python there is really no use for linked lists, because there is no efficient way to implement them (at least not more efficient than the built-in array type). The array/linked list comparison your professor mostly applies to C. — Martijn
– Martijn, Commented Oct 7, 2014 at 18:12

tadman · Accepted Answer · 2014-10-07 15:52:07Z

8

Fixed-sized arrays cannot have elements added to the end if the array is full, but removing elements is fine. That's how a stack works.

Internally Ruby arrays are allocated as C-style arrays of a fixed size and are automatically resized as elements are added. As an optimization they are often re-sized a bit beyond what you need to avoid re-allocating on every single addition.

A linked-list is a different data structure that allows for more flexible insertion and removal, but is much slower to traverse and doesn't permit easy random access, things very important for an array structure.

answered Oct 7, 2014 at 15:52

tadman

212k23 gold badges237 silver badges266 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

chopper draw lion4 Over a year ago

Cool. I know JS and Python are also derivatives of C. Do they also use C style arrays?

tadman Over a year ago

They're not derivatives of C, but the standard Ruby, Python and JavaScript V8 core is written in C. It's just convention that they use C-style arrays internally, but each has a different approach as to how those are employed.

Mike A. · Accepted Answer · 2020-09-04 21:58:35Z

4

https://github.com/ruby/ruby/blob/master/array.c

Quick glance at the source for the Ruby Array implementation, it's a C array, just a block of memory. But as you can see in the code, it also provides functions to add and remove by updating this block of memory or reallocating if needed, giving you the convenience of modifying the Ruby array like it's dynamic.

edited Sep 4, 2020 at 21:58

Mike A.

3,23924 silver badges20 bronze badges

answered Oct 7, 2014 at 16:06

Chong Yu

4703 silver badges8 bronze badges

Collectives™ on Stack Overflow

What data structure are Ruby arrays?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related