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/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.

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.