Java List Implementations: ArrayList, LinkedList, Vector

Java has three main List implementations with different performance trade-offs. ArrayList is the default choice — it's backed by a resizable array, so getting an element by index is instant O of 1, like looking up a spot in an array. Adding to the end is usually O of 1, but occasionally O of n when the array fills up and needs to resize. The downside is inserting in the middle is O of n because you have to shift all the later elements over. LinkedList is a doubly-linked list where each element points to the next and previous. That makes adding or removing at either end O of 1, which is great for queues. The catch is if you want the element at index 100, you have to walk through 99 nodes first, so random access is O of n. LinkedList also implements the Deque interface, so you can use it as a queue or stack. Vector is basically the old synchronized version of ArrayList from Java 1.0 — every method is synchronized, which causes unnecessary lock overhead. We don't use Vector in modern code. If you need thread safety, you'd wrap ArrayList with Collections dot synchronizedList or use CopyOnWriteArrayList for read-heavy scenarios. One thing that surprises people is ArrayList usually beats LinkedList even for insertion-heavy workloads because of cache locality — array elements sit next to each other in memory, so the CPU loads them in chunks, but LinkedList nodes are scattered all over the heap causing cache misses. In practice, stick with ArrayList unless you specifically need that O of 1 queue behavior at both ends.