Assignment 8 - Data Structures 1

Assignment

For each program below:

  • Tell me what the program does. Show what it prints.
  • Explain the results of the program. What is it doing and printing?
  • Try to explain WHY the results are what they are. If you don’t know for certain, create a hypothesis.
  • This has a lot to do with data structures. Make sure your explanation does dive into the particulars of the data structures and what is happening. Don’t give a “surface” explanation, make sure you understand. Ask me questions if needed or check to make sure your are in the right ballpark. This assignment is the easiest to get a bad grade on if you don’t check to make sure.

Part 1

Test01.java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.LinkedList;

public class Test01 {
    private static int n = 10000000;

    private static void link_list_add_test() {
        LinkedList<Integer> list = new LinkedList<Integer>();

        for(int i=0; i < n; i++) {
            // Look up the documentation for the following command
            list.add(0, 0);
        }
    }

    public static void main(String [] args) {
        System.out.println("Starting test...");

        double total_duration = 0.0;
        for(int test=0; test < 20; test++) {
            long startTime = System.nanoTime();
            link_list_add_test();
            long endTime = System.nanoTime();
            double duration = (endTime - startTime) / 1000000000.;
            total_duration += duration;
            System.out.println(String.format("Test took %f seconds.", duration));
        }
        System.out.println(String.format("Total test took %f seconds.", total_duration));

    }
}

Part 2

Test02.java
 1
 2
 3
 4
 5
 6
 7
 8
 9
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class Test02 {
    private static int n = 10000000;

    private static void link_list_add_test() {
        LinkedList<Integer> list = new LinkedList<Integer>();

        for(int i=0; i < n; i++) {
            // Note, this command is different than the one in
            // the prior example!
            list.add(0);
        }
    }

    private static void array_add_test() {
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0; i < n; i++) {
            list.add(0);
        }
    }

    private static void stack_add_test() {
        Stack<Integer> stack = new Stack<Integer>();

        for(int i=0; i < n; i++) {
            stack.add(0);
        }
    }
    public static void main(String [] args) {
        System.out.println("Warming up...");
        for(int test=0; test < 20; test++) {
            array_add_test();
        }

        double total_duration = 0.0;
        System.out.println("Starting array_add_test test...");
        for(int test=0; test < 20; test++) {
            long startTime = System.nanoTime();
            array_add_test();
            long endTime = System.nanoTime();
            double duration = (endTime - startTime) / 1000000000.;
            total_duration += duration;
            System.out.println(String.format("array_add_test test took %f seconds.", duration));
        }
        System.out.println(String.format("Total array_add_test took %f seconds.", total_duration));

        total_duration = 0.0;
        System.out.println("Starting link_list_add_test test...");
        for(int test=0; test < 20; test++) {
            long startTime = System.nanoTime();
            link_list_add_test();
            long endTime = System.nanoTime();
            double duration = (endTime - startTime) / 1000000000.;
            total_duration += duration;
            System.out.println(String.format("link_list_add_test test took %f seconds.", duration));
        }
        System.out.println(String.format("Total link_list_add_test took %f seconds.", total_duration));

        total_duration = 0.0;
        System.out.println("Starting stack_add_test test...");
        for(int test=0; test < 20; test++) {
            long startTime = System.nanoTime();
            stack_add_test();
            long endTime = System.nanoTime();
            double duration = (endTime - startTime) / 1000000000.;
            total_duration += duration;
            System.out.println(String.format("stack_add_test test took %f seconds.", duration));
        }
        System.out.println(String.format("Total stack_add_test took %f seconds.", total_duration));

    }
}

Part 3

Test03.java
 1
 2
 3
 4
 5
 6
 7
 8
 9
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class Test04 {
    public static int n = 100000;

    public static void link_list_access_test() {
        LinkedList<Integer> list = new LinkedList<Integer>();

        for(int i=0; i < n; i++) {
            list.add(0, 0);
        }

        long startTime = System.nanoTime();
        for(int i = 0; i < n; i++) {
            int x = list.get(i);
        }
        long endTime = System.nanoTime();
        double duration = (endTime - startTime) / 1000000000.;
        System.out.println(String.format("link_list_access_test test took %f seconds.", duration));
    }

    public static void array_access_test() {
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0; i < n; i++) {
            list.add(0,0);
        }
        long startTime = System.nanoTime();
        for(int i = 0; i < n; i++) {
            int x = list.get(i);
        }
        long endTime = System.nanoTime();
        double duration = (endTime - startTime) / 1000000000.;
        System.out.println(String.format("array_add_test test took %f seconds.", duration));
    }

    public static void stack_access_test() {
        Stack<Integer> stack = new Stack<Integer>();

        for(int i=0; i < n; i++) {
            stack.add(0, 0);
        }
        long startTime = System.nanoTime();
        for(int i = 0; i < n; i++) {
            int x = stack.get(i);
        }
        long endTime = System.nanoTime();
        double duration = (endTime - startTime) / 1000000000.;
        System.out.println(String.format("stack_access_test test took %f seconds.", duration));
    }

    public static void main(String [] args) {
        link_list_access_test();
        link_list_access_test();
        array_access_test();
        stack_access_test();
    }
}