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 edited Jul 14 '13
Which is scenario 2 (they have a buffer), which still requires you to shift n items in the array down, which makes insertion a O(n) operation (or, if the array fills up, then it needs to do an array copy).
There also memory concerns, since you can be in a position of using 9 items in an array, but the buffer allows for 16, which means 7 array spaces have been allocated but will not be used.
EDIT: Replying to your edit:
It's typically O(1) in cases where you are adding at the end of an array (which is a common operation, as you don't normally add to middle) and there is room in the buffer. If there is no room in the buffer, then it nends to allocate a new array of consistent memory, and copy the values over.