Why Would You Need a Linked List in Ruby?

I am learning more about linked lists, and one question that kept coming up for me is, what would you use a linked list for in Ruby or Rails programming?

This resource says that you use linked lists to avoid problems and complexity with memory allocation in C.

Basically, to create an array in C, you have to allocate memory, and you have to have some idea of how big the array will be if you want to do that. If the array gets much bigger than the original size, you will have to reallocate memory for the new elements.

Using a linked list is much simpler, because each element or node only needs memory for its content, and a pointer to the next node. Each time you add to the list, you are only adding memory for a new node. And you can add any datatype, of any size, at any node (although I’m not sure this is an issue for Ruby arrays).

But Ruby does all this for us, right?

This excellent article on sitepoint explains that yes, Ruby does this for us, and it does a pretty good job. But you still might want to use a linked list in special cases.  Allocating new memory to add more elements to an array still takes time. So if you have an array with thousands of elements, you might want to look at using a linked list for optimization if you will be adding to it.

But in most cases, it’s fine to add elements to an array, and Ruby will only resize the array if needed.  (It is faster, for larger arrays, to use push or pop instead of shift or unshift.)

Linked lists are also useful immutable data structures for functional programming, if you’re into that sort of thing.

And finally, searching an array and searching a linked list are both O(n) (aka linear) complexity.  You have to search through every element to find a specific element.  If you need a faster lookup time, you’ll need a hash table.