(Ruby arrays, at least in MRI, are basically STL vectors).
1000 inserts to the middle of a 1,000,000 element Ruby array happens so quickly you can barely perceive the delay. The same insert pattern to a basic Ruby linked list sets my machine on fire.
EDIT: Updated to remove the term 'toy-apps'
Even on fairly large graphs --- say, graphs at the scale of basic blocks in a program, but (obviously) not on the scale of "recommendation graph at Amazon" --- you shouldn't be burning huge numbers of cycles seeking through reference links. In naive reference-link implementations, Ruby sorely increases the constant factors for graph analysis, but computing a minimum cost spanning tree isn't going to kill you (especially because the intermediate data structures you'd use to do it would be native-code Arrays and Hashes). On the other hand, linked lists more or less pessimize Ruby, forcing it to do nothing but expensive interpreter looping, pointer chasing, and object management.
Having said all that, for serious work, I'd keep my data structures outboard, probably in Redis.
Other people would probably answer "just write a graph library in C; for instance, you could write a C wrapper around void-star-specialized boost::graph", then bridge it to Ruby with FFI.
Ruby is as good at C for I/O bound problem subsets. This is a lot of problems, and so having a language as pleasant to write in as Ruby is a win (you could say the same for Node.js and maybe even Python). It is obviously not the only language you'll ever need, though.
They're so utterly irrelevant in 99% of startups today, where knowing how to lay out your classes and methods for maintainability is so much more important than any trivial and pointless performance gain.
The complexity of solutions is at such a higher level now than it's ever been and yet we're still worrying about structures that shaves less than a ms off something that's called once every 10 seconds.
The reason why ruby and python have grown in dominance in the last few years is because you don't actually have to worry about this any more.
With that said, a lot of startups (and web apps in general) are effectively consumer CRUD apps w/ nice images and transitions. Perf generally isn't important until scale becomes an issue (and until then you're main perf bottlenekck is some DB and/or network code that someone who cared about perf wrote).
So I agree. It makes sense to use effectively a domain specific language/framework like RoR when you're in that domain. And linked lists may not be applicable. But I'd still be weary of hiring people for whom reasoning about them is off-limits.
For example if I give you an element of an array/linked list and tell you to insert a new element adjacent to it -- a linked list is a constant time insertion, whereas arrays are typically O(n).