Recently I have been looking LinkedLists in Java. After some research, I found out that the main benefit of using LinkedList over ArrayList is the fact that it's faster when removing/adding elements mid array in a list with a large amount of data. Therefore, what would be the benefit of using an ArrayList and not always a LinkedList?
For the sake of comparison, I wrote this simple program to compare the run speed between LinkedList and ArrayList. The concept of the program is that it creates an int array of length n and populates it with random integers from Integer.MIN_VALUE to Integer.MAX_VALUE.
Then, it creates another array that is x% of the elements of the first array. For instance, if the first array was [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], the second array, if x was set to 50%, may be [2, 4, 5, 9, 10]. This will result in an array with random elements from the start, middle, and end of the original array.
The run time elapsed during the creation of these arrays is not counted. Afterward, the program creates a LinkedList, add all elements from the first array into this list, and removes the elements of the second array from this list. I repeat this process y times and calculate the average elapsed time using System.nanoTime().
I know my code is far from optimized, but since it is the exact same code for both LinkedList and ArrayList, only changing the type of list that is being created and not pre-setting the size of the list on initialization, the results should not be affected, correct? For example, if my bad code is making it run 400% slower, since both use the same code, the results should not be affected whatsoever, since both are, theoretically, 400% slower.
The results I found are that ArrayLists are, in average, 360% faster than LinkedLists, at least when using a 100 thousand integers array and running it 10 times while removing 45% of the elements.
From what I understood by reading this, this, and this StackOverflow posts that compare the performance of ArrayList and LinkedList, that happens because LinkedLists allocates more memory (24 bytes vs 4 bytes on ArrayLists) per node. Although, theoretically, LinkedLists are faster when adding/removing elements mid array elements, needing only O(n/4) steps on average, while Lists need O(n/2), in reality - at least in my tests and in the tests performed in the posts linked above - that does not seem to be true. If that is the case, then the question inverts itself: what would be the benefit of using LinkedLists and not ArrayList? Only to be able to use list.iterator()?
Here is the exact results I got and the code I used to get them:
It took 53079,970300 ms with LinkedList to run 10 times with an array of 100000 integers removing 45 percent of the elements
The average run time for LinkedList was 5307,997030 ms
It took 14344,833900 ms with normal List to run 10 times with an array of 100000 integers removing 45 percent of the elements
The average run time for normal List was 1434,483390 ms
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public class LinkedLists {
public static void main(String[] args) {
int timesToRun = 10;
int percentageToRemove = 45;
int[] arr = getRandomArray(100_000);
int[] integersToRemoveArr = getIntegersToRemoveArr(percentageToRemove, arr);
long elapsedTime = 0L;
long startTime;
long endTime;
//LinkedLists
startTime = System.nanoTime();
for (int i = 0; i < timesToRun; i++) {
linkedList(arr, integersToRemoveArr);
}
endTime = System.nanoTime();
elapsedTime += endTime - startTime;
System.out.printf("It took %f ms with LinkedList to run %d times with an array of %d integers removing %d percent of the elements\n", (endTime - startTime) * 0.000001, timesToRun, arr.length, percentageToRemove);
System.out.printf("The average run time for LinkedList was %f ms\n", elapsedTime/timesToRun * 0.000001);
//Force GC - again, not sure I need this, just to be safe
Runtime.getRuntime().gc();
//Normal Lists
elapsedTime = 0L;
startTime = System.nanoTime();
for (int i = 0; i < timesToRun; i++) {
normalList(arr, integersToRemoveArr);
}
endTime = System.nanoTime();
elapsedTime += endTime - startTime;
System.out.printf("It took %f ms with normal List to run %d times with an array of %d integers removing %d percent of the elements\n", (endTime - startTime) * 0.000001, timesToRun, arr.length, percentageToRemove);
System.out.printf("The average run time for normal List was %f ms\n", elapsedTime/timesToRun * 0.000001);
}
/**
* Get an array wit X percent of the integers of the providade array
*/
public static int[] getIntegersToRemoveArr(int percentageToRemove, int[] originalArray) {
if (percentageToRemove > 100 || percentageToRemove < 0) {
return new int[]{};
}
List<Integer> indexesToRemove = new ArrayList<>();
while (indexesToRemove.size() < (originalArray.length * (percentageToRemove)/100F)) {
int x = ThreadLocalRandom.current().nextInt(0, originalArray.length-1);
indexesToRemove.add(originalArray[x]);
}
int[] arr = new int[indexesToRemove.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = indexesToRemove.get(i);
}
Arrays.sort(arr);
return arr;
}
public static int[] getRandomArray(int length) {
if (length < 1) {
return new int[]{};
}
int[] arr = new int[length];
for (int i = 0; i < length; i++) {
arr[i] = ThreadLocalRandom.current().nextInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
}
return arr;
}
/**
* Create a LinkedList from the provided array and remove from the list the elements in integersToRemove
*/
public static void linkedList(int[] arr, int[] integersToRemove) {
LinkedList<Integer> list = new LinkedList<>();
for (int i : arr) {
list.add(i);
}
for (int i : integersToRemove) {
list.remove((Integer) i);
}
//Nulling the element to allow GC to remove it - i'm not sure this is needed since I'm not using
//this var anywhere, but just to be safe
list = null;
}
/**
* Create a LinkedList from the provided array and remove from the list the elements in integersToRemove
*/
public static void normalList(int[] arr, int[] integersToRemove) {
List<Integer> list = new ArrayList<>();
for (int i : arr) {
list.add(i);
}
for (int i : integersToRemove) {
list.remove((Integer) i);
}
//Nulling the element to allow GC to remove it - i'm not sure this is needed since I'm not using
//this var anywhere, but just to be safe
list = null;
}
}
