Matthew Merrill

Full Stack Software Developer

Index | Projects | Slides | Resume

Measuring 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);

png

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);

png

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);

png

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);

png

Conclusion

Just don’t use LinkedList. Use ArrayList.


Matthew Merrill 2021
www.mattmerr.com EMail | Keys | LinkedIn | GitHub | Dark Mode Light Mode