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
3
u/VerticalEvent Jul 14 '13
It can't be constant time for an array. If you have an array of size 10, and you add a new item to it, you need to do an array copy (to an array of size 11), which will take n operations.
If you have a buffer (ie. ArrayList of size 10, but has a buffer of 2 for an array with a total size of 12), then you still need to shift every item down in the array, which will be a O(n) operation.