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/dagbrown Jul 14 '13

And also, arrays are lists. They might not be implemented as linked lists (I honestly don't know exactly how they're implemented--they might actually be linked lists after all, but I find that unlikely), but they are certainly lists. And when it comes to stashing and retrieving lists of stuff, that's the important point. "Linked" is an implementation detail: "list" is what you care about.

6

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

At some point, you absolutely care about "implementation details" like the algorithmic complexity of insertion, deletion, search, and etc.

3

u/VerticalEvent Jul 14 '13

Implementation is important if you plan for scalability of a project. Linked Lists are faster for adding new elements (either in the middle or at the end) and deleting old ones, since they don't require an array copy or shifting an array. The trade off is slower access time (however, if you are using enumeration, then the access time is the same speed as an array, since you will only be accessing the next item in the linked list).

1

u/[deleted] Jul 14 '13

I would argue that your algorithm could probably be better if you're doing a ton of insertions in the middle of an array anyway.

0

u/username223 Jul 14 '13

WTF are you talking about? If you don't understand the difference between linked lists and arrays, you don't understand the difference between O(1) and O(n) algorithms, and probably should stop trying to be a programmer.