LinkedList and ArrayList both implement List Interface but how they work internally is where the differences lie. The main difference between ArrayList and LinkedList is that ArrayList is implemented using a resizable array while LinkedList is implemented using doubly LinkedList. ArrayList is more popular among Java programmers than LinkedList as there are few scenarios on which LinkedList is a suitable collection than ArrayList. In this article, we will see some differences between LinkedList and ArrayList and try to find out when and where to use LinkedList over ArrayList.
That’s all on the difference between ArrayList and LinkedList in Java. Use ArrayList in Java for all their situation where you need non-synchronized index-based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing ArrayList with a proper initial size.
LinkedList vs ArrayList in Java
All the differences between LinkedList and ArrayList have their root in the difference between Array and LinkedList data structure. If you are familiar with Array and LinkedList data structure you will most likely derive the following differences between them:
1. Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements.
On the Other hand, LinkedList doesn't provide Random or index-based access and you need to iterate over the linked list to retrieve any element which is of order O(n).
2. Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing the array and copying content to the new array if the array gets full which makes adding into ArrayList of O(n) in the worst case while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of the array.
3. Removal is like insertions better in LinkedList than ArrayList.
4. LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds an actual object (data) but in the case of LinkedList, each node holds both data and address of the next and previous node.
When to use LinkedList and ArrayList in Java?
As I said LinkedList is not as popular as ArrayList but still, there are situations where a LinkedList is a better choice than ArrayList in Java. Use LinkedList in Java if:
1. Your application can live without Random access. Because if you need nth element in LinkedList you need to first traverse up to nth element O(n) and then you get data from that node.
2. Your application is more insertion and deletion driver and you insert or remove more than retrieval. Since insertion or removal doesn't involve resizing it's much faster than ArrayList.
And, if you need to know more diffrences betwen ArrayList and LinkedList in Java then here is a nice talbe which you can refer:
That’s all on the difference between ArrayList and LinkedList in Java. Use ArrayList in Java for all their situation where you need non-synchronized index-based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing ArrayList with a proper initial size.
Other Java Tutorials you may like
Thanks for reading this article so far. Let me know if this question was asked to you on any Java Interviews? It was asked to me multiple times and its my favorite one? what about you?
21 comments :
Another difference between LinkedList and ArrayList is that ArrayList is index based while LinkedList is not. I prefer to use ArrayList or Vector but never used LinkedList.
LinkedList vs ArrayList, ArrayList vs LinkedList, ArrayList and LinkedList in Java, LinkedList and ArrayList in Java, Differnece between ArrayList and LinkedList, Difference between LinkedList and ArrayList, What is difference between LinkedList and ArrayList, When to use LinkedList and When to use ArrayList, LinkedList and Array in Java
You may want to have a look at http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list which introduces GapList which strives for combining the strengths of both ArrayList and LinkedList.
Would someone explain why I'm getting better results with inserting to ArrayList list than to LinkedList? Is that some compiler optimization? Using Java 1.6.0 u27.
Here's the code I used:
public class ListsTest {
public static void main(String args[]) {
int count = 10000000;
List arrayList = new ArrayList();
long time = addElements(arrayList, count);
System.out.println("ArrayList with " + count + " elements: " + time
+ " ms.");
List linkedList = new LinkedList();
time = addElements(linkedList, count);
System.out.println("LinkedList with " + count + " elements: " + time
+ " ms.");
}
private static long addElements(List list, int number) {
long start = System.currentTimeMillis();
for (int i = 0; i < number; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
return end - start;
}
}
Hi all - currently thinking of whether to choose ArrayList or LinkedList.
So as i understood from all the comments i found, LinkedList is faster, when inserting at random places, but slower when reading from random index.
But please take a look at the following test:
public class Test {
private static final int NUMBER = 100000;
/**
* @param args
*/
public static void main(String[] args) throws Exception {
testAddEnd(new ArrayList());
testAddEnd(new LinkedList());
testAddEnd(new Vector());
testAddMiddle(new ArrayList());
testAddMiddle2( new LinkedList());
testAddMiddle(new Vector());
testAddStart(new ArrayList());
testAddStart(new LinkedList());
testAddStart(new Vector());
}
private static final void testAddEnd(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
list.add(Integer.valueOf(i));
}
System.out.println("Add End (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}
private static final void testAddMiddle(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(i / 2, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Middle (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}
private static final void testAddMiddle2(LinkedList list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(i / 2, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Middle (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}
private static final void testAddStart(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(0, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Start (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}
}
with the results:
Add End (java.util.ArrayList): 21
Add End (java.util.LinkedList): 15
Add End (java.util.Vector): 11
Add Middle (java.util.ArrayList): 485
Add Middle (java.util.LinkedList): 9192
Add Middle (java.util.Vector): 482
Add Start (java.util.ArrayList): 1108
Add Start (java.util.LinkedList): 15
Add Start (java.util.Vector): 1150
Could you explain this???
Thanks, Dirk.
@Dirk, You can see that LinkedList give better performance than ArrayList while inserting object into either beginning or end , because LinkedList is implemented at DoublyLinked list using Deque interface. Also for random index requires traversal of list either from beginning or end, whichever is closer to the position. That's why insertion on middle is such an expensive operation in LinkedList.
I understand that the right way to traverse a LinkedList is through ListIterator and it scans it sequentially. But Java API does provide an API for random access using get(int index). And in facts its performance is same as of LinkedList (as show from code below). Does it mean Java provides an efficient wrapper API for LinkedList that works like ArrayList?
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList list = new LinkedList();
for (int i =0;i<=1000000; i++) {
list.add(i);
}
long start = System.currentTimeMillis();
list.get(1);
long end = System.currentTimeMillis();
System.out.println(" time to traverse 1st element " + (end - start) );
start = System.currentTimeMillis();
list.get(999999);
end = System.currentTimeMillis();
System.out.println(" time take to traverse 999999th element " + (end - start) );
}
time to traverse 1st element 0
time to traverse 999999th element 0
-- Viv
Does ArraList vs LinkedList is similar to Array vs LinkedList in terms of data structure ?
Guys, before you try to do test like those up here, please keep in mind things like warming up testing environment. You have to pass code optimization by making few(lots) of creating, retriving etc operation as some optimization will be done during compilation some during application running.
Linked list also keeps the order after a remove(index)
Good and clear explanation. Fortunately for me, most of my problems have been of the "array-type" while I was not really aware of linked lists.
Hi Javin..gr8 article few things that I want to add is ...
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList
get is O(n)
add is O(1)
remove is O(n)
Iterator.remove is O(1)
For ArrayList
get is O(1)
add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
remove is O(n)
LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.
ArrayLists, on the other hand, allow random access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average
Another key difference between ArrayList vs LinkedList in Java is that LinkedList implements Queue interface, which means it can be used as FIFO data structures. LinkedList implements method defined in Queue interface e.g. poll(), peek() and offer() which can be used to retrieve and remove head element from list. ArrayList doesn't implement Queue interface. Since LinkedList provides O(1) performance for adding object at beginning and removing object from end, its best suited for such use cases.
I'm using LinkedList only when I need Queue interface features, in all other situations I prefer ArrayList. Nice comparision, good job.
In arraylist too we can remove the elements using the index value: http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#remove(int)
But your following statement is contradictory in the first point:
"but remove is costly in ArrayList as you need to rearrange all elements"
@Anonymous, Yes, we can remove elements by index in ArrayList, but that also shifts subsequent elements to the left by subtracting one from there index, This is costly operation, because it involves calls to System.arraycopy() for copying elements. If you look code for remove(int index) from java.lang.ArrayList, this is clear:
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
QUOTE:"time to traverse 1st element 0
time to traverse 999999th element 0"
The reason of the test result shown above is that the retrieval operation of get(i) method either begin from the beginning or the end of the list. And it depends on which index is closed to index i.So get(1) starts retrieving from the beginning of the list, get(999999) starts from the end instead.
LinkedList can be used as queue,deque and stack and even index-access collection.
LinkedList is truly function-rich.
LinkedList is best suited when you need sequential access to it like adding,removing elements one after another. However indexed access might be not very efficient.
Read my tutorial to know more about internal life of LinkedList here
LinkedList already provides random or index based access / public E get(int index)
Hello Yngvar that comes from List interface but for linked list they won't provide O(1) time, instead O(n).
Again there would be trade off, for linkedList the addition of any new element, how it could be O(1) complexity, it would be O(n), as for every element to be added, you have to traverse the list and added to the end of the list, again for the arraylist if the size of the list is not excceding the available size of the list, it would be o(1) of complexity , and if size exceeds the limit, it would be o(n)
Post a Comment