Vector vs. LinkedList

Discussion in 'Java' started by Hal Vaughan, Jan 18, 2007.

  1. Hal Vaughan

    Hal Vaughan Guest

    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
     
    Hal Vaughan, Jan 18, 2007
    #1
    1. Advertising

  2. 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.
     
    Andrew Thompson, Jan 18, 2007
    #2
    1. Advertising

  3. Hal Vaughan

    Eric Sosman Guest

    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
    lid
     
    Eric Sosman, Jan 18, 2007
    #3
  4. 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
     
    =?ISO-8859-1?Q?Arne_Vajh=F8j?=, Jan 18, 2007
    #4
  5. 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.
     
    Andrew Thompson, Jan 18, 2007
    #5
  6. "Hal Vaughan" <> wrote in message
    news:...
    > 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.
     
    Mike Schilling, Jan 18, 2007
    #6
  7. Hal Vaughan

    Adam Maass Guest

    "Hal Vaughan" <> 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.
     
    Adam Maass, Jan 18, 2007
    #7
  8. Hal Vaughan

    Oliver Wong Guest

    "Eric Sosman" <> wrote in message
    news:...
    >
    > 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
     
    Oliver Wong, Jan 18, 2007
    #8
  9. "Oliver Wong" <> wrote in message
    news:u%Mrh.8140$...
    > "Eric Sosman" <> wrote in message
    > news:...
    >>
    >> 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...
     
    Mike Schilling, Jan 18, 2007
    #9
  10. Hal Vaughan <> wrote in
    news::

    > 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
     
    Greg R. Broderick, Jan 18, 2007
    #10
  11. Hal Vaughan

    jupiter Guest

    "Mike Schilling" <> wrote in message
    news:DMNrh.62439$...
    >
    > "Oliver Wong" <> wrote in message
    > news:u%Mrh.8140$...
    >> "Eric Sosman" <> wrote in message
    >> news:...
    >>>
    >>> 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...

    Then it chokes like a Colts QB.
     
    jupiter, Jan 19, 2007
    #11
  12. Hal Vaughan

    Woebegone Guest

    Greg R. Broderick wrote:
    > Hal Vaughan <> wrote in
    > news::
    >
    >> 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


    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)>
     
    Woebegone, Jan 19, 2007
    #12
  13. "Greg R. Broderick" <> wrote in
    message
    news:...
    > Hal Vaughan <> wrote in
    > news::
    >
    >> 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.


    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.
     
    Mike Schilling, Jan 19, 2007
    #13
  14. In article <>,
    Adam Maass <> wrote:
    >
    >
    >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
    --
    Bent Dalager - - http://www.pvv.org/~bcd
    powered by emacs
     
    Bent C Dalager, Jan 19, 2007
    #14
  15. Hal Vaughan

    Lew Guest

    Mike Schilling wrote:
    > 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
     
    Lew, Jan 19, 2007
    #15
  16. Hal Vaughan

    Eric Sosman Guest

    Lew wrote:
    > Mike Schilling wrote:
    >> 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?


    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.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Jan 19, 2007
    #16
  17. "Lew" <> wrote in message
    news:...
    > Mike Schilling wrote:
    >> 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?


    You won't see a CMF since you're not using an iterator. Each individual call
    to size() and get() will work fine.
     
    Mike Schilling, Jan 19, 2007
    #17
  18. Hal Vaughan

    Chris Uppal Guest

    Lew wrote:

    > To guarantee
    > > sensible behavior, it's necessary to synchronize the entire loop.

    >
    > 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
     
    Chris Uppal, Jan 19, 2007
    #18
  19. "Chris Uppal" <-THIS.org> wrote in message
    news:45b0f0e2$0$757$...
    > Lew wrote:
    >
    >> To guarantee
    >> > sensible behavior, it's necessary to synchronize the entire loop.

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


    And it won't be thrown at all unless an iterator is used, which is why my
    example didn't use one :)
     
    Mike Schilling, Jan 19, 2007
    #19
  20. Hal Vaughan

    Chris Uppal Guest

    Mike Schilling wrote:

    > > 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 :)


    Bah! A trifling implementation detail...

    -- chris
     
    Chris Uppal, Jan 19, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    23,833
  2. Replies:
    8
    Views:
    1,932
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    571
    James Kanze
    Sep 4, 2007
  4. Amit Jain
    Replies:
    8
    Views:
    1,176
    Mike Schilling
    Oct 3, 2007
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    366
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page