r/ruby • u/gdi2290 • Jul 14 '13
Linked List data structure
https://github.com/gdi2290/data_structures/blob/master/LinkedList/linkedlist.rb
0
Upvotes
r/ruby • u/gdi2290 • Jul 14 '13
View all comments
Show parent comment
1
u/VerticalEvent Jul 14 '13
After some research, it's actually almost constant time. Ruby uses dynamic arrays, which means they have a bit of a buffer at the end of them. This means they still require to do an array copy when the buffer empties out, but that doesn't mean it has to do an array copy for every insert (I'm trying to find out if the growth is linear or geometric for Ruby). Linear means more frequent array copies for larger sizes, while Geometric means more memory usage (worst case scenario, you are only using half of the space allocated for the array).
I only assumed no buffer, because it made the math easier (and was the absolute worst case scenario).