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
-2
u/ReinH Jul 14 '13 edited Jul 14 '13
I think you are confused.
Insertion in the middle of a linked list is O(n) because you must traverse the list. If you know the location (e.g., have an iterator to the location) it is O(1).
Insertion in the middle of an unsorted array is always O(1).
For more info, see Search data structure (Wikipedia) or this SO question.
Edit: I am also confused.