LinkedList vs ArrayList

Discussion in 'Java' started by Thomas Hawtin, Apr 11, 2006.

  1. Vanessa Berni wrote:
    > I'ev a big problem. I've a program that handles with a orded set of object.
    > With this objects I've to
    >
    > a)execute a LOT of random access
    > b) insert/remove from head and tail (not so frequently as the number of
    > operation (a) )
    >
    > Do I have to use an ArrayList o LinkedList?


    Suck it and see.

    You should find a long LinkedList is absolutely terrible for random access.

    Unfortunately ArrayList isn't cyclic, removing from the head will cost.
    It probably wont cost as much as a random access on a long LinkedList.
    Removing from the head of an array list, just involves a block move of
    pointers. Making your way through a linked list involves accessing large
    amounts of memory (whether randomly or sequentially will likely depend
    upon GC algorithm).

    If you do lots of inserts/removes on heads and tails separately, perhaps
    you could get away with reversing the list from time to time or
    inserting/removing a block at a time.

    For small lists, you may find different results apply.

    You might be able to find a CyclicArrayList implementation somewhere (or
    write your own if it is important). Java 1.6 will have Deque and in
    particular ArrayDeque, unfortunately neither support random access.

    Tom Hawtin
    --
    Unemployed English Java programmer
    http://jroller.com/page/tackline/
     
    Thomas Hawtin, Apr 11, 2006
    #1
    1. Advertising

  2. Hi all,
    I'ev a big problem. I've a program that handles with a orded set of object.
    With this objects I've to

    a)execute a LOT of random access
    b) insert/remove from head and tail (not so frequently as the number of
    operation (a) )

    Do I have to use an ArrayList o LinkedList?

    Grazie mille
    Vanessa
     
    Vanessa Berni, Apr 11, 2006
    #2
    1. Advertising

  3. Thomas Hawtin

    Ben Guest

    Vanessa Berni wrote:
    > Hi all,
    > I'ev a big problem. I've a program that handles with a orded set of object.
    > With this objects I've to
    >
    > a)execute a LOT of random access
    > b) insert/remove from head and tail (not so frequently as the number of
    > operation (a) )
    >
    > Do I have to use an ArrayList o LinkedList?
    >
    > Grazie mille
    > Vanessa
    >
    >


    For a lot of random access, it's actually better to use the
    java.util.TreeSet especially since you specified an ordered set.

    LinkedList are better when you don't have an order or a set.
    and ArrayList when you are more worried about the adding execution time.

    Ben
     
    Ben, Apr 11, 2006
    #3
  4. Hi,
    thank you for your help.
    How do I get the i-th element from a treeset (the equivalent of
    ArrayList.get(i))??

    Thank you
    Vanessa

    "Ben" <> ha scritto nel messaggio
    news:e1ggmi$dcg$...
    > Vanessa Berni wrote:
    >> Hi all,
    >> I'ev a big problem. I've a program that handles with a orded set of
    >> object.
    >> With this objects I've to
    >>
    >> a)execute a LOT of random access
    >> b) insert/remove from head and tail (not so frequently as the number of
    >> operation (a) )
    >>
    >> Do I have to use an ArrayList o LinkedList?
    >>
    >> Grazie mille
    >> Vanessa
    >>
    >>

    >
    > For a lot of random access, it's actually better to use the
    > java.util.TreeSet especially since you specified an ordered set.
    >
    > LinkedList are better when you don't have an order or a set.
    > and ArrayList when you are more worried about the adding execution time.
    >
    > Ben
     
    Vanessa Berni, Apr 11, 2006
    #4
  5. Vanessa Berni wrote:
    > Hi all,
    > I'ev a big problem. I've a program that handles with a orded set of object.
    > With this objects I've to
    >
    > a)execute a LOT of random access
    > b) insert/remove from head and tail (not so frequently as the number of
    > operation (a) )
    >
    > Do I have to use an ArrayList o LinkedList?
    >
    > Grazie mille
    > Vanessa
    >
    >


    When you do your random access, how do you select the element? By value,
    or by index?

    Patricia
     
    Patricia Shanahan, Apr 11, 2006
    #5
  6. Thomas Hawtin

    Fahd Shariff Guest

    Fahd Shariff, Apr 11, 2006
    #6
  7. Sometimes by vakue and sometime by index.


    "Patricia Shanahan" <> ha scritto nel messaggio
    news:SQP_f.1407$...
    > Vanessa Berni wrote:
    >> Hi all,
    >> I'ev a big problem. I've a program that handles with a orded set of
    >> object.
    >> With this objects I've to
    >>
    >> a)execute a LOT of random access
    >> b) insert/remove from head and tail (not so frequently as the number of
    >> operation (a) )
    >>
    >> Do I have to use an ArrayList o LinkedList?
    >>
    >> Grazie mille
    >> Vanessa
    >>
    >>

    >
    > When you do your random access, how do you select the element? By value,
    > or by index?
    >
    > Patricia
     
    Vanessa Berni, Apr 11, 2006
    #7
  8. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Vanessa Berni schreef:
    > Hi,
    > thank you for your help.
    > How do I get the i-th element from a treeset (the equivalent of
    > ArrayList.get(i))??


    You can’t, but there is of course an iterator, and if that doesn’t
    suffice, there is tailset(element).first().

    But did you mean by ordered that you elements are ordered, or that they
    induce an ordering? Only in the latter case is a TreeMap interesting.

    If you do only adding and deleting at the end, then ArrayList is
    perfect, if you need insertion and deletion at the front, you could
    consider re-implementing ArrayList with a start and end pointer, instead
    of only the end pointer, as it is now.

    LinkedList is only interesting if you want to insert elements in the middle.

    H.
    - --
    Hendrik Maryns

    ==================
    www.lieverleven.be
    http://aouw.org
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2 (GNU/Linux)

    iD8DBQFEO8p5e+7xMGD3itQRAgjvAJ0X9jlFvFGPyu40+jmBYTG8AXvcDQCfdNx6
    pClxCmp6EoTWhRXFoqoNvSY=
    =1Y1t
    -----END PGP SIGNATURE-----
     
    Hendrik Maryns, Apr 11, 2006
    #8
  9. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Ben schreef:
    > Vanessa Berni wrote:
    >> Hi all,
    >> I'ev a big problem. I've a program that handles with a orded set of
    >> object.
    >> With this objects I've to
    >>
    >> a)execute a LOT of random access
    >> b) insert/remove from head and tail (not so frequently as the number
    >> of operation (a) )
    >>
    >> Do I have to use an ArrayList o LinkedList?
    >>
    >> Grazie mille
    >> Vanessa
    >>
    >>

    >
    > For a lot of random access, it's actually better to use the
    > java.util.TreeSet especially since you specified an ordered set.
    >
    > LinkedList are better when you don't have an order or a set.
    > and ArrayList when you are more worried about the adding execution time.


    You did mean the inverse, right?
    H.
    - --
    Hendrik Maryns

    ==================
    www.lieverleven.be
    http://aouw.org
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2 (GNU/Linux)

    iD8DBQFEO8qfe+7xMGD3itQRAhhSAKCCXz1Xj1gAZ3979PwpgBP2X/J5RwCdG5bS
    GADhdO7f9C6pV46Si2j7cCU=
    =HKnQ
    -----END PGP SIGNATURE-----
     
    Hendrik Maryns, Apr 11, 2006
    #9
  10. In this way It will cost me O(i) every time ....

    "Fahd Shariff" <> ha scritto nel messaggio
    news:...
    > If you really want to "get the i-th element" use an iterator and call
    > its next() method i times.
    >
    > --
    > Fahd Shariff
    > http://www.fahdshariff.cjb.net
    >
     
    Vanessa Berni, Apr 11, 2006
    #10
  11. Vanessa Berni wrote:
    > Sometimes by vakue and sometime by index.
    >
    >
    > "Patricia Shanahan" <> ha scritto nel messaggio
    > news:SQP_f.1407$...
    >
    >>Vanessa Berni wrote:
    >>
    >>>Hi all,
    >>>I'ev a big problem. I've a program that handles with a orded set of
    >>>object.
    >>>With this objects I've to
    >>>
    >>>a)execute a LOT of random access
    >>>b) insert/remove from head and tail (not so frequently as the number of
    >>>operation (a) )
    >>>
    >>>Do I have to use an ArrayList o LinkedList?
    >>>
    >>>Grazie mille
    >>>Vanessa
    >>>
    >>>

    >>
    >>When you do your random access, how do you select the element? By value,
    >>or by index?
    >>
    >>Patricia


    Depending on details of what you are doing, consider alternatives such
    as one or more HashMap instances. It depends partly on a tradeoff
    between time, code complexity, and space.

    You could get the equivalent of your access by index with a HashMap that
    maps Integer to your objects. Keep track of the index of the lowest and
    highest index elements. To insert or delete at head or tail, both do the
    put or remove, and also adjust the lowest or highest index value.

    To access by value fast, keep the reverse map, object to Integer. You
    can do O(1) access by value, and keep the first map consistent only
    accessing it by Integer key.

    Essentially, turn EVERYTHING into key-based access to a HashMap, and it
    is all O(1).

    Patricia
     
    Patricia Shanahan, Apr 11, 2006
    #11
  12. Thomas Hawtin

    Ben Guest

    Vanessa Berni wrote:
    > Hi,
    > thank you for your help.
    > How do I get the i-th element from a treeset (the equivalent of
    > ArrayList.get(i))??
    >
    > Thank you
    > Vanessa
    >


    in a TreeSet you don't have a method like the .get(i) of the arrayList.
    Instead the TreeSet provides you with an iterator that will allow you to
    step through and find the object that you want. Look at the Java API for
    more specific information :

    http://java.sun.com/j2se/1.3/docs/api/java/util/TreeSet.html

    Ben
     
    Ben, Apr 11, 2006
    #12
  13. > If you do only adding and deleting at the end, then ArrayList is
    > perfect, if you need insertion and deletion at the front, you could
    > consider re-implementing ArrayList with a start and end pointer, instead
    > of only the end pointer, as it is now.


    The problem of removing from the front of the ArrayList is that the array
    will be "resized and re-indexed" and so it costs O(n)? Isn't it?

    If I had a pointer at the start won't it be resized?

    Vanessa
     
    Vanessa Berni, Apr 11, 2006
    #13
  14. Vanessa Berni wrote:
    >
    > The problem of removing from the front of the ArrayList is that the array
    > will be "resized and re-indexed" and so it costs O(n)? Isn't it?


    O(n) but by a tiny factor. It's just a System.arraycopy.

    LinkedList.get is also an O(n) operation, but probably with a slightly
    larger factor.

    Tom Hawtin
    --
    Unemployed English Java programmer
    http://jroller.com/page/tackline/
     
    Thomas Hawtin, Apr 11, 2006
    #14
  15. Hendrik Maryns wrote:

    > LinkedList is only interesting if you want to insert elements in the middle.


    Actually I found out in another project that it's also faster if you do
    a lot of iterating. Probably because of the array bounds checks in
    ArrayList.

    Kind regards

    robert
     
    Robert Klemme, Apr 11, 2006
    #15
  16. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Vanessa Berni schreef:
    >> If you do only adding and deleting at the end, then ArrayList is
    >> perfect, if you need insertion and deletion at the front, you could
    >> consider re-implementing ArrayList with a start and end pointer, instead
    >> of only the end pointer, as it is now.

    >
    > The problem of removing from the front of the ArrayList is that the array
    > will be "resized and re-indexed" and so it costs O(n)? Isn't it?


    Indeed.

    > If I had a pointer at the start won't it be resized?


    I wrote /re/-implement. Have a look at the source code of ArrayList.
    Then instead of only the size int, which is in fact a pointer to the end
    of the list, have a start and end pointer, which indicate which part of
    the array is used. Of course you’ll have to consider how to add an
    element in the middle...

    This is basically the CyclicArrayList Tom Hawtin writes about.

    You could also keep two ArrayLists, one for the last half in normal
    order, one for the first half in reversed order. Then insertion and
    deletion at the beginning is cheap, but you have to deal with the case
    your front list gets empty and such.

    H.
    - --
    Hendrik Maryns

    ==================
    www.lieverleven.be
    http://aouw.org
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2 (GNU/Linux)

    iD8DBQFEO9KNe+7xMGD3itQRAj0uAJ9xt5mnYZGENCwrIEZpjhRxNvLJ+wCfajnk
    pWOsjY1OVmduCHFXUkcb7dw=
    =Yzz2
    -----END PGP SIGNATURE-----
     
    Hendrik Maryns, Apr 11, 2006
    #16
  17. Vanessa Berni sez:
    > In this way It will cost me O(i) every time ....


    So will LinkedList.get( i ), the $15 question is how long it
    will take on a real CPU with a real list. OTGH, there's only
    one way to resize an array: create a new larger (or smaller)
    one and copy elements. Every resize of an ArrayList requires
    2x the memory -- dep. on the size of your list, this may be
    a bigger concern than time.

    If you know the number of elements in advance, you can avoid
    resizing (delete by setting element to null) and have O(1)
    indexed access with an array(List). Other options include a
    map with orig. index as a key (requires extra memory for
    Integer keys) for storage, or a list for storage and a map
    for index.

    Dima
    --
    Q276304 - Error Message: Your Password Must Be at Least 18770 Characters
    and Cannot Repeat Any of Your Previous 30689 Passwords -- RISKS 21.37
     
    Dimitri Maziuk, Apr 11, 2006
    #17
  18. "Vanessa Berni" <> wrote in message
    news:AmP_f.78608$...
    > Hi all,
    > I'ev a big problem. I've a program that handles with a orded set of
    > object.
    > With this objects I've to
    >
    > a)execute a LOT of random access
    > b) insert/remove from head and tail (not so frequently as the number of
    > operation (a) )
    >
    > Do I have to use an ArrayList o LinkedList?


    What you want is a random access List-like structure that has both negative
    and positive indices, and where both start and end index can chance.
    Operations at the head increment and decrement the start index, operations
    at the tail increment and decrement the end index. This can easily be built
    using two ArrayLists, one for the negative indices and one for the
    non-negative. You'll need to keep track of the current start and end
    indices. You'll also need to keep track of the current actual sizes of the
    ArrayLists, so that you know whether an insert at the head (or tail) is a
    set() or an add().
     
    Mike Schilling, Apr 11, 2006
    #18
  19. I've been thinking about all the operation I have to do with my set andf
    I've found out that

    1) I've to read all the elements (in order) : I can do it with a
    listiterator
    2) Given the current element (pointed by the listIterator) (i-th element) I
    have to find the previous element (that is NOT necessarly (i-1))
    3) Given the current element (pointed by the listIterator) (i-th element) I
    have to find the next element (that is NOT necessarly (i+1))
    4) I've to do some operation with the 3 elements (modify the current
    element)
    5) I've to move "up" or "down" the current element

    I think that, in this case, the best solution would be a LinkedList.
    I'm not able to execute operations 2) and 3).

    I'd like to create 2 new listIterator "cloning" the one I have that points
    to the current element.
    With the first I will execute operation 2 and with the other operation 3.

    //pseudo code
    ListIterator curr=myset.listIterator();
    while(curr.hasNext()){
    //get element
    MyObject obj=(MyObject)curr.next();

    //create listIterator
    ListIterator findPrec=curr;
    ListIterator findNext=curr;

    //find previous element moving findPrec
    !!!! if I move findPrec I'll move also findNext and curr

    //find previous element moving findNext
    !!!! if I move findNext I'll move also findPrec and curr
    }

    Is there a way to do what I want to?

    Thanks
    Vanessa


    "Vanessa Berni" <> ha scritto nel messaggio
    news:AmP_f.78608$...
    > Hi all,
    > I'ev a big problem. I've a program that handles with a orded set of
    > object.
    > With this objects I've to
    >
    > a)execute a LOT of random access
    > b) insert/remove from head and tail (not so frequently as the number of
    > operation (a) )
    >
    > Do I have to use an ArrayList o LinkedList?
    >
    > Grazie mille
    > Vanessa
    >
    >
     
    Vanessa Berni, Apr 12, 2006
    #19
  20. Vanessa Berni wrote:
    >
    > I'd like to create 2 new listIterator "cloning" the one I have that points
    > to the current element.


    If you use the iterators to modify the list, then you'll get into
    trouble with ConcurrentModificationException.

    Possibly there is a better data structure, but it depend upon the
    details of what you are trying to do. Or possibly if you suck it and
    see, ArrayList will turn out to be fast enough. There's not much point
    in optimising something that performs sufficiently well.

    Tom Hawtin
    --
    Unemployed English Java programmer
    http://jroller.com/page/tackline/
     
    Thomas Hawtin, Apr 12, 2006
    #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. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,772
    Natty Gur
    Aug 19, 2003
  2. Kaidi
    Replies:
    4
    Views:
    2,432
    Kaidi
    Jan 3, 2004
  3. xz
    Replies:
    16
    Views:
    2,413
  4. Amit Jain
    Replies:
    8
    Views:
    1,183
    Mike Schilling
    Oct 3, 2007
  5. Philipp
    Replies:
    6
    Views:
    941
    Arne Vajhøj
    May 28, 2008
Loading...

Share This Page