Results 1 to 7 of 7
Like Tree1Likes
  • 1 Post By Danieldcc

Thread: efficiency question

  1. #1
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default efficiency question

    When I run a method that counts amount of even numbers over 200,000 numbers on an arraylist and linkedlist, the array list completes in less than a second while the linked list takes almost half a minute. Can someone explain why the arraylist performs it so much more faster.

  2. #2
    eRaaaa is offline Senior Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    787
    Rep Power
    6

    Default Re: efficiency question

    Give us a whole example. The numbers are already in the list? You only read from the list? If, in which way?
    Do you understand the differents between arraylist and linkedlist implementations?

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,662
    Blog Entries
    7
    Rep Power
    21

    Default Re: efficiency question

    Finding element #n in an ArrayList takes one single operation while it takes n operations for a LinkedList (it's all in the API documentation).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: efficiency question

    Quote Originally Posted by JosAH View Post
    Finding element #n in an ArrayList takes one single operation while it takes n operations for a LinkedList (it's all in the API documentation).

    kind regards,

    Jos
    Could you explain this quickly please? I understand both of the ADTs but I don't get how the arraylist does it quicker

  5. #5
    Danieldcc is offline Member
    Join Date
    Sep 2010
    Posts
    83
    Rep Power
    0

    Default Re: efficiency question

    newbie here; I think an array can reference by a[i] so you directly go to that element that is required....with a linked list there is no referencing the i'th element so every time you do an operation it starts from the beginning of the linked list and traverses through the list until it finds the element that it needs, that's why takes much longer.............so if you have 100k elements, linked list has to go through each one to reach the element that you might want. that's what i assume
    sunde887 likes this.

  6. #6
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: efficiency question

    // count even numbers in a sequence of integers public static int countEven(List<Integer> seq) {
    int c = 0; for (int i = 0; i < seq.size(); i++) {
    if ( seq.get(i) % 2 == 0 ) { c++; }
    } return c;

    //fill up the array and linkelist seqArr is the arraylist and seqLL is the linkedlist.
    int n = Integer.parseInt(args[0]);
    for (int i = 0; i < 400000; i++) {
    int n = (int) (Math.random() * 100);
    seqArr.add(n);
    seqLL.add(n);

    Than I use the method countEven on both of them.

    Hopefully this clears it up. Why does the array come back with the answer quicker?

  7. #7
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: efficiency question

    According to the API documentation for LinkedList, it implements a doubly linked list. When you use indices to access entries, the implementation starts at the head or tail of the list, whichever is closer, and must traverse the list to get to the desired index. That traversal is what you are experiencing as an extended elapsed time to completion compared to the direct access that the ArrayList implementation affords you.

Similar Threads

  1. efficiency problem
    By marcosol in forum Advanced Java
    Replies: 3
    Last Post: 03-10-2012, 12:41 PM
  2. Efficiency of Searching
    By fam2315 in forum New To Java
    Replies: 12
    Last Post: 08-03-2011, 08:44 AM
  3. Cryptography Efficiency
    By joshdgreen in forum Advanced Java
    Replies: 22
    Last Post: 10-29-2010, 09:16 AM
  4. Replies: 7
    Last Post: 07-29-2010, 11:25 AM
  5. An Efficiency Question
    By Revenna in forum Java 2D
    Replies: 0
    Last Post: 06-25-2010, 07:22 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •