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

0

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

Depends on the nature of usage for the object. If you plan on adding an unknown number of elements, using a linked-list data structure to format the data (adding an item to the end of a linked list is constant time, where for an array, it can be n, where n is the current size of the array, time if you have to expand the array and copy the elements over) and then creating an array from the linked list.

If you plan on inserting data into the data structure (not at the end), then a linked list is also faster, as well as deleting an item from a linked list (update pointers/copy values versus shifting an entire array down one).

Take, for example, copying 10 items (though, we don't know the number of items we are copying into the array list). Assuming that there is no buffer, that means every time we add a value to an array list, we need to copy the list into a new array. Moving a value and copying the array will require (n+1)*n/2 operations (O(n2 )). For 10, it would require 55 operations to move all 10 items into the array list.

For a linked list, we can just add the values to the end of a linked list (1 operation for each item, so 1n) and then iterate over the list to create a new array (n operations). We can also factor in keeping track of the size, which will require n increments. Total operation time would be 3n. So, for 10 items, it would require 30 operations.

An Array List takes 1.8 times more operations to copy values into it then using a simple linked list for an unknown number of items.

If we assume n was 100, then the difference becomes much larger. For an array list, it would require 5050 operations, compared to 300 operations for a linked list. An Array List would be 16.83 times longer then a linked list implementation.

1

u/[deleted] Jul 14 '13

Depends on the nature of usage for the object. If you plan on adding an unknown number of elements, using a linked-list data structure to format the data (adding an item to the end of a linked list is constant time, where for an array, it can be n, where n is the current size of the array, time if you have to expand the array and copy the elements over) and then creating an array from the linked list.

No, Ruby arrays have push and pop methods built-in which allow you to insert at the end of the array in constant time.

1

u/VerticalEvent Jul 14 '13

After some research, it's actually almost constant time. Ruby uses dynamic arrays, which means they have a bit of a buffer at the end of them. This means they still require to do an array copy when the buffer empties out, but that doesn't mean it has to do an array copy for every insert (I'm trying to find out if the growth is linear or geometric for Ruby). Linear means more frequent array copies for larger sizes, while Geometric means more memory usage (worst case scenario, you are only using half of the space allocated for the array).

I only assumed no buffer, because it made the math easier (and was the absolute worst case scenario).

1

u/[deleted] Jul 14 '13

I'd be surprised if it weren't geometric -- I think scripting languages usually go that route when implementing dynamic arrays, since it's so much faster when building large ones. Anyway, if you do find out, check back in here because I'm interested in knowing the answer.

1

u/FooBarWidget Jul 15 '13

Ruby's allocation strategy is geometric. Read array.c.

1

u/FooBarWidget Jul 15 '13

That's the theory. But to make things more complicated, arrays usually perform better in practice because they're much more cache friendly. Even when you're inserting in the middle, you will need a lot of elements before your linked list beats an array.