aspose file tools*
The moose likes Java in General and the fly likes ArrayList vs LinkedList? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "ArrayList vs LinkedList?" Watch "ArrayList vs LinkedList?" New topic
Author

ArrayList vs LinkedList?

raj pandey
Greenhorn

Joined: Jan 13, 2012
Posts: 7
Dear All..
i am using collection...
and i have a little bit doubt on Linkedlist and Arraylist...in the case of frequent insertion
That which one gives more performance in frequent insertion..?
Thanks in advance !!!
Ronak Chauhan
Greenhorn

Joined: Jan 13, 2012
Posts: 6
array list is fast in access but for insertion and deletion linked list is really beneficial..so you should go with linked list
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

This topic has been moved to Java in General -- as the Jobs Discussion forum seems really out of place for it.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

raj pandey wrote:Dear All..
and i have a little bit doubt on Linkedlist and Arraylist...in the case of frequent insertion
That which one gives more performance in frequent insertion..?


It depends.

If you're always inserting at the end (such as with a simple add() call), it won't matter much. ArrayList might be a tiny bit faster due to not having to create a "node" object, but if you don't properly size the list ahead of time, that slight advantage will probably be erased when we have to grow the list. You probably won't notice any difference either way though.

If you're inserting in the beginning or middle of the list, LinkedList will be faster, since all it has to do is move a couple of links around, while ArrayList has to keep re-copying the elements further down the array.

For the most common use cases, you won't see any difference.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Ronak Chauhan wrote:array list is fast in access


For random access, yes. But for hitting the beginning or end of the list, or for iterating, they are the same.

but for insertion and deletion linked list is really beneficial..so you should go with linked list


Not exactly true. See my previous post.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7807
    
  21

raj pandey wrote:That which one gives more performance in frequent insertion..?

As Ronak said: LinkedList; however, I doubt that that's where your research ends.

For example, LinkedList's performance for retrieving specific elements (or sorting) is awful, whereas ArrayList's is pretty much the same as an array. What you need is a structure that satisfies all your needs, or gives you the best combination of performance; and that requires answers to more than just a single question.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
raj pandey wrote:That which one gives more performance in frequent insertion..?

As Ronak said: LinkedList;


And yet... Not.

With -Xms1G -Xmx1G and 10M elements, the following code gives:
ArrayList: 280
LinkedList: 338
ArrayList: 207
LinkedList: 342

With -Xms1G -Xmx1G and 20M elements, it gives:
ArrayList: 800
LinkedList: 3,735
ArrayList: 107
LinkedList: 3,839

