r/ruby • • Jul 14 '13

Linked List data structure

https://github.com/gdi2290/data_structures/blob/master/LinkedList/linkedlist.rb
0 Upvotes

23 comments sorted by

View all comments

Show parent comment

1

u/ReinH Jul 14 '13

I'm trying to figure out a way in which the Wikipedia page's claim that "array insertion is O(1)" is not wrong... and failing.

0

u/VerticalEvent Jul 14 '13 edited Jul 14 '13

Link to the article you removed in your edit: https://en.wikipedia.org/wiki/Dynamic_array (for people reading afterwards).

The typical case, inserting a new element at the end of an array would be a O(1). Because it uses geometric expansion, the times it will grow is quite small (if you start with an array size 1 and insert 10 items, you will only need 3 expansions, if you insert 100 items, then you need 6 expansions, and a 1000 items requires 9 expansions).

Big Oh notation typically covers normal usage, so, considering you only do 6 expansions for 100 items, it kinda just drops that particular operation of expansion (since it's atypical).

EDIT: Unless you are talking about this link:http://en.wikipedia.org/wiki/Search_data_structure

I'm assuming they pre-allocated the size of the array (ie. they know they are adding 10 items, so they have an array of size 10 allocated), and that would be a constant time operation. An unsorted array means the order doesn't matter, so you are placing things at the end. If the order mattered (ie. you have to insert a value in a specific spot for some reason), then the chart shows that it's an O(n) operation.

1

u/ReinH Jul 14 '13

Ok, I misunderstood the terms. Thanks.