• Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedList vs ArrayList  RSS feed

 
Niki Kulkarni
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Everyone,

I have just begin to understand collections in Java. I read about the differences between LinkedList and ArrayList but have several doubts on it. I have mentioned them below

1) Why retrieving in ArrayList is faster then LinkedList?. Since both have the get method how does performance differ?.
2) How does re-sizing happens internally in ArrayList when a item is added or removed?. How slow this is compared to the pointer re-shuffling in LinkedList when a item is added or removed?.


Thanks for your time.






 
Swastik Dey
Rancher
Posts: 1815
15
Android Eclipse IDE Java Java ME
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Swastik Dey wrote:May be this helps . . .
We're not supposed to say SO is good (‍), but that link is good. The Java Tutorials will probably also help: look for the List Implementations section, but it is worth reading the whole “trail” if you have the time.
 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Niki, welcome to CodeRanch. This is actually an advanced topic if you've just started with collections.

Retrieving from an ArrayList is not necessarily faster than retrieving from a LinkedList. In theory, if you want to retrieve every element from the list once, both should be about equally fast. However, LinkedList is very bad at "random access" (getting a specific element at some position of your choosing). That's because it doesn't have direct access to the element you want. It needs to traverse all the elements before or after it to get to the point you want.

As for the re-sizing, this is a detail that may change per implementation. I believe Oracle's ArrayList doubles in capacity when it's full. This leads to a cost called "Amortized constant time". It means that the cost for growing the list is divided by the size of the list, making the average cost per addition near constant. Growing a LinkedList is also constant, as you may imagine.

However, insertion is a different thing. If you keep inserting elements at the start of a list, ArrayList will be much slower than LinkedList, because an ArrayList needs to move all the elements in the list one place forward.
 
Niki Kulkarni
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Hi Niki, welcome to CodeRanch. This is actually an advanced topic if you've just started with collections.

Retrieving from an ArrayList is not necessarily faster than retrieving from a LinkedList. In theory, if you want to retrieve every element from the list once, both should be about equally fast. However, LinkedList is very bad at "random access" (getting a specific element at some position of your choosing). That's because it doesn't have direct access to the element you want. It needs to traverse all the elements before or after it to get to the point you want.

As for the re-sizing, this is a detail that may change per implementation. I believe Oracle's ArrayList doubles in capacity when it's full. This leads to a cost called "Amortized constant time". It means that the cost for growing the list is divided by the size of the list, making the average cost per addition near constant. Growing a LinkedList is also constant, as you may imagine.

However, insertion is a different thing. If you keep inserting elements at the start of a list, ArrayList will be much slower than LinkedList, because an ArrayList needs to move all the elements in the list one place forward.


Thanks Stephan. I didn't understand couple of points above, I have marked them in bold. Also i have below Question.

If i want to get a element at certain index in LinkedList, does it internally traverse to every item in the List before returning one?. How does it work in ArrayList?.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote:Why retrieving in ArrayList is faster then LinkedList?.

Presuming you're talking about random retrieval (ie, "get me element x"), it's because ArrayList is based on an array; and you probably already know that to get element x from an array, you simply write array[x] (and it's blisteringly fast).

LinkedList's are made up of "nodes" that link to each other, so getting from one node to the next one (in either direction) is very quick, but getting directly to a node x is not. There are variants (eg, Skiplists) that do make this process much quicker, but unfortunately, Java doesn't yet have an implementation that implements List (no idea why not). It does have one that implements Set though (ConcurrentSkipListSet).

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote:Thanks Stephan. I didn't understand couple of points above, I have marked them in bold.

The explanation of "amortized" time is a bit involved, but basically, it works like this:
Because Arraylists are based on arrays, and arrays have a fixed size, if you fill up the array, you need to reallocate it (and copy the contents of the old one) in order to fit new elements in. If you do that, say, every 10 elements you add (ie, a constant), then the cost of that reallocation is directly related to the number of elements in the array. If on the other hand you double the size every time, there's a limit to the number of times you can do it before you run out of room (you can't create an array larger than 2 billion elements), so the cost isn't directly linked to the number of elements.

Unfortunately, there's another cost associated with what Stephan was talking about: In order to add a new element at the first position, an ArrayList has to shift all the other elements one position to the right (whether it also reallocates or not); a LinkedList simply needs to add a new Node that links to the "old first" Node.

If i want to get a element at certain index in LinkedList, does it internally traverse to every item in the List before returning one?.

Yes.

How does it work in ArrayList?.

See my previous post.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ArrayLists are built on top of arrays, which Winston already explained are extremely fast. Most importantly, it takes them as much time to retrieve array[5] as array[26], this is called "random access". The problem with arrays is that they cannot grow dynamically. Once you have an array of a particular size, you're stuck with that size.

So let's say your ArrayList has size 4, and its underlying array also has length 4 (in other words, the list is "full"). When you want to add another element, the ArrayList has to "grow". It does this by creating a new array of length 8, and moving the 4 existing elements into the first four slots. After the next four slots have been filled, ArrayList will create a new array of length 16.

As you can see, when the list is full, it has to take some extra time to grow, before you can add another element. The cost of growing the list becomes higher, because it has more elements to copy. However, it also has to perform this growing operation fewer times as the list grows. When you divide the cost of growing the list by the size of the list, you get the average cost of growth, per addition to the list. This average cost is constant, and is named "Amortized constant time". The word "amortized" here is to tell us that the cost of adding an element to the list has a cost involved that may be very high for some elements, but gets smeared over all elements that have already been added.

