compare LinkedList with ArrayList and Vector

Discussion in 'Java' started by Amit Jain, Oct 2, 2007.

  1. Amit Jain

    Amit Jain Guest

    What are the performance issue with LinkedList in compare of ArrayList
    and Vector?

    Position-based access has constaint-time performane for the ArrayList
    and Vector classes. However, position-based access is in linear time
    for a LinkedList.
    Amit Jain, Oct 2, 2007
    #1
    1. Advertising

  2. Amit Jain wrote:
    > What are the performance issue with LinkedList in compare of ArrayList
    > and Vector?
    >
    > Position-based access has constaint-time performane for the ArrayList
    > and Vector classes. However, position-based access is in linear time
    > for a LinkedList.


    So you answered your own question ? Or ?

    Arne
    =?ISO-8859-1?Q?Arne_Vajh=F8j?=, Oct 2, 2007
    #2
    1. Advertising

  3. "Amit Jain" <> wrote in message
    news:...
    > What are the performance issue with LinkedList in compare of ArrayList
    > and Vector?
    >
    > Position-based access has constaint-time performane for the ArrayList
    > and Vector classes. However, position-based access is in linear time
    > for a LinkedList.


    That's one. Now, suppose you're iterating through a List and decide to
    remove the current entry (or insert a new entry before the current one.)
    The cost is linear for the ArrayList but fixed for the LinkedList.
    Mike Schilling, Oct 2, 2007
    #3
  4. Amit Jain

    Amit Jain Guest

    > That's one. Now, suppose you're iterating through a List and decide to
    > remove the current entry (or insert a new entry before the current one.)
    > The cost is linear for the ArrayList but fixed for the LinkedList.


    Can you please more describe the work Linear in your answer "The cost
    is linear..." .

    Thanks
    Amit Jain
    Amit Jain, Oct 2, 2007
    #4
  5. Amit Jain

    Daniel Pitts Guest

    On Oct 2, 12:21 pm, Amit Jain <> wrote:
    > What are the performance issue with LinkedList in compare of ArrayList
    > and Vector?
    >
    > Position-based access has constaint-time performane for the ArrayList
    > and Vector classes. However, position-based access is in linear time
    > for a LinkedList.


    Vector is obsolete and should not be used.

    LinkedList has constant time addition/removal from both ends of the
    list. Also, if you have an iterator into a specific location in the
    list, insertion/removal at that location is constant time. For
    ArrayList (and Vector), inserting/removing from the list (other than
    the end) results in an array copy of all elements after the insert/
    remove position.

    In most common situations, I use:
    List<SomeType> myList = new ArrayList<SomeType>();
    If that turns out to be to slow because I'm using a lot of middle
    inserts/removals, then I can switch it with LinkedList<SomeTime>().
    Daniel Pitts, Oct 2, 2007
    #5
  6. "Amit Jain" <> wrote in message
    news:...
    >> That's one. Now, suppose you're iterating through a List and decide to
    >> remove the current entry (or insert a new entry before the current one.)
    >> The cost is linear for the ArrayList but fixed for the LinkedList.

    >
    > Can you please more describe the work Linear in your answer "The cost
    > is linear..." .


    I was copying your use of the word. Anyway, I meant proportonal to the size
    of the array.
    Mike Schilling, Oct 2, 2007
    #6
  7. Amit Jain

    Lew Guest

    Mike Schilling wrote (and thus should be attributed):
    >> That's one. Now, suppose you're iterating through a List and decide to
    >> remove the current entry (or insert a new entry before the current one.)
    >> The cost is linear for the ArrayList but fixed for the LinkedList.


    Amit Jain wrote:
    > Can you please more describe the work Linear [sic] in your answer "The cost
    > is linear..." .


    Polynomial of order 1.

    For example, the function "f(x) = mx + k" is linear in x because it scales as
    the first power of x.

    "f(x) = ax^2 + bx + c" is quadratic, i.e., it scales as the second power of x.

    <http://en.wikipedia.org/wiki/Linear_equation>
    <http://en.wikipedia.org/wiki/Quadratic>

    The context for these terms here is /asymptotic analysis/, the analysis of a
    problem for its limiting characteristics. The limit of growth rate with the
    size of the input is a major analytical datum.

    <http://en.wikipedia.org/wiki/Big_O_notation>

    For an x-fold increase in problem size (e.g., the length of a List), the time
    (or other metric of effort) to solve the problem will increase by some
    function of x, f(x). If f(x) doesn't change with the problem size, it's of
    order 0. If it increases in direct proportion to x, it's linear. If it
    increases proportionate to the square of x, it's quadratic, and so on.

    There is a lot of study time in your near future. GIYF.

    --
    Lew
    Lew, Oct 2, 2007
    #7
  8. Amit Jain

    Roedy Green Guest

    >What are the performance issue with LinkedList in compare of ArrayList
    >and Vector?


    Look at the implementation. One is good at indexing to find an
    element, the other is good at inserting and deleting and element.
    --
    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Oct 3, 2007
    #8
  9. "Roedy Green" <> wrote in message
    news:...
    > >What are the performance issue with LinkedList in compare of ArrayList
    >>and Vector?

    >
    > Look at the implementation. One is good at indexing to find an
    > element, the other is good at inserting and deleting and element.


    And both are crap at doing lookups, which is why Maps exist..
    Mike Schilling, Oct 3, 2007
    #9
    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. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,726
    Natty Gur
    Aug 19, 2003
  2. Kaidi
    Replies:
    4
    Views:
    2,328
    Kaidi
    Jan 3, 2004
  3. Thomas Hawtin

    LinkedList vs ArrayList

    Thomas Hawtin, Apr 11, 2006, in forum: Java
    Replies:
    22
    Views:
    7,088
    Robert Klemme
    Apr 12, 2006
  4. Hal Vaughan

    Vector vs. LinkedList

    Hal Vaughan, Jan 18, 2007, in forum: Java
    Replies:
    22
    Views:
    6,104
    Hal Vaughan
    Jan 22, 2007
  5. Replies:
    8
    Views:
    1,887
    Csaba
    Feb 18, 2006
Loading...

Share This Page