Vector vs. LinkedList

[Hal Vaughan]

I've read up on Vectors and LinkedLists. Other than slightly different
interfaces, I'm not clear on reasons for using one over the other. Both
can keep growing and can have members inserted or removed as needed.

Is there a reason to use one over the other?

Thanks!

Hal

 

[Andrew Thompson]

I've read up on Vectors and LinkedLists.

What about ArrayList's?

.. Other than slightly different
interfaces, I'm not clear on reasons for using one over the other. Both
can keep growing and can have members inserted or removed as needed.

Is there a reason to use one over the other?

If limited to Java 1.1, use Vector (both the
others were introduced in 1.2).

Assuming the user has joined us in this
millennium, and is using Java 1.2+ then,
yes, go with AL/LL.

But I cannot recall the reason, though I thought
that AL's were generally preferred to LL's, and
it seems LL's have more methods that are
'beyond'/'not relevant to' work that can be
done by a plain old Vector.

Andrew T.

 

[Eric Sosman]

What about ArrayList's?


If limited to Java 1.1, use Vector (both the
others were introduced in 1.2).

Assuming the user has joined us in this
millennium, and is using Java 1.2+ then,
yes, go with AL/LL.

But I cannot recall the reason, though I thought
that AL's were generally preferred to LL's, and
it seems LL's have more methods that are
'beyond'/'not relevant to' work that can be
done by a plain old Vector.

ArrayList is better than LinkedList because it has faster
access by position. Want to find the tenth element, or the
hundredth, or the thousandth? ArrayList can do it in a jiffy,
while LinkedList must crawl through the first nine or ninety-nine
or nine hundred ninety-nine elements just to discover the one
you want. Yay, ArrayList! Boo, hiss, LinkedList!

LinkedList is better than ArrayList because it has faster
insertions and deletions at arbitrary locations. Want to use
a List as a queue? Either List can easily add new elements at
the end, but what happens when you pull the first element off
the beginning? LinkedList does it in a jiffy, while poor old
ArrayList huffs and puffs and has a hernia shuffling all the
rest of the elements around in its array. Yay, LinkedList!
Boo, hiss, ArrayList!

For my next trick, I'll explain why oranges are better
than apples, *and* vice versa.

 

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

If limited to Java 1.1, use Vector (both the
others were introduced in 1.2).

Assuming the user has joined us in this
millennium, and is using Java 1.2+ then,
yes, go with AL/LL.

But I cannot recall the reason, though I thought
that AL's were generally preferred to LL's, and
it seems LL's have more methods that are
'beyond'/'not relevant to' work that can be
done by a plain old Vector.

ArrayList and LinkedList will have some different performance
characteristics for operations due to their implementation.

It may not be relevant for original poster, but ...

Arne

 

[Andrew Thompson]

....
ArrayList is ...

(big snip)

Thanks. I was thinking something vaguely along
those lines, but it sounded a lot better coming from
someone that *knew* what they were talking about.

For my next trick, I'll explain why oranges are better
than apples,

...what about Bananas?

..*and* vice versa.

...Oh wait, of course. Bananas beat both apples
and oranges, "hand's" down - so not directly
relevant.

(ducks)

Andrew T.

 

[Mike Schilling]

I've read up on Vectors and LinkedLists. Other than slightly different
interfaces, I'm not clear on reasons for using one over the other. Both
can keep growing and can have members inserted or removed as needed.

Is there a reason to use one over the other?

Vectors are far more like ArrayLists than LinkedLists.

Use an ArayList (or a Vector) if you need fast random access. Use a Linked
List if you want fast inserts and removals throughout the list. If all you
want is to add members at the end and traverse from one end to the other
using an iterator, use whichever you like. But do *not* do

for (int i = 0; i < list.size(); i++)
{
Object o = list.get(i);
...
}

with a LinkedList. Each get(i) searches from either the beginning or the
end of the list.

 

[Adam Maass]

I've read up on Vectors and LinkedLists. Other than slightly different
interfaces, I'm not clear on reasons for using one over the other. Both
can keep growing and can have members inserted or removed as needed.

Is there a reason to use one over the other?

Short answer: yes.

Longer answer:

Vector, LinkedList, and ArrayList all implement the List interface. As such,
they all adhere to the contract of List: they contain objects in a
particular order, and offer methods to add objects to the list, remove
objects from the list, iterate over them (via an Iterator), and to access
objects by index in the list.

The differences come in the implementation.

Vector is basically a synchronized version of ArrayList. That is, all of the
methods on Vector have the "synchronized" keyword. That means that only one
thread at a time can access the internals of any given instance of Vector.
This is generally a Good Thing, but incurs the overhead of obtaining the
lock on the instance every time any method is called. If you have some other
guarantee that only one thread at a time can access any given Vector, then
this overhead is unnecessary, and you may as well use the (unsychronized)
ArrayList.

An ArrayList is implemented with a backing array. Inserts at the end are
fast (unless the backing array needs to be resized). Inserts in the middle
or at the front mean that all the other elements of the array need to be
copied to make room. Deletions mean that elements need to be copied down
from the end of the list. Iteration is fast; it means incrementing an index
into the array. Sorts are reasonably fast, as ArrayList supports O(1) random
access. Indexed access (via the "get(int)" method) is very fast.

A LinkedList is also unsynchronized. A LinkedList is implemented as a
doubly-linked chain of nodes. Inserts at the beginning or end are very fast.
Deletions from the middle are very fast (via the Iterator's "remove"
method), as a deletion only means moving two references. Iteration is fast;
it simply means walking the chain of nodes. Sorts are slow, as LinkedList
supports only O(n) random access. Indexed access (via the "get(int)" method)
is slow.

 

