The Collections Framework in the Java 2 library is great. The API couldn't
be any easier to use and it's easy to change implementations without having to
do a lot of work retrofitting your code. I think that it fits most general
programming needs.
However, there are a lot of problems with it too. For starters, there is no
good built in implementation of a Stack. Yes, there is java.util.Stack ,
but that class extends java.util.Vector .
This makes it easy to "forget" that you should use only push(Object o)
and pop() by allowing you to use the methods in Vector like
add(Object o, int index) and other non-Stack operations. This fact is
pointed out in the book Effective Java and the author underscores that
this was a bad design (inheritance violates encapsulation; composition preserves
it).
The Collections Framework tries to do the right thing by providing 3
interfaces ( java.util.Set ,
java.util.List ,
and java.util.Map ).
These interfaces have various implementations contained in the same package
( java.util.TreeSet ,
java.util.HashMap ,
java.util.LinkedList ,
etc.). All of these classes implement their named interfaces which is good and
they all provide adequate functionality for most needs.
What is a real pain in the neck is that these containers (I say containers to
mean all of those in the Collections Framework) are not synchronized
out-of-the-box. It reduces overhead in high stress environments, but that does
not assuage the inherent need for it. To make things a little better, there is a
utility class called java.util.Collections
that allows you to return a synchronized view of a container, but you can only
access the container via the methods in the interface that said container
implements.
What is the point of my rant? Since java.util.Stack
does not meet my needs, I decided to re-implement a Stack using a java.util.LinkedList
as the backing store. I chose java.util.LinkedList
because it had methods that were best suited to do the job and it is reasonably
fast for inserting and removing objects from the list. The problem was that the
methods that I really need to implement the Stack in a straightforward way are
not part of the java.util.List
interface. I thought it would be okay and I took the hit. I successfully did
that (any programmer worth their salt should be able to) and then moved on to a
queue then a deque. It was during my testing of my queue that I got into a
synchronization pitfall.
Let's suppose that I have one of my Queues managing several objects and let's
say that I start two different Threads to manage objects entering and leaving
the queue. Without synchronizing the object, I would most certainly have a
corrupt data structure. So, I have to resort to manual synchronization. What's
worse is that I have to obtain the lock on the data structure. Suddenly, my
dream of a simple data structure with an easy to use API are gone.
I suppose I'll get over it. I may have to tweak those structures some, but I
want to keep the usability of those structures at a very simple level. I can
hide a lot of the synchronization issues under the API, but what does that do to
my performance?