Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Vector vs. LinkedList

Reply
Thread Tools

Vector vs. LinkedList

 
 
Hal Vaughan
Guest
Posts: n/a
 
      01-18-2007
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
 
Reply With Quote
 
 
 
 
Andrew Thompson
Guest
Posts: n/a
 
      01-18-2007
Hal Vaughan wrote:
> 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.

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      01-18-2007
Andrew Thompson wrote:
> Hal Vaughan wrote:
>> 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.


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.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

 
Reply With Quote
 
=?ISO-8859-1?Q?Arne_Vajh=F8j?=
Guest
Posts: n/a
 
      01-18-2007
Andrew Thompson wrote:
> Hal Vaughan wrote:
>> I've read up on Vectors and LinkedLists.


>> 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.


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
 
Reply With Quote
 
Andrew Thompson
Guest
Posts: n/a
 
      01-18-2007
Eric Sosman wrote:
> Andrew Thompson wrote:
> > Hal Vaughan wrote:
> >> I've read up on Vectors and LinkedLists.

> >
> > What about ArrayList's?

....
> 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.

 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      01-18-2007

"Hal Vaughan" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed). ..
> 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.


 
Reply With Quote
 
Adam Maass
Guest
Posts: n/a
 
      01-18-2007

"Hal Vaughan" <(E-Mail Removed)> wrote:
> 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.



 
Reply With Quote
 
Oliver Wong
Guest
Posts: n/a
 
      01-18-2007
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> 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


 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      01-18-2007

"Oliver Wong" <(E-Mail Removed)> wrote in message
news:u%Mrh.8140$(E-Mail Removed)...
> "Eric Sosman" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>>
>> 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.
>


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


 
Reply With Quote
 
Greg R. Broderick
Guest
Posts: n/a
 
      01-18-2007
Hal Vaughan <(E-Mail Removed)> wrote in
news:(E-Mail Removed):

> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
compare LinkedList with ArrayList and Vector Amit Jain Java 8 10-03-2007 03:24 AM
const vector<A> vs vector<const A> vs const vector<const A> Javier C++ 2 09-04-2007 08:46 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
how the vector is created, how to pass vector to webservices method apachesoap:Vector Rushikesh Joshi Perl Misc 0 07-10-2004 01:04 PM



Advertisments