[Oliver Wong]

ArrayList is better than LinkedList because it has faster
access by position. Want to find the tenth element, or the
hundredth, or the thousandth? ArrayList can do it in a jiffy,
while LinkedList must crawl through the first nine or ninety-nine
or nine hundred ninety-nine elements just to discover the one
you want. Yay, ArrayList! Boo, hiss, LinkedList!

The LinkedList implementation provided by Sun will first check whether
it's faster to start from the beginning or start from the end of a linked
list. So if your LL has length 1000, and you ask for element 998, then the
implementation will only crawl through 1 element, and not 998 elements.

- Oliver

 

[Mike Schilling]

The LinkedList implementation provided by Sun will first check whether
it's faster to start from the beginning or start from the end of a linked
list. So if your LL has length 1000, and you ask for element 998, then the
implementation will only crawl through 1 element, and not 998 elements.

True, but if you ask for number 500...

 

[Greg R. Broderick]

I've read up on Vectors and LinkedLists. Other than slightly
different interfaces, I'm not clear on reasons for using one over
the other. Both can keep growing and can have members inserted or
removed as needed.

Is there a reason to use one over the other?

One complication that no one else has mentioned is that
java.util.vector is inherently synchronized, whereas
java.util.ArrayList and java.util.LinkedList are not. If you are
developing multithreaded code, then this should be a big
consideration.

For maximum code flexibility, I'd recommend that you declare your
variables / fields as the interface supertype "List" and use only
methods that are defined on the List interface. This will allow you
to easily and quickly switch implementations should performance
require this change.

Example:

List aList = new ArrayList();


Cheers!
GRB

 

[jupiter]

True, but if you ask for number 500...

Then it chokes like a Colts QB.

 

[Woebegone]

One complication that no one else has mentioned is that
java.util.vector is inherently synchronized, whereas
java.util.ArrayList and java.util.LinkedList are not. If you are
developing multithreaded code, then this should be a big
consideration.

For maximum code flexibility, I'd recommend that you declare your
variables / fields as the interface supertype "List" and use only
methods that are defined on the List interface. This will allow you
to easily and quickly switch implementations should performance
require this change.

Example:

List aList = new ArrayList();


Cheers!
GRB

So if you do require synchronization, use the appropriate interface,
then use java.util.Collections.synchronized/whatever/(yourlist), after
you've chosen the best implementation in context.

e.g
<http://java.sun.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)>

 

[Mike Schilling]

message

One complication that no one else has mentioned is that
java.util.vector is inherently synchronized, whereas
java.util.ArrayList and java.util.LinkedList are not. If you are
developing multithreaded code, then this should be a big
consideration.

As long as we're on the subject, I'll mention that per-method
synchronization goes only so far. It's still possible that

Vector v;
for (int i = 0; i < v.size(); i++)
{
Object o = v.get(i);
....
}

will throw an exception, say if another thread removes objects from the
vector between the call to size() and the call to get(). To guarantee
sensible behavior, it's necessary to synchronize the entire loop.

 

[Bent C Dalager]

Vector is basically a synchronized version of ArrayList. That is, all of the
methods on Vector have the "synchronized" keyword. That means that only one
thread at a time can access the internals of any given instance of Vector.
This is generally a Good Thing, but incurs the overhead of obtaining the
lock on the instance every time any method is called. If you have some other
guarantee that only one thread at a time can access any given Vector, then
this overhead is unnecessary, and you may as well use the (unsychronized)
ArrayList.

One important difference between Vector and a synchronized ArrayList
(obtained by calling Collections.synchronizedList) is that Vector is
deadlock-prone when equals() is called on it from different threads
whileas a synchronized ArrayList is not.

This is presumably because Vector's get() method is synchronized and
this is the one that is used by AbstractList's ListIterator - which is
used by equals(). A synchronized ArrayList, on the other hand, uses a
ListIterator that operates on the backing list (the unsynchronized
one) and so the calls that equals() makes to get() (through the
ListIterator) aren't synchronized in this case.

I would (and do) use ArrayList rather than Vector

Cheers
Bent D

 

[Lew]

As long as we're on the subject, I'll mention that per-method
synchronization goes only so far. It's still possible that

Vector v;
for (int i = 0; i < v.size(); i++)
{
Object o = v.get(i);
....
}

will throw an exception, say if another thread removes objects from the
vector between the call to size() and the call to get(). To guarantee
sensible behavior, it's necessary to synchronize the entire loop.

Or catch and handle the ConcurrentModificationException?

- Lew

 

[Eric Sosman]

Or catch and handle the ConcurrentModificationException?

Is there a likelihood of CME here? I don't see one -- but
of course we're only looking at a fragmentary sketch, and we
may have imagined different completions.

 

[Mike Schilling]

Or catch and handle the ConcurrentModificationException?

You won't see a CMF since you're not using an iterator. Each individual call
to size() and get() will work fine.

 

[Chris Uppal]

To guarantee

Or catch and handle the ConcurrentModificationException?

No, ConcurrentModificationException is not guaranteed to be thrown (it's
documented only to be thrown on a best-effort basis and merely to help expose
bugs).

Also, as I understand it, the set() and setElementAt() operations are not
considered to "modify" the list for the purposes of
ConcurrentModificationException.

-- chris

 

[Mike Schilling]

No, ConcurrentModificationException is not guaranteed to be thrown (it's
documented only to be thrown on a best-effort basis and merely to help
expose
bugs).

And it won't be thrown at all unless an iterator is used, which is why my
example didn't use one

 

[Chris Uppal]

And it won't be thrown at all unless an iterator is used, which is why my
example didn't use one

Bah! A trifling implementation detail...

-- chris