File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Difference between ArrayList and 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 "Difference between ArrayList and LinkedList?" Watch "Difference between ArrayList and LinkedList?" New topic
Author

Difference between ArrayList and LinkedList?

Thomas Markl
Ranch Hand

Joined: Mar 08, 2001
Posts: 192
What ist the difference between an ArrayList and a LinkedList?
When do we use a LinkedList? What’s the advantage over an ArrayList?


result of both is:
C:\Java\EigeneJavaProgramme>java ListOp1a
[This, is, a, test, test]
Anonymous
Ranch Hand

Joined: Nov 22, 2008
Posts: 18944
Both are similar, though slightly different in terms of goal and implementation. In a LinkedList, each element is linked to its previous and next element making it easier to delete or insert in the middle of the list. A ArrayList is more as its name subjects used as an array.
Performance is similar, though LinkedList is optimized when inserting elements before the end of the list, where ArrayList is optimized when adding elements at the end.
Cheers
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
jeya lakshmi
Greenhorn

Joined: Oct 23, 2009
Posts: 1
public void add(int index,E element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

add(int index,E element)- this method is used to insert a element wherever we want.Then what is the difference between linkedlist and arraylist
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14266
    
  21

jeya lakshmi wrote:Then what is the difference between linkedlist and arraylist

The difference is in the performance characteristics. Because of the way ArrayList and LinkedList work internally, some operations are more efficient on ArrayList, and some operations are more efficient on LinkedList.

For example, inserting an element in the middle of the list is relatively slow on ArrayList, but fast on LinkedList. And looking up a random element in the list is fast on ArrayList, but slow on LinkedList. Which of the two you should choose depends on what you're going to use the list for. This page from Sun's Java Tutorials explains:
If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList. Furthermore, the constant factor for LinkedList is much worse. If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Sam Samson
Ranch Hand

Joined: Oct 08, 2011
Posts: 61

Thomas Paul wrote:Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections


In this newsletter is a table. Regarding this table I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements. LinkedList is only slower when getting an element? I can't remember that I've ever used get(index) on an ArrayList.

I've done some research into this topic via Google. Almost everyone is saying that ArrayList should be chosen. LinkedList uses more memory etc. Here they're discussing it on StackOverflow.

I don't understand the issue with "RandomAccess". What is exactly RandomAccess on an ordered List?

In a for-each loop, which method is called behind the scenes for iterating? get(index)? an Iterator?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

Yes, ArrayList is generally faster. You should almost always prefer it, unless you are doing a *lot* of inserting and removing at places other than the end of the list.

The RandomAccess interface is just a label that some utility classes may check for when they are performing operations on lists. Random access means that reading a value in the middle of the list is just as fast as reading a value at the start or end of the list. A binary search will perform rather poorly on a list that doesn't have random access. So instead, when the algorithm sees that the list doesn't implement RandomAccess, it might first copy the contents of the list to an array (which has random access) before performing the search.

The enhanced for loop (or for-each loop) will use an Iterator behind the scenes. The iterator itself may use the get() method, but this is only the case for random access collections, such as ArrayList. The iterator provided by LinkedList will just have a reference to the current node in the link.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Sam Samson wrote:I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements.


Not quite sure what you're saying here. If you're just going to add at the end with add() and iterate normally with iterator() or foreach, then the performance will be the same.

If you're going to insert an element anywhere but at the end, LL will be faster the closer the insertion point moves to the beginning of the list. The reason for this is that LL just has to update 4 pointers, whereas AL has to copy all the elements after the insertion point. So O(1) for LL vs. O(n) for AL.

However, if you're using an index to get to the location where you're going to insert (as opposed to doing through ListIterator during an iteration), then LL will have an O(n) cost to find the element at that index.

LinkedList is only slower when getting an element?


Yes, the only significant performance disadvantage of LL is when accessing an element by index. For LL that is O(n), since it has to count from the beginning or end of the list, but for AL it's O(1), since it can use indexed access to get straight to the corresponding element in the backing array.

Outside of CPU cycles, LL will use on average about 20-30 byte per element, whereas AL will use about 4. This will really only be significant if your list is very large (probably millions of elements or more) AND the size of one element is under about 200 bytes or so.

I can't remember that I've ever used get(index) on an ArrayList.


It's definitely a less common use case than simply iterating and processing all elements.

Almost everyone is saying that ArrayList should be chosen.


For the vast majority of use cases, there will be no noticeable difference. The most common use case is simply a bunch of add()s, to build it up, and then using iterate() to access the elements for processing. Both will have the same performance for this case. As far as memory goes, since most lists are probably less than a few thousand or tens of thousands of elements, we're talking worst case a few hundred kB difference in memory for the common case.

I don't understand the issue with "RandomAccess". What is exactly RandomAccess on an ordered List?


Accessing any arbitrary element, in no particular order (usually by index), rather than accessing them in order via iteration.

In a for-each loop, which method is called in behind for iterating? get(index)?


No, it uses the Iterator.

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:Yes, ArrayList is generally faster. You should almost always prefer it, unless you are doing a *lot* of inserting and removing at places other than the end of the list.


I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.

I do use AL unless I have a specific reason to use LL, but something's gotta be the default, and for most cases it doesn't matter.
Sam Samson
Ranch Hand

Joined: Oct 08, 2011
Posts: 61

Thanks, now it's a little bit more understandable.

Can you explain me that kind of notation to me? O(1) for LL vs. O(n) for AL. What's the meaning of O?

Summarize:
LinkedList should be chosen if I want to make a lot of insertions(not at the end) and deletions. And get(index) isn't heavily used.

True or false?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18648
    
    8

Sam Samson wrote:
Thomas Paul wrote:Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections


In this newsletter is a table. Regarding this table I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements.


Bear in mind that the newsletter is now nearly 10 years old. Advice about Java performance does not age well so you should normally seek the most recent advice.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.


I meant faster in absolute terms, not in complexity class. On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList. If I set the initial capacity for ArrayList to 10.000.000, it takes 50 ms.

It seems it takes LinkedList a lot of time to create the node objects that wrap the elements.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14266
    
  21

Sam Samson wrote:Can you explain me that kind of notation to me? O(1) for LL vs. O(n) for AL. What's the meaning of O?

See Big O notation. It's a way to express how much work algorithms cost.

O(1) means "constant time"; whatever the input, it will take some constant amount of time to perform the algorithm. For example, in an ArrayList, get(index) is O(1), because no matter how many elements there are in the ArrayList, you can lookup any element in a constant amount of time.

O(n) means "linear time"; the amount of time it takes to run the algorithm is proportional to the size of the input (n). For example, in a LinkedList, get(index) is O(n), because the time it takes to find an arbitrary element in a LinkedList is proportional to the number of elements in the list.

Other common algorithms have a complexity of for example O(n log n), or O(n²).
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:
I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.


I meant faster in absolute terms, not in complexity class.


I figured as much. My point was that since the big-O curves are the same, that absolute performance wouldn't matter.

On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList.


I'm kind of surprised. There was a similar discussion recently, and I thought I created a class to test just that, and got indeterminate results--sometimes LL was faster and sometimes AL. Can't find my test class now.

I still wouldn't choose AL for performance reasons unless I measured and found that LL was causing a bottleneck.

It seems it takes LinkedList a lot of time to create the node objects that wrap the elements.


Yup. I figured the larger array creation and copy would offset that to a greater degree than your numbers suggest.

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:
I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.


I meant faster in absolute terms, not in complexity class. On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList. If I set the initial capacity for ArrayList to 10.000.000, it takes 50 ms.


I changed your test a bit:

1. I always add the same object. Adding the iteration over the array of objects means we're timing more than just the list.add() method.

2. I run the pair of alternating tests 3 times, so any JVM startup issues should wash away.

3. I System.gc() after each individual test, and sleep to give the GC time and the JVM cycles to do it, so each test has the best chance of starting with a clean slate memory wise.

4. I launch the JVM with -Xms1G -Xmx1G, so that we (I hope) won't be measuring time obtaining memory from the OS.

The results are interesting. For 10,000,000 elements, while AL is still faster, it's only a factor of about 2x, vs. your factor of 7x-8x. However, when I bump the size up to 20,000,000, I get a factor of about 6x.

I guess that makes sense. The per-element cost for LL is constant, where as the per-element cost for AL could be decreasing, since the allocate/copy happens less and less frequently as the list gets larger.

(I still wouldn't pick AL for speed as a general rule though. )



Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

I'm curious, could you run the code I posted and report what timings you get? Maybe play around with it, if you want?

I know there are factors involved that my test can't account for, but I still wonder

[edit]

Hah wow you beat me to my own request!
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:I'm curious, could you run the code I posted and report what timings you get? Maybe play around with it, if you want?

I know there are factors involved that my test can't account for, but I still wonder

[edit]

Hah wow you beat me to my own request!


Running your code as-is, no changes except that I'm on 1.6 so can't use 10_000_000, and no -Xms or -Xmx args, I got the following, for 3 consecutive runs:


Putting the 3 runs in one JVM execution:

but no additional changes, I got this:

Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

Thanks, I ran your code and I got about the same results you did, except it seems your system is twice as fast :P

My point is that unless you need random access, or random insertion/removal, there's no good reason to prefer one over the other, other for the fact that ArrayList generally has better coefficients. I think that's a good reason to use it as the default.

I agree it doesn't matter much in the face of bigger performance issues in an application, but what the hey.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19718
    
  20

Jeff Verdegan wrote:

If you use Java 7 you can prevent that unnecessary calculation and simply write 40_000_000. Of course it's only syntactic sugar; the compiler will already turn 40 * 1000 * 1000 into 40000000.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

Jeff Verdegan wrote:[...] I'm on 1.6 so can't use 10_000_000 [...]
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19718
    
  20

Missed that...
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

Stephan van Hulst wrote:My point is that unless you need random access, or random insertion/removal, there's no good reason to prefer one over the other, other for the fact that ArrayList generally has better coefficients. I think that's a good reason to use it as the default.

I agree it doesn't matter much in the face of bigger performance issues in an application, but what the hey.

Do you always know beforehand you'll not need random access to items in an arbitrary list? I use ArrayList by default for that reason alone, LinkedList only when I have documented reason to do so, generally for queues.

Warning: wild speculation: I live under deeply rooted, yet unfounded impression that the more objects are there on the heap, the more work GC has to do. Large LinkedList could therefore put more strain on the GC, as it takes more memory spread among significantly more objects than an ArrayList of the same size. I don't know how to reliably test this assumption, though. Has anybody some ideas on this?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop. When you use the get() method in response to some GUI event then you hardly need random access, since the user isn't going to notice any difference.

These situations are fairly rare, since you mostly want to iterate over the entire list, as opposed to accessing specific elements. Most of the algorithms that do fancy stuff using specific elements are already pretty standard, such as searching and sorting algorithms. They already account for whether the data type they operate on has random access.

I guess in theory a LinkedList would put more strain on the GC, but it's very hard to make any assumptions about stuff that the JVM does behind the scenes.
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

Stephan van Hulst wrote:Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop. When you use the get() method in response to some GUI event then you hardly need random access, since the user isn't going to notice any difference.

That much is clear. I had possible future extensions of the software on my mind. I'm probably just used to being able to pass lists to methods and services that may use random access. It is true that indexed access is not that common, and probably some of its occurrences in my code might indicate a flaw in design (I do use the collection-for-loop whenever possible, of course, but time from time an index access still sneaks in).

The LinkedList main advantage of low-cost insert and deletions is probably also negligible unless the list is really huge and modified a lot, and you should also know that ahead of time.

It simply seems to me that LinkedList has a few very subtle disadvantages (total performance, memory requirements, random access, might be less GC friendly) and perhaps one similarly subtle advantage over an ArrayList that actually gets very rarely utilized (I certainly use index access much more than ListIterator or even Iterator in my code, but others may have a different mileage, of course).
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Rob Spoor wrote:
Jeff Verdegan wrote:

If you use Java 7 you can prevent that unnecessary calculation and simply write 40_000_000. Of course it's only syntactic sugar; the compiler will already turn 40 * 1000 * 1000 into 40000000.


Yup. Not on 7 yet though.
\
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop.


Except that the creator of the List doesn't always know how it will be used.

I guess in theory a LinkedList would put more strain on the GC, but it's very hard to make any assumptions about stuff that the JVM does behind the scenes.


Yeah, it really depends. If the objects are short-lived enough to be reclaimed while still in eden, then I don't think it's any extra strain. IIRC, it's live objects that need to be copied that put the strain on it.

But yes, LL creates more objects than AL, and as a general rule, GC costs increase with object creation. Actually measuring those costs for the scenarios in question is not something I care to dabble in, however.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3647
    
  17

Jeff Verdegan wrote:Except that the creator of the List doesn't always know how it will be used.


Ahh, but that's why methods that do require random access can check whether it's provided ;)

It's funny how this old thread still managed to generate all this interesting discussion
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Stephan van Hulst wrote:
Jeff Verdegan wrote:Except that the creator of the List doesn't always know how it will be used.


Ahh, but that's why methods that do require random access can check whether it's provided ;)


Not disagreeing with that one bit. Just with the claim that, "Yes, you'll always know ahead of time that you need random access."

It's funny how this old thread still managed to generate all this interesting discussion


Indeed.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Difference between ArrayList and LinkedList?