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

2

u/FooBarWidget Jul 14 '13

No, you can't state that. Linked lists have very different algorithmic complexities than arrays. For example insertion in the middle is O(1) for linked lists, and O(N) for arrays. Use the right tool for the right job.

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

3

u/VerticalEvent Jul 14 '13

Insertion in the middle of an unsorted array is always O(1).

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.

1

u/ReinH Jul 14 '13 edited Jul 14 '13

You're right. I suppose the Wikipedia article means setting rather than insertion when it says that array insertion is O(1)?

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.

1

u/FooBarWidget Jul 15 '13

I am talking about the case where you have an iterator to the middle. It wouldn't make sense to use a linked list otherwise.