Which class from the Java runtime environment you should use when you need a stack.
The package java.util
contains a few classes suitable for pushing, poping, and
peeking in stack style.
push | pop | peek | |
---|---|---|---|
Stack | s.push(e) |
s.pop() |
s.peek() |
ArrayList | s.add(e) |
s.remove(s.size()-1) |
s.get(s.size()-1) |
LinkedList | s.addFirst(e) |
s.removeFirst() |
s.peekFirst() |
ArrayDeque | s.addFirst(e) |
s.removeFirst() |
s.peekFirst() |
All but ArrayDeque
implement
the widely used and known interface List
.
Let's see how efficient are the implementations in JRE6, in relative units.
time | space | |
---|---|---|
Stack | x2.09 | x1.6 |
ArrayList | x1.15 | x1.3 |
LinkedList | x1.27 | x3.02 |
ArrayDeque | 1 | 1 |
Yep, ArrayDeque
is best
both in terms of time and speed. If you need a subtype of
List
then go with
ArrayList
. If you want
to eat memory like crazy for no good reason then try
LinkedList
. And if you
have a thing for names like Vector
(which Stack
extends) then,
well, go for it. Just don't say I told you to use it.
Finally, if you are a speed junkie and you know in advance the
maximum possible size of the stack, then you can implement
your own for a x1.2 speed-up (compared to ArrayDeque
).
Just for the record, a basic stack operation for ArrayDeque
takes about 15ns on my
old laptop.
Good bye, and stay tuned for the next useless microbenchmark results.
4 comments:
If "having a thing for names" the same thing as needing something to be synchronized, then I have a "thing for names" when I am writing concurrent applications. Also, ArrayDeque is only available in Java6.
I often find that I want to synchronize at a higher level than the individual data structure, so whether its synchronized or not isn't very important. This is a interesting result assuming you need a really big and frequently used stack. If you're only using it moderately you can't beat the clarity of calling a Stack a Stack.
@Andrew: The size of the stack doesn't really matter. If you use it a lot or not matters, of course.
@Jim: Like Andrew, I also prefer higher level synchronization usually.
There are other differences between the classes above, but I wanted to focus only on raw performance, because otherwise I would have went on for a few pages :p. Thanks for sharing what you see as being important.
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.