Like Kjellkod mentions, in theory the linked-list should deliver better performance than a vector whenever you need to insert or remove objects at or from positions not at the ends, however the reality is that in real, modern systems the hardware optimizes instruction/data reads by caching contiguous bytes of RAM in the CPU, and this optimization makes all the difference in the world when you have to insert or remove an item from the collection because you first have to seek the position you're interested in before performing the operation. Since arrays are contiguous blocks of memory by definition (and a vector is essentially an array with a cherry on top), then arrays will naturally perform better because cache misses are minimized, as opposed to a linked-list.
The Test
Naturally, I had to see this for myself, so I did a test in Java (as opposed to C++11 like Kjellrod). My testbed is a laptop running Windows 7 64-bit running on an i7-263QM @ 2GHz with 6GB of DDR3 1333Mhz DRAM. I have no idea about the timings of the RAM modules, but if it helps, my laptop is this one. The Java runtime I used is:
>> java -version
java version "1.6.0_29"
Java(TM) SE Runtime Environment (build 1.6.0_29-b11)
Java HotSpot(TM) Client VM (build 20.4-b02, mixed mode, sharing)
The JDK version I'm using is 1.6.0_29. Both are 32-bit. I implemented the same algorithm that Kjellkod did. The code is available here.
Following are my results (the axis at the bottom refers to the number of elements being sorted):
Just like Kjellkod, I found the performance of the linked-list vastly inferior to that of a vector. Notice, however, that my code actually ran faster despite the Java implementation. On a semantic level, does my code not mean the same as his? In other words, did I screw up somewhere?
[UPDATE 2012-03-19: My code did not run faster by any means... I mistakenly assumed that Kjellkod's times were in milliseconds as opposed to microseconds... until a few days ago, I wasn't even aware that measuring elapsed times of a few microseconds was possible on a typical consumer computer! Here's a really great link: https://blogs.oracle.com/dholmes/entry/inside_the_hotspot_vm_clocks.]
Notice that I threw in an ArrayList in there for comparison. Being an array deep down, its performance should be far better than the linked-list. It is. But how does it stack up against the Vector? This is where it gets interesting: if you google search around you will find that the general consensus is the Vector will be slower because it is synchronized whereas the ArrayList is not. Let's find out.
Using the same testbed:
Notice that slight overshoot (relative underperformance) of a couple of ms of the Vector in the ~200-700 range. I was able to reproduce that every time and can't yet figure out what could be the cause. After ~700 elements though, the vector is clearly faster than the arraylist by a few milliseconds, with the gap widening as we add more and more elements. Yet, that initial spike in the vector's time is unexpected; I predicted the ArrayList to be consistently slower than the Vector because of the additional overhead.
Conclusion
Overall, there seem to be only a few edge cases where a Linked-List makes sense (read the comments on Kjellrod's articles). Apart from those though, stay away from the linked-list despite everything the web tells you.
Between a Vector and an ArrayList though, there's pretty much no real reason to favor one over the other in terms of performance alone. Developing applications in Java typically means you're not interested in wringing out every single millisecond of performance out of your code and hardware, and also it's unusual to be working with lists of several thousand elements. Ranges from a dozen elements to a few hundred are typically the case and, as you can see above, the difference in performance is only 2 or 3 milliseconds at the most within that range.