On ArrayLists and Vectors
Long ago, when I first started doing Java, I struggled against Java’s limitations regarding the resizing of arrays. Eventually after poking around for solutions, I found the
ArrayList. Before that, I found the
Vector, but for whatever reason, NetBeans was saying that
Vector was deprecated, so I settled on
ArrayList, and it was fine.
A few years later, I took my first class on C++, and learned about the
std::vector. I was also introduced to the concepts of the vector and the linked list. Needless to say, I was confused. If vectors and linked lists aren’t the same thing, then what is this
ArrayList thing? At the time, I elected not to pursue the question, needing to focus on figuring out these “pointer” things they were making us learn. I put it out of my mind.
Flash forward to today. This morning I was travelling the internet, and I came across a forum thread. The topic of the
ArrayList came up. Curiosity finally overcame me, and I looked into the issue.
So, About Those ArrayLists…
The Java Collections framework is broken up into various datatype interfaces. There is an interface for lists, queues, maps, sets, and deqeues.
You’ll notice that there is no vector interface. While a list and an array have different semantics and use cases, you can use them roughly in the same way. “Array indexing” can be implemented on a list by iterating to the nth node, and arrays can be traversed like a list. Since there’s nothing a list can do that a vector can’t and vice versa, it follows that they can both implement the same interface. Sun had to make a choice: name that interface “list” or “vector”. They went with list.
Given that Java’s vector type implements the list interface, it follows that they would reflect that in the name:
ArrayList. For all intents and purposes,
ArrayList is equivalent to C++’s
ArrayList implements the Collections framework’s list interface, but it is a growable array. It behaves like a vector, indexing is cheap, resizing is expensive. Java also provides a
LinkedList that behaves like a linked list.
So, what about Java’s
Vector? It seems that
Vector predates the Collections framework. After the introduction of the Collections framework
Vector was retrofitted to be a part of it, also implementing the list interface. So, what’s the difference between
Vector is synchronized, and therefore is safe to use in threaded code. Due to this it is significantly slower than
Simply put: use
ArrayList in single-threaded code, and
Vector in multi-threaded code.
Why Names Matter
This is why names matter. One might not think much of it, but imagine how many hiring managers would be out an interview question if
Vector had been named