So, in the end, for the general case, it doesn't really matter. Both have O(1) performance for simple add()s.

  • If you need random access, ArrayList has the advantage.
  • If you need to add/remove other than at the end, LinkedList has the advantage.
  • If you need both, you'll have to evaluate your specific use cases and test to determine which is best for you.
  • If you don't need either, then it shouldn't matter which one you pick, and only if you observe a bottleneck and measure the list insertion to be the problem should you worry about picking one or the other for performance.


  • Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7807
        
      21

    Jeff Verdegan wrote:
  • If you need to add/remove other than at the end, LinkedList has the advantage.

  • Quite right. I was assuming an insert, not an add; and for small sets LinkedList's theoretical performance advantage is likely to be outweighed by all that darn linking.

    @raj: which just goes to prove that the only correct answer is the one you find yourself by testing.

    Winston
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    Winston Gutkowski wrote:@raj: which just goes to prove that the only correct answer is the one you find yourself by testing.


    But, and this is important, you have to be testing a case that you actually care about. You much test the same size lists, the same number of elements in the list, the same type of access, etc. And you should repeat the test to overcome any JIT optimization costs in the early runs.


    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Pat Farrell wrote:
    Winston Gutkowski wrote:@raj: which just goes to prove that the only correct answer is the one you find yourself by testing.


    But, and this is important, you have to be testing a case that you actually care about. You much test the same size lists, the same number of elements in the list, the same type of access, etc. And you should repeat the test to overcome any JIT optimization costs in the early runs.




    AND the test should be representative of how you'll actually be using it, or you need to explicitly take into account the way in which it is not.

    For example, in this case, you might say, "Well, LL is many times slower than AL for the size of list I'll be dealing with, BUT that's just for adding and doing nothing else. I know that I'll be reading each element from a file/DB/network, so that I/O will dwarf the 2 second difference over 20M records."

    (One of my pet peeves is when people say, "Use A because it's 10x faster than B", totally ignoring the fact that a 10x performance improvement in 1% of your code is meaningless, and totally ignoring that there are factors other than "efficiency" that matter.)

    </rant>
    Arun Giridharan
    Ranch Hand

    Joined: Sep 30, 2010
    Posts: 290

    raj pandey wrote:Dear All..
    i am using collection...
    and i have a little bit doubt on Linkedlist and Arraylist...in the case of frequent insertion
    That which one gives more performance in frequent insertion..?
    Thanks in advance !!!


    i prefer LinkedList since it is O(1) for insertion , as insertion increase the array size get resized(new array) and increase so result would be O(n) for larger number of elements.
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    Arun Giridharan wrote:i prefer LinkedList since it is O(1) for insertion , as insertion increase the array size get resized(new array) and increase so result would be O(n) for larger number of elements.

    It is true that its O(1) but big-oh notation does not care about what the constants are and its only meaningful as N becomes very large. Millions or Billions.

    For many algorithms, including LinkedList, when N is small say under 100, the constants are far more important than the big-OH value.

    Using a LinkedList for a small number of values when you are using it as an array is simply wrong. Its not better in any sense. It probably is slower, and for sure code is less obvious to someone reading it.
    Arun Giridharan
    Ranch Hand

    Joined: Sep 30, 2010
    Posts: 290

    Pat Farrell wrote:
    Using a LinkedList for a small number of values when you are using it as an array is simply wrong.

    Why do i want to do so ?? , i though the question was about insertion about huge number of items.

    Pat Farrell wrote:
    Its not better in any sense. It probably is slower, and for sure code is less obvious to someone reading it.

    yes
    Saral Saxena
    Ranch Hand

    Joined: Apr 22, 2011
    Posts: 202

    Jeff Verdegan wrote:
    Winston Gutkowski wrote:
    raj pandey wrote:That which one gives more performance in frequent insertion..?

    As Ronak said: LinkedList;


    And yet... Not.

    With -Xms1G -Xmx1G and 10M elements, the following code gives:
    ArrayList: 280
    LinkedList: 338
    ArrayList: 207
    LinkedList: 342

    With -Xms1G -Xmx1G and 20M elements, it gives:
    ArrayList: 800
    LinkedList: 3,735
    ArrayList: 107
    LinkedList: 3,839

    So, in the end, for the general case, it doesn't really matter. Both have O(1) performance for simple add()s.

  • If you need random access, ArrayList has the advantage.
  • If you need to add/remove other than at the end, LinkedList has the advantage.
  • If you need both, you'll have to evaluate your specific use cases and test to determine which is best for you.
  • If you don't need either, then it shouldn't matter which one you pick, and only if you observe a bottleneck and measure the list insertion to be the problem should you worry about picking one or the other for performance.




  • Hi ,

    I have executed your program could you please tell me in detail what -Xms1G -Xmx1G represents..?
    As i have entered this in vm arguements section of eclipse and i was surprised to see that after entering this as vm arguments it shows that linked list taking less time as without entering these in vm arguements, it had bring down the value at least much less...my readings on executing the above program after entering these as vm arguments are

    ArrayList: 234
    LinkedList: 265
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Arun Giridharan wrote:
    raj pandey wrote:Dear All..
    i am using collection...
    and i have a little bit doubt on Linkedlist and Arraylist...in the case of frequent insertion
    That which one gives more performance in frequent insertion..?
    Thanks in advance !!!


    i prefer LinkedList since it is O(1) for insertion


    So is ArrayList, for insertion at the end, which is by far the most common use case. Non-end insertion/deletion and random access are the two less common use cases that can tip the scales definitively one way or the other.

    , as insertion increase the array size get resized(new array) and increase so result would be O(n) for larger number of elements.


    No, it's still O(1). Also, see the results of my tests, above. Also, if you know the necessary size ahead of time, or at least an upper bound, then ArrayList will be faster and consume less space than LinkedList--and it stil might even if you don't.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Saral Saxena wrote:
    I have executed your program could you please tell me in detail what -Xms1G -Xmx1G represents..?


    The minimum and maximum heap the JVM is allowed to use. Setting the maximum value high means I'll have enough memory for what I'm doing. Setting the minimum to the same value might mean that it reserves all the memory at startup so that my timing tests won't be skewed by the JVM having to ask the OS for more memory. However, seeing the disparity between LL and AL for 20M elements makes me wonder if I might be mistaken about that.


    As i have entered this in vm arguements section of eclipse and i was surprised to see that after entering this as vm arguments it shows that linked list taking less time as without entering these in vm arguements


    That's what I would expect. See my above explanation. Perhaps the reason it didn't work for me is that I'm on a 64-bit OS and hardware. Or maybe it's just a different version of the JVM with a different approach to memory management.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Pat Farrell wrote:
    Using a LinkedList for a small number of values when you are using it as an array is simply wrong. Its not better in any sense. It probably is slower, and for sure code is less obvious to someone reading it.


    Why less obvious? Is it because ArrayList is the de facto default, and people might tend to assume that if you're using LinkedList there must be a specific reason? Or am I missing something?
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    We write code for two audiences. The first, and least important, is for the compiler so the code will do what we want. The second, and over the long term more important, is for the human reader who will stumble across the code years from now and have to "maintain" it. When a smart maintainer sees LinkedList, he expects that its used as a linked list, with lots of insertions between elements, removals of elements, etc. If you use it as a simple array, it makes understanding the code more difficult and take longer. No programmer, initial developer, or maintainer has excess time.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Pat Farrell wrote:We write code for two audiences. The first, and least important, is for the compiler so the code will do what we want. The second, and over the long term more important, is for the human reader who will stumble across the code years from now and have to "maintain" it.


    Yes. Well aware of that, thanks. Just wondering what your reasoning was.

    When a smart maintainer sees LinkedList, he expects that its used as a linked list, with lots of insertions between elements, removals of elements, etc


    So your answer to my question is, "Yes, because ArrayList is the de facto default, so if we see LinkedList, we assume it was used for a specific reason." Thanks. Just wanted that clarification on your reasoning.

    I'll point out, though, that ArrayList has its own special strength--namely, random access. It just so happens that it's the de facto default, probably for historical reasons--namely that it's the replacement for Vector, which was the only list implementation before 1.2, and which is backed by an array probably because that's a built-in list-like structure.

    It could just as easily have ended up the other way around, where we might be saying, "If we see ArrayList instead of LinkedList, we would assume it's because the author expects random access to be important." The fact is, for the vast majority of cases, either one fits the bill quite well. Neither is "a level above" the other in any general sense.

    . If you use it as a simple array, it makes understanding the code more difficult and take longer.


    Well, yes, in general, if you use a class in a way that's contrary to its intended purpose, it makes it harder to maintain. The same goes if you use ArrayList when LinkedList would have been better. And in most cases, we don't use a List--either LL or AL--as a "simple array." We use it as a simple List. If we want a simple array, we should use an array, not AL and not LL.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7807
        
      21

    Jeff Verdegan wrote:If we want a simple array, we should use an array, not AL and not LL.

    Particularly if it's being used for primitives. For objects, I'm not so sure; especially after discovering Josh Bloch's ArrayAsList wrapper in EJ.

    I just can't think of an occasion when I would prefer a T[] to a List<T>

    Winston
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    Jeff Verdegan wrote:Well, yes, in general, if you use a class in a way that's contrary to its intended purpose, it makes it harder to maintain. The same goes if you use ArrayList when LinkedList would have been better.


    +1 exactly.
    Martin Vajsar
    Sheriff

    Joined: Aug 22, 2010
    Posts: 3610
        
      60

    As somebody wrote about millions of records in a LinkedList, I'd mention another consideration: LinkedList has bigger memory overhead than ArrayList. For every item in a linked list a new object is allocated, which contains references to the previous and next item (the list is doubly-linked) and of course a reference to the item held. An ArrayList contains only the reference to the item (which is part of an internal array), therefore if the capacity is set more or less at the size of the list, it will take less that third of the memory a LinkedList would take. It might be insignificant if the items in the list are large, but when storing millions of small objects (say, Integers), the linked list's memory requirements might become an issue in itself. Generally, the memory will run out sooner than if you let the ArrayList to grow as needed from its default initial capacity, which might be a little bit surprising.
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3014
        
      10
    Note that with LinkedList, there can be a big difference between inserting and deleting from the list directly, and inserting and deleting through the list's iterator. If you are inserting or deleting in the middle of the list (or more generally, anywhere a long way away from either end) then insertion and deletion on the list aren't as fast as you might hope. To access element i and insert or delete at that postion, you need to find element i first - and if you're using random access, those can still be O(n) operations, unless you're at one of the ends. On the other hand, if you insert or delete while iterating, and using the iterator, then the iterator remembers where you are in the list, and it's an O(1) operation. Of course it's still O(n) to iterate through the list - but at least you're not multiplying that factor by an additional O(n) for each operation along the way.
    Seetharaman Venkatasamy
    Ranch Hand

    Joined: Jan 28, 2008
    Posts: 5575

    so far I have worked 5 to 6 projects.. I have not seen LinkedList in that project. I do blame the kind of project ;)
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3014
        
      10
    Winston Gutkowski wrote:I just can't think of an occasion when I would prefer a T[] to a List<T>

    Well, prior to generics in JDK 1.5, arrays were perhaps the best way to communicate and enforce that a list/array/whatever should contain elements of a particular type. Even today, generics are subject to erasure while arrays are not, so there's a slight argument for preferring them for that reason. That's not a strong enough reason to actually prefer them, I think. But it's something.
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    Premature optimization is the root of all evil.
    --Donald Knuth
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Pat Farrell wrote:Premature optimization is the root of all evil.
    --Donald Knuth


    Is that aimed at a particular individual or post? The key messages throughout this thread have been:

    1) For the most common use case, either one will probably work equally well. (i.e., don't optimize prematurely)

    2) To determine the performance for a particular case, you need to measure. (Don't prematurely optimize, but do get the relevant information when optimization is needed.)

    3) AL and LL each have their strengths for certain use cases. (Optimize when appropriate.)

    Additionally that recent post about LL insertion/removal when you're already there with the iterator vs. having to find the spot at which to insert/remove is about appropriate optimization, not premature.

    Sorry if I seem prickly. Just not sure what you're trying to add to the discussion here.
    Pat Farrell
    Rancher

    Joined: Aug 11, 2007
    Posts: 4658
        
        5

    Jeff Verdegan wrote:
    3) AL and LL each have their strengths for certain use cases. (Optimize when appropriate.)
    ...
    Sorry if I seem prickly. Just not sure what you're trying to add to the discussion here.


    Nearly all worry about performance of ArrayList vs LinkedList is premature. It is rare that the application performance is driven by the choice of list. Nearly of the real world applications that I've worked on in the past 40 years have their performance controlled by the DBMS or some other external thing.

    Sure, the wrong choice can have impact. But when you measure things, and you are only doing a million inserts, its likely that the performance difference are not important to the overall application performance. If the million things are big, you probably should not be storing them all in memory anyway.

    I've been on the ranch here for only a few years, but I can not remember a single case, either here in General or over in Performance, where it was actually a case of "optimizing when appropriate"

    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Pat Farrell wrote:
    Jeff Verdegan wrote:
    3) AL and LL each have their strengths for certain use cases. (Optimize when appropriate.)
    ...
    Sorry if I seem prickly. Just not sure what you're trying to add to the discussion here.


    Nearly all worry about performance of ArrayList vs LinkedList is premature.


    As I pointed out way back in the beginning: For the general use case of adding at the end and iterating, it is indeed. But if you know you're going to do a lot of random access or adding/removing in the beginning or middle, then choosing one or the other for performance reasons is certainly not premature.

    It is rare that the application performance is driven by the choice of list. Nearly of the real world applications that I've worked on in the past 40 years have their performance controlled by the DBMS or some other external thing.


    True. But a meaningful portion of the app could take a negative hit if you choose wrong for the above criteria.


    I've been on the ranch here for only a few years, but I can not remember a single case, either here in General or over in Performance, where it was actually a case of "optimizing when appropriate"


    I think I've already made clear where the comments in this thread were talking about appropriate optimization.
    Arun Giridharan
    Ranch Hand

    Joined: Sep 30, 2010
    Posts: 290

    Jeff Verdegan wrote:

    , as insertion increase the array size get resized(new array) and increase so result would be O(n) for larger number of elements.


    No, it's still O(1).


    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Arun Giridharan wrote:
    Jeff Verdegan wrote:

    , as insertion increase the array size get resized(new array) and increase so result would be O(n) for larger number of elements.


    No, it's still O(1).




    Why do you think it would be otherwise? True, we have to copy N elements every time we grow, but that happens less and less frequently as the list grows, so adding N elements still approaches O(N) overall, or O(1) per element.
    Martin Vajsar
    Sheriff

    Joined: Aug 22, 2010
    Posts: 3610
        
      60

    Mike Simmons wrote:Even today, generics are subject to erasure while arrays are not, so there's a slight argument for preferring them for that reason. That's not a strong enough reason to actually prefer them, I think. But it's something.

    Actually, since 1.5 there is the Collections.checkedList() for that.
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3014
        
      10
    Yes, but after erasure, that's a runtime check - while arrays continue to give compile-time checking. As I said, it's a slight reason.
    Martin Vajsar
    Sheriff

    Joined: Aug 22, 2010
    Posts: 3610
        
      60

    Mike Simmons wrote:Yes, but after erasure, that's a runtime check - while arrays continue to give compile-time checking. As I said, it's a slight reason.

    Not at all.

    Firstly, arrays do provide runtime check; the following code compiles (no warnings!) and throws ArrayStoreException:


    Secondly, generics provide better compile time checks, the following code compiles with warnings (and you need to resort to raw types to have it compile at all, which should light up all sorts of red lights around such code):

    And though it does not fail in runtime, you can add runtime checks if you want to. By default, the check overhead is not incurred.

    To sum it up, lists beat arrays on every front nowadays.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7807
        
      21

    Jeff Verdegan wrote:True, we have to copy N elements every time we grow...

    Actually, we copy N element references, which is probably a lot less. But you knew that .

    Winston
    Paul Clapham
    Bartender

    Joined: Oct 14, 2005
    Posts: 18570
        
        8

    Jeff Verdegan wrote:True, we have to copy N elements every time we grow, but that happens less and less frequently as the list grows, so adding N elements still approaches O(N) overall, or O(1) per element.


    Assuming that every time the ArrayList's internal array overflows it copies it to a new array which is twice as large, then a little bit of mathematics shows that no matter how many entries there are in the list, on the average each of them has been copied some number of times which is no more than 2. Or to put it another way, the total number of entry-copying events is no more than 2N, where N is the number of entries.

    I don't remember whether "twice as large" is actually what happens in current ArrayList implementations, but a similar calculation applies no matter what the factor is for increasing the size of the internal array.

    So yes, what you say there is correct.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Paul Clapham wrote:
    Jeff Verdegan wrote:True, we have to copy N elements every time we grow, but that happens less and less frequently as the list grows, so adding N elements still approaches O(N) overall, or O(1) per element.


    Assuming that every time the ArrayList's internal array overflows it copies it to a new array which is twice as large, then a little bit of mathematics shows that no matter how many entries there are in the list, on the average each of them has been copied some number of times which is no more than 2. Or to put it another way, the total number of entry-copying events is no more than 2N, where N is the number of entries.

    I don't remember whether "twice as large" is actually what happens in current ArrayList implementations, but a similar calculation applies no matter what the factor is for increasing the size of the internal array.

    So yes, what you say there is correct.


    Thanks for the verification, with actual valid, meaningful math and everything.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38865
        
      23
    If you have any idea how many references you wish to keep in your List, you can use the ensureCapacity(int) method to speed things up. You will find that method in ArrayList and Vector, but not in LinkedList because it is unnecessary there.
    Paul Clapham
    Bartender

    Joined: Oct 14, 2005
    Posts: 18570
        
        8

    Jeff Verdegan wrote:Thanks for the verification, with actual valid, meaningful math and everything.


    I was dismayed at the vague questions and sloppy myths being perpetrated at the beginning of the thread so I had to do some math to comfort myself. Besides I found it slightly counter-intuitive that the contribution of array-copying to building an ArrayList was only O(1).
    Stephan van Hulst
    Bartender

    Joined: Sep 20, 2010
    Posts: 3647
        
      16

    See also amortized complexity.
     
     
    subject: ArrayList vs LinkedList?