CSC300: Linear versus Constant Time [3/8] Previous pageContentsNext page

Accessing a linked list element is linear time

Accessing an array list element is constant time

file:PlaygroundIndexing.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
package algs14;
import java.util.*;
import stdlib.*;
public class PlaygroundIndexing { 
  public static void main (String[] args) {
    ArrayList<Integer> array =  new ArrayList<>();
    LinkedList<Integer> linked =  new LinkedList<>();
    int size = 60_000_000;
    for (int i=1; i<=size; i++) {
      array.add(i);
      linked.add(i);
    }
    
    int MIN = 256;
    int MAX = size;
    double prevTime = performanceLinked (linked, MIN);
    for (int N = MIN*2; N <= MAX; N=N*2) {
      double time = performanceLinked (linked, N);
      StdOut.format ("Linked elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }

    MIN = 256;
    MAX = size;
    prevTime = performanceArray (array, MIN);
    for (int N = MIN*2; N <= MAX; N=N*2) {
      double time = performanceArray (array, N);
      StdOut.format ("Array  elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }
  }
  private static double performanceLinked (LinkedList<Integer> linked, int N) {
    Stopwatch sw = new Stopwatch ();
    linked.get(N);
    return sw.elapsedTime ();
  }
  private static double performanceArray (ArrayList<Integer> linked, int N) {
    Stopwatch sw = new Stopwatch ();
    linked.get(N);
    return sw.elapsedTime ();
  }
  
}

Output 

Linked elapsed count N=          512 [     0.000 :        NaN]
Linked elapsed count N=        1,024 [     0.000 :        NaN]
Linked elapsed count N=        2,048 [     0.000 :        NaN]
Linked elapsed count N=        4,096 [     0.000 :        NaN]
Linked elapsed count N=        8,192 [     0.000 :        NaN]
Linked elapsed count N=       16,384 [     0.000 :        NaN]
Linked elapsed count N=       32,768 [     0.000 :        NaN]
Linked elapsed count N=       65,536 [     0.001 :   Infinity]
Linked elapsed count N=      131,072 [     0.001 :      1.000]
Linked elapsed count N=      262,144 [     0.002 :      2.000]
Linked elapsed count N=      524,288 [     0.003 :      1.500]
Linked elapsed count N=    1,048,576 [     0.005 :      1.667]
Linked elapsed count N=    2,097,152 [     0.010 :      2.000]
Linked elapsed count N=    4,194,304 [     0.024 :      2.400]
Linked elapsed count N=    8,388,608 [     0.075 :      3.125]
Linked elapsed count N=   16,777,216 [     0.151 :      2.013]
Linked elapsed count N=   33,554,432 [     0.211 :      1.397]
Array  elapsed count N=          512 [     0.000 :        NaN]
Array  elapsed count N=        1,024 [     0.000 :        NaN]
Array  elapsed count N=        2,048 [     0.000 :        NaN]
Array  elapsed count N=        4,096 [     0.000 :        NaN]
Array  elapsed count N=        8,192 [     0.000 :        NaN]
Array  elapsed count N=       16,384 [     0.000 :        NaN]
Array  elapsed count N=       32,768 [     0.000 :        NaN]
Array  elapsed count N=       65,536 [     0.000 :        NaN]
Array  elapsed count N=      131,072 [     0.000 :        NaN]
Array  elapsed count N=      262,144 [     0.000 :        NaN]
Array  elapsed count N=      524,288 [     0.000 :        NaN]
Array  elapsed count N=    1,048,576 [     0.000 :        NaN]
Array  elapsed count N=    2,097,152 [     0.000 :        NaN]
Array  elapsed count N=    4,194,304 [     0.000 :        NaN]
Array  elapsed count N=    8,388,608 [     0.000 :        NaN]
Array  elapsed count N=   16,777,216 [     0.000 :        NaN]
Array  elapsed count N=   33,554,432 [     0.000 :        NaN]

Previous pageContentsNext page