- Manipulation: Moving elements around and changing elements in LinkedLists takes less time because, as you saw by the implementation, you can simply change node references. ArrayLists internally use arrays, so manipulating elements in ArrayLists requires traversing an array and physically shifting memory bits around, which takes more time.
- Adding to front or back: It’s easier to end to the front or end of a LinkedList because you simply change the head or tail node. Adding to the beginning of an ArrayList requires transferring all the data down one position, which takes more time.
- Storing: It’s more efficient to store elements in an ArrayList if you’re not going to change elements around too much.
- Accessing: It takes less time to access an element in an ArrayList because it internally uses arrays, so elements can be accessed immediately. To access an element in a LinkedList, you have to traverse down the entire list one by one until you reach the node you want
Let’s demonstrate these differences by actually measuring the time it takes to complete an operation: adding elements to a list.
Here is our test code:
long a, b; LinkedList<Integer> list1 = new LinkedList<Integers>(); a = System.nanoTime(); for(int i=0; i<10000; i++) list1.add(1); b = System.nanoTime(); System.out.println("Linked: " + (b-a) + " ns"); ArrayList<Integer> list2 = new ArrayList<Integer>(); a = System.nanoTime(); for(int i=0; i<10000; i++) list2.add(1); b = System.nanoTime(); System.out.println("ArrayList: " + (b-a) + " ns");
System.nanoTime() is a method which returns the current time of the system in nanoseconds. We record the time and store it in a, complete our operation, and then record the time again to store it in b. (a and b are longs because the current time in nanoseconds is too large to fit in an integer.)
We add a large number of elements (10,000) because the efficiency differences usually only show up when dealing with large amounts of data. We just add the element “1” repeatedly for simplicity.
Here is the output:
Linked: 10251960 ns ArrayList: 18086990 ns
Clearly, the LinkedList takes much less time to add a large number of elements than the ArrayList does. Also, note that these numbers will be different every time you run the code because your computer will probably be doing other tasks (with other apps running in the background, like connecting to Google, keeping track of time, etc.), but the LinkedList will always take less time in general.