A data structure is a specific way to organize & access data.
Examples include:
Arrays
Binary trees
Hashes
Different data structures excel at different tasks.
For example, hashes are great if you’re looking to store data that looks like a dictionary (word & definition), or a phone book (person name & number).
Knowing what data structures are available, and the characteristics of each of them, will make you a better Ruby developer.
That’s what you’ll learn in this article!
Understanding Arrays
The array is the first data structure that you learn about when you start reading about programming.
Arrays use a contiguous chunk of memory where objects are stored one after another without gaps between them.
Unlike in lower-level programming languages, like C, Ruby does all the hard work of managing your memory, expanding the maximum array size & compacting it when you delete elements.
Uses:
As a base for more advanced data structures
To gather results from running a loop
Collecting items
You’ll find arrays everywhere, like the split & chars methods, which break down a string into an array of characters.
Example:
out = []
10.times { |i| out << i }
out
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
The following table shows you how the different array operations behave as the size of the array increases.
If you aren't familiar with time complexity notation read this article.
Time complexity for arrays:
Operation
Complexity
push
O(1)
pop
O(1)
access
O(1)
find
O(n)
delete
O(n)
Why is this helpful?
Because it tells you the performance characteristics of arrays.
If you're doing a lot of find operations on a HUGE array that's going to be slow...
But if you know what indexes to use, then an array is going to be fast because of the O(1) time complexity.
Choose your data structure with this criteria:
Performance characteristics => What are you doing with the data? How big is your dataset?
Shape & form of your data => What kind of data are you working with? Could you re-organize your data so it fits a better data structure?
The Hash Data Structure
Do you have a mapping between country codes & country names?
A hash is a data structure where every value has a key & this key can be anything, like a string, an integer, a symbol, etc.
How does it work?
A hash converts your key into a number (using the hash method in Ruby) & then uses that number as the index. But you don't need to understand that to be able to use hashes in your Ruby programs.
Uses:
Counting characters in a string
Mapping words to definitions, names to phone numbers, etc.
WRT array popping, it’s important to note that what Ruby calls pop() is removing the last element, so it’s essentially acting as a stack. Removing the first element, so that it would be treated as a queue, would be O(n), since it would have to shift all the other elements down by 1. (Unless it did something fancy under the hood like maintaining an offset, but the generic abstract data type array doesn’t do that.)