Insertion at the start of a list is very difficult for ArrayLists. You have to copy every element in the list, and move it one place forward, to make room for the new element. LinkedLists don't have this problem. You just create a new node to hold your element, tell the list that it is the new head, and let it link to the former head of the list.
 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Annndddd.... Winston is faster than Stephan at adding stuff at the end of a topic ;)
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Annndddd.... Winston is faster than Stephan at adding stuff at the end of a topic ;)

That's a first. I'm usually the snail.

Winston
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote: . . . If i want to get a element at certain index in LinkedList, does it internally traverse to every item in the List before returning one?. . . .
Yes.

I think Stephan and Winston have already explained how that happens.
 
Niki Kulkarni
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Winston and Stephan for detailed explanation.
I have couple of more questions below.
1. Why does the ArrayList growing operation becomes fewer when the list is more?
2. Only advantage of ArrayList I see is that retrieval is quicker. Since ArrayList creates a copy every time when its full, Will it not cause performance degredation when using it for larger data storage?
 
Stuart A. Burkett
Ranch Hand
Posts: 679
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote:1. Why does the ArrayList growing operation becomes fewer when the list is more?

Can you rephrase that ? I don't understand what you are asking.

Niki Kulkarni wrote:Since ArrayList creates a copy every time when its full, Will it not cause performance degredation when using it for larger data storage?

That's what the ensurecapacity method is for. If you know you are going to be adding a large amount of elements to the ArrayList, you make sure it is big enough to hold that data and so doesn't require any resizing.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote:Thanks Winston and Stephan for detailed explanation.

You're welcome.

1. Why does the ArrayList growing operation becomes fewer when the list is more?

Don't understand the question. I presume you follow what it means when we say that we double the size of the array every time?

Only advantage of ArrayList I see is that retrieval is quicker.

No. Random retrieval ("get me element x") is quicker. And that's actually quite a biggie in a lot of cases.

Since ArrayList creates a copy every time when its full, Will it not cause performance degredation when using it for larger data storage?

As with almost everything in programming, the answer is: it depends. And if you know how many items the List is going to need beforehand, you can create one with an initial capacity, which eliminates the need for ANY reallocating.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Niki Kulkarni wrote:1. Why does the ArrayList growing operation becomes fewer when the list is more?

Because the growing doubles the capacity every time. So if you have a list of size 4, double it's capacity, you can add 4 elements before it has to grow again. Then after you double it, you can add 8 elements before you have to double it.

2. Only advantage of ArrayList I see is that retrieval is quicker. Since ArrayList creates a copy every time when its full, Will it not cause performance degredation when using it for larger data storage?


No, because as we have explained, addition has amortized constant time. If you have a really really large data storage, sure it will cost some time if you have to double it, but the chances of having to double are also very low.

ArrayLists are preferred to LinkedLists because they are usually faster (in absolute time) at almost everything than a LinkedList is. The cost of growing a list is relatively low compared to creating a new Node object for every element of the LinkedList. The only thing ArrayLists really suck at is random insertion.
 
Stuart A. Burkett
Ranch Hand
Posts: 679
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Niki Kulkarni wrote:1. Why does the ArrayList growing operation becomes fewer when the list is more?

Because the growing doubles the capacity every time.

That's what I thought as well, but according to the Javadoc
As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

So, while a specific implementation of ArrayList might double the capacity every time, there's no guarantee that that will happen.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stuart A. Burkett wrote:So, while a specific implementation of ArrayList might double the capacity every time, there's no guarantee that that will happen.

It does, however, have to be done in a manner that fulfils the "amortized constant time" requirement which, reading between the lines, means that it almost certainly has to be based on current capacity; it can't be a constant.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stuart A. Burkett wrote:
Stephan van Hulst wrote:Because the growing doubles the capacity every time.

That's what I thought as well, but according to the Javadoc
As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

So, while a specific implementation of ArrayList might double the capacity every time, there's no guarantee that that will happen.

Stephan van Hulst wrote:As for the re-sizing, this is a detail that may change per implementation. I believe Oracle's ArrayList doubles in capacity when it's full.

 
Niki Kulkarni
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Niki Kulkarni wrote:
2. Only advantage of ArrayList I see is that retrieval is quicker. Since ArrayList creates a copy every time when its full, Will it not cause performance degredation when using it for larger data storage?


No, because as we have explained, addition has amortized constant time. If you have a really really large data storage, sure it will cost some time if you have to double it, but the chances of having to double are also very low.

ArrayLists are preferred to LinkedLists because they are usually faster (in absolute time) at almost everything than a LinkedList is. The cost of growing a list is relatively low compared to creating a new Node object for every element of the LinkedList. The only thing ArrayLists really suck at is random insertion


Is random insertion in ArrayList so expensive?. Is it good to avoid random insertion while using ArrayList and how can it be managed when using larger applications?.

 
Stephan van Hulst
Saloon Keeper
Posts: 7976
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just don't try anything funny. If you use the Collection interface instead of the List interface wherever you can, you will end up being able to do a lot less wrong.
 
Niki Kulkarni
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Just don't try anything funny. If you use the Collection interface instead of the List interface wherever you can, you will end up being able to do a lot less wrong.


Sure . Thanks Stephan


Thanks Everyone for your time
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!