Matthew Merrill
Full Stack Software Developer
Index | Projects | SlidesMeasuring Time Complexity of LinkedList in a Loop
Dependencies
%%loadFromPOM
<repository>
<id>central</id>
<url>https://repo1.maven.org/maven2/</url>
</repository>
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
<dependency>
<groupId>org.knowm.xchart</groupId>
<artifactId>xchart</artifactId>
<version>3.8.1</version>
</dependency>
Timing Methodology
“constructAlgorithm” not defined here, will be defined in an upcoming cell.
import com.google.common.base.Stopwatch;
public long timeRunnable(Runnable r) {
Stopwatch stopwatch = Stopwatch.createStarted();
r.run();
stopwatch.stop();
return stopwatch.elapsed(TimeUnit.MILLISECONDS);
}
public void recordMeasurements(int step, int max, int measurements,
List<Integer> xData, List<Double> yData) {
xData.clear();
yData.clear();
for (int x = 0; x <= max; x += step) {
xData.add(x);
// Record the average measurement
double timeSum = 0;
for (int m = 0; m < measurements; m++) {
long millis = timeRunnable(constructAlgorithm(x));
timeSum += millis / 1000.0d;
}
yData.add(timeSum / measurements);
}
}
Setup & Algorithm
Set up a LinkedList with the requested size, and then return a Runnable that will run the code to be timed. The code we want to time here calls .get() on every index in the list.
The () -> { } wrapping our code creates a Runnable object so that we can time
only the code that
is in the Runnable (we don’t want our setup to be included in the timing.)
import java.util.*;
public Runnable constructAlgorithm(int size) {
// Setup code is NOT timed
List<Integer> list = new LinkedList<>();
for (int idx = 0; idx < size; idx++) {
list.add(idx);
}
// Return a Runnable for the code that we want to time
return () -> {
for (int idx = 0; idx < list.size(); idx++) {
list.get(idx);
}
};
}
Results
10 measurements are averaged for N = 0 1,000 2,000 ... 20,000.
The results are charted and displayed using a simple library XChart.
import org.knowm.xchart.*;
List<Integer> xData = new ArrayList<>();
List<Double> yData = new ArrayList<>();
// Record measurement at N=0, 1000, 2000, ... 20000
recordMeasurements(/* step= */ 1_000,
/* max= */ 20_000,
/* measurements= */ 10,
xData, yData);
XYChart chart = QuickChart.getChart("LinkedList get-in-loop Runtime", "N", "Time (sec)", "T(N)", xData, yData);
BitmapEncoder.getBufferedImage(chart);
Analysis
It is clear from the graph that calling LinkedList#get in a loop to get every
index is not growing linearly with the number of elements. This matches what we
would assume from algorithms theory – LinkedList#get requires O(N) time,
and we perform that O(N) work O(N) times.
N * N = N^2
If we want to be more precise with the amount of work done, the first loop has to traverse 1 node to find the value, the next loop has to traverse 2 nodes, etc until the last loop traverses N nodes.
1 + 2 + 3 + ... + N = N(N+1)/2 = (N^2 + N)/2 = (N^2)/2 + N/2 --> N^2
complexity
Iterating over a LinkedList the Correct Way
To avoid this exponential slowdown with additional items, iterate over your LinkedList using a for-each loop where possible (or move to ArrayList because that’s almost always faster.)
Below is an example of using a for-each loop. The runtime graphs are essentially flat, with the time spent on both algorithms measuring below even a single millisecond at the same max value of 20,000 elements.
public Runnable constructAlgorithm(int size) {
List<Integer> list = new LinkedList<>();
for (int idx = 0; idx < size; idx++) {
list.add(idx);
}
return () -> {
// for each value in the list...
for (Integer value : list) {
// do something with the value
value = value + value;
}
};
}
// Record measurement at N=0, 1000, 2000, ... 20000
recordMeasurements(/* step= */ 1_000,
/* max= */ 20_000,
/* measurements= */ 10,
xData, yData);
XYChart chart = QuickChart.getChart("LinkedList for-each Runtime", "N", "Time (sec)", "T(N)", xData, yData);
BitmapEncoder.getBufferedImage(chart);
public Runnable constructAlgorithm(int size) {
// Using an ArrayList
List<Integer> list = new ArrayList<>();
for (int idx = 0; idx < size; idx++) {
list.add(idx);
}
return () -> {
for (int idx = 0; idx < list.size(); idx++) {
list.get(idx);
}
};
}
// Record measurement at N=0, 1000, 2000, ... 20000
recordMeasurements(/* step= */ 1_000,
/* max= */ 20_000,
/* measurements= */ 10,
xData, yData);
XYChart chart = QuickChart.getChart("ArrayList get-in-loop Runtime", "N", "Time (sec)", "T(N)", xData, yData);
BitmapEncoder.getBufferedImage(chart);
public Runnable constructAlgorithm(int size) {
// Using an ArrayList
List<Integer> list = new ArrayList<>();
for (int idx = 0; idx < size; idx++) {
list.add(idx);
}
return () -> {
// for each value in the list...
for (Integer value : list) {
// do something with the value
value = value + value;
}
};
}
// Record measurement at N=0, 1000, 2000, ... 20000
recordMeasurements(/* step= */ 1_000,
/* max= */ 20_000,
/* measurements= */ 10,
xData, yData);
XYChart chart = QuickChart.getChart("ArrayList for-each Runtime", "N", "Time (sec)", "T(N)", xData, yData);
BitmapEncoder.getBufferedImage(chart);
Conclusion
Just don’t use LinkedList. Use ArrayList.