8. ADTs and Lists Lesson

Lesson Objectives

Introduce linked lists and use them to implement the Stack ADT.

The Node Class

The Node Class

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Four Activities

Today, we are going to work through five group activities related to your recent readings on linked lists and ADTs.

Rapid Fire Review

In your groups, answer each of the following multiple-select questions. Each person should have their own copy of the questions and solution(s) in addition to what is on your exit ticket.

  1. What is a linked list?

    1. A collection of data stored in contiguous memory locations.

    2. A sequence of objects where each object references the next.

    3. A type of array where elements are accessed randomly.

    4. A data structure that performs better in all situations than an array.

  2. What does the next instance variable in a Node object do?

    1. Stores the value of the Node.

    2. Links to the previous Node in the sequence.

    3. Links to the next Node in the linked list.

    4. Stores the index of the Node in an array.

  3. Which of the following statements best describes a primary advantage of using a linked list over an array?

    1. Linked lists are stored in contiguous memory, making access to elements faster.

    2. Linked lists are easier to search than arrays.

    3. Linked lists can grow dynamically without the need to reallocate memory.

    4. Linked lists can only store string data types.

  4. Why is a linked list considered an alternative to an array?

    1. Linked lists and arrays have identical performance characteristics.

    2. Both store collections of data but handle memory allocation and access differently.

    3. Linked lists are always faster than arrays.

    4. Arrays can only hold integer values while linked lists can hold any data type.

Code Tracing 1

In your groups, draw the memory map for the following code and then write the output for the print statements. Each person should have their own copy of the memory map in addition to the one on your exit ticket.

Listing 70 Code Tracing 1
 2public static void main(String[] args) {
 3
 4    Node node = new Node("Billy");
 5    node.setItem("Susan");
 6    node.setNext(new Node("Sally"));
 7    node.getNext().setNext(new Node("Barry"));
 8
 9    Node end = new Node("Supa Mike", node);
10    Node n = node.getNext();
11    n.setNext(new Node("Simon"));
12
13    System.out.println(node.getItem());                     // Output 1
14    System.out.println(node.getNext().getItem());           // Output 2
15    System.out.println(end.getItem());                      // Output 3
16    System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18} // main
Code Tracing 1: Sample Solution

Note

The one-parameter Node constructor uses this(item, null); to call the two-parameter constructor. Both constructor calls initialize the same object. This is why <init> (the name used for constructors in the trace) appears twice for that object when stepping through its construction; a second object is not created.

Step 1 of 14: Driver.java:4
Listing 71 Code visualization for Code Tracing 1.
 4Node node = new Node("Billy");
 5node.setItem("Susan");
 6node.setNext(new Node("Sally"));
 7node.getNext().setNext(new Node("Barry"));
 8
 9Node end = new Node("Supa Mike", node);
10Node n = node.getNext();
11n.setNext(new Node("Simon"));
12
13System.out.println(node.getItem());                     // Output 1
14System.out.println(node.getNext().getItem());           // Output 2
15System.out.println(end.getItem());                      // Output 3
16System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20String lastItem = node.getNext().getNext().getNext().getItem();
21System.out.println(lastItem);                           // Output 6 (reachable?)

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 4

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 4 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 5

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 5 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 6

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 7

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 7 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 9

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 9 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 10

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 10 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 11

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 11 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 13

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 13 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 14

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 14 in Driver.java. [code listing] [download] [open]

Susan

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 15

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 15 in Driver.java. [code listing] [download] [open]

Susan
Sally

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 16

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 16 in Driver.java. [code listing] [download] [open]

Susan
Sally
Supa Mike

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 18

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 18 in Driver.java. [code listing] [download] [open]

Susan
Sally
Supa Mike
Simon

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 20

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 20 in Driver.java. [code listing] [download] [open]

Susan
Sally
Supa Mike
Simon
null

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node node = new Node("Billy");
 5        node.setItem("Susan");
 6        node.setNext(new Node("Sally"));
 7        node.getNext().setNext(new Node("Barry"));
 8
 9        Node end = new Node("Supa Mike", node);
10        Node n = node.getNext();
11        n.setNext(new Node("Simon"));
12
13        System.out.println(node.getItem());                     // Output 1
14        System.out.println(node.getNext().getItem());           // Output 2
15        System.out.println(end.getItem());                      // Output 3
16        System.out.println(node.getNext().getNext().getItem()); // Output 4
17
18        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)
19
20        String lastItem = node.getNext().getNext().getNext().getItem();
21        System.out.println(lastItem);                           // Output 6 (reachable?)
22    } // main
23
24} // Driver
Code visualization diagram for Driver.java line 20

Code visualization for Code Tracing 1. Note: The debugger breakpoint is on line 20 in Driver.java. [code listing] [download] [open]

Susan
Sally
Supa Mike
Simon
null
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Node.getItem()" because the return value of "Node.getNext()" is null
	at Driver.main(Driver.java:20)

>_ Console Output

Code Writing 1
Code visualization diagram for lectures/lesson8:190 (end of main)

Final captured memory state. [download] [open]

In your groups, write the code to produce a linked list that looks like the one depicted in the memory map above.

Code Writing 1: Sample Solutions
Sample Solution 1

Note

The sample solution approaches the problem by repeatedly prepending nodes in the linked list.

Step 1 of 4: Driver.java:4
Listing 72 Code Writing 1: Sample Solution 1.
Node head = new Node("third", null); // line 4
head = new Node("second", head);     // line 5
head = new Node("first", head);      // line 6

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("third", null); // line 4
5        head = new Node("second", head);     // line 5
6        head = new Node("first", head);      // line 6
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 4

Memory Map for Code Writing 1: Sample Solution 1. Note: The debugger breakpoint is on line 4 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("third", null); // line 4
5        head = new Node("second", head);     // line 5
6        head = new Node("first", head);      // line 6
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 5

Memory Map for Code Writing 1: Sample Solution 1. Note: The debugger breakpoint is on line 5 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("third", null); // line 4
5        head = new Node("second", head);     // line 5
6        head = new Node("first", head);      // line 6
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 6

Memory Map for Code Writing 1: Sample Solution 1. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("third", null); // line 4
5        head = new Node("second", head);     // line 5
6        head = new Node("first", head);      // line 6
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 7

Memory Map for Code Writing 1: Sample Solution 1. Note: The debugger breakpoint is on line 7 in Driver.java. [code listing] [download] [open]

Sample Solution 2

Note

The sample solution approaches the problem by repeatedly appending nodes in the linked list. It does not scale well.

Step 1 of 4: Driver.java:4
Listing 73 Code Writing: Sample Solution 2.
Node head = new Node("first", null);
head.setNext(new Node("second", null));
head.getNext().setNext(new Node("third", null));

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first", null);
5        head.setNext(new Node("second", null));
6        head.getNext().setNext(new Node("third", null));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 4

Code Writing: Sample Solution 2. Note: The debugger breakpoint is on line 4 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first", null);
5        head.setNext(new Node("second", null));
6        head.getNext().setNext(new Node("third", null));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 5

Code Writing: Sample Solution 2. Note: The debugger breakpoint is on line 5 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first", null);
5        head.setNext(new Node("second", null));
6        head.getNext().setNext(new Node("third", null));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 6

Code Writing: Sample Solution 2. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first", null);
5        head.setNext(new Node("second", null));
6        head.getNext().setNext(new Node("third", null));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 7

Code Writing: Sample Solution 2. Note: The debugger breakpoint is on line 7 in Driver.java. [code listing] [download] [open]

Sample Solution 3

Note

This sample solution does not match up exactly since it introduces additional local variables (besides just head) that were not in the original memory map.

Step 1 of 7: Driver.java:4
Listing 74 Code Writing: Sample Solution 3.
Node first = new Node("first", null);
Node second = new Node("second", null);
Node third = new Node("third", null);

first.setNext(second);
second.setNext(third);

Node head = first;

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 4

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 4 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 5

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 5 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 6

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 8

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 8 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 9

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 9 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 11

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 11 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node first = new Node("first", null);
 5        Node second = new Node("second", null);
 6        Node third = new Node("third", null);
 7
 8        first.setNext(second);
 9        second.setNext(third);
10
11        Node head = first;
12    } // main
13
14} // Driver
Code visualization diagram for Driver.java line 12

Code Writing: Sample Solution 3. Note: The debugger breakpoint is on line 12 in Driver.java. [code listing] [download] [open]

Sample Solution 4

Note

We do NOT recommend this one. It works, but it is hard to read.

Step 1 of 2: Driver.java:6
Listing 75 Code Writing: Sample Solution 4.
// Node head = new Node("first", new Node("second", new Node("third")));

Node head = new Node(
    "first",
    new Node(
        "second",
        new Node(
            "third",
            null
        )
    )
);

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        // Node head = new Node("first", new Node("second", new Node("third")));
 5
 6        Node head = new Node(
 7            "first",
 8            new Node(
 9                "second",
10                new Node(
11                    "third",
12                    null
13                )
14            )
15        );
16    } // main
17
18} // Driver
Code visualization diagram for Driver.java line 6

Code Writing: Sample Solution 4. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        // Node head = new Node("first", new Node("second", new Node("third")));
 5
 6        Node head = new Node(
 7            "first",
 8            new Node(
 9                "second",
10                new Node(
11                    "third",
12                    null
13                )
14            )
15        );
16    } // main
17
18} // Driver
Code visualization diagram for Driver.java line 16

Code Writing: Sample Solution 4. Note: The debugger breakpoint is on line 16 in Driver.java. [code listing] [download] [open]

Sample Solution 5

Note

This sample solution inserts the node for "second" last, but it still produces the same final result.

Step 1 of 4: Driver.java:4
Listing 76 Code Writing: Sample Solution 5.
Node head = new Node("first");
head.setNext(new Node("third"));
head.setNext(new Node("second", head.getNext()));

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first");
5        head.setNext(new Node("third"));
6        head.setNext(new Node("second", head.getNext()));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 4

Code Writing: Sample Solution 5. Note: The debugger breakpoint is on line 4 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first");
5        head.setNext(new Node("third"));
6        head.setNext(new Node("second", head.getNext()));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 5

Code Writing: Sample Solution 5. Note: The debugger breakpoint is on line 5 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first");
5        head.setNext(new Node("third"));
6        head.setNext(new Node("second", head.getNext()));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 6

Code Writing: Sample Solution 5. Note: The debugger breakpoint is on line 6 in Driver.java. [code listing] [download] [open]

Driver.java

1public class Driver {
2
3    public static void main(String[] args) {
4        Node head = new Node("first");
5        head.setNext(new Node("third"));
6        head.setNext(new Node("second", head.getNext()));
7    } // main
8
9} // Driver
Code visualization diagram for Driver.java line 7

Code Writing: Sample Solution 5. Note: The debugger breakpoint is on line 7 in Driver.java. [code listing] [download] [open]

Code Tracing 2

Draw the memory map for the code below and write the output produced by the following code:

 4Node head = new Node("date");
 5head = new Node("cherry", head);
 6head = new Node("banana", head);
 7head = new Node("apple", head);
 8
 9Node current = head;
10while (current != null) {
11   System.out.print(current.getItem() + " ");
12   current = current.getNext();
13} // while
Memory Maps

Note

The final two steps below show what memory looks like just before and immediately after executing the while-loop.

Step 1 of 19: Driver.java:4

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 4

Memory state at the breakpoint on line 4 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 5

Memory state at the breakpoint on line 5 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 6

Memory state at the breakpoint on line 6 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 7

Memory state at the breakpoint on line 7 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 9

Memory state at the breakpoint on line 9 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 10

Memory state at the breakpoint on line 10 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 11

Memory state at the breakpoint on line 11 in Driver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 12

Memory state at the breakpoint on line 12 in Driver.java. [code listing] [download] [open]

apple 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 10

Memory state at the breakpoint on line 10 in Driver.java. [code listing] [download] [open]

apple 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 11

Memory state at the breakpoint on line 11 in Driver.java. [code listing] [download] [open]

apple 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 12

Memory state at the breakpoint on line 12 in Driver.java. [code listing] [download] [open]

apple banana 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 10

Memory state at the breakpoint on line 10 in Driver.java. [code listing] [download] [open]

apple banana 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 11

Memory state at the breakpoint on line 11 in Driver.java. [code listing] [download] [open]

apple banana 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 12

Memory state at the breakpoint on line 12 in Driver.java. [code listing] [download] [open]

apple banana cherry 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 10

Memory state at the breakpoint on line 10 in Driver.java. [code listing] [download] [open]

apple banana cherry 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 11

Memory state at the breakpoint on line 11 in Driver.java. [code listing] [download] [open]

apple banana cherry 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 12

Memory state at the breakpoint on line 12 in Driver.java. [code listing] [download] [open]

apple banana cherry date 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 10

Memory state at the breakpoint on line 10 in Driver.java. [code listing] [download] [open]

apple banana cherry date 

>_ Console Output

Driver.java

 1public class Driver {
 2
 3    public static void main(String[] args) {
 4        Node head = new Node("date");
 5        head = new Node("cherry", head);
 6        head = new Node("banana", head);
 7        head = new Node("apple", head);
 8
 9        Node current = head;
10        while (current != null) {
11           System.out.print(current.getItem() + " ");
12           current = current.getNext();
13        } // while
14    } // main
15
16} // Driver
Code visualization diagram for Driver.java line 14

Memory state at the breakpoint on line 14 in Driver.java. [code listing] [download] [open]

apple banana cherry date 

>_ Console Output

Solution
Code visualization diagram for lectures/lesson8:381 (end of main)

Final captured memory state. [download] [open]

Code Writing 2

In your groups, write a method with the signature below. You do not need to rewrite the Javadoc comment.

 1/**
 2 * Returns with a reference to the {@code Node} that can be
 3 * reached after traversing {@code numLinks}
 4 * many links starting at {@code node}.
 5 *
 6 * @param node the node where we begin the search.
 7 * @param numLinks the number of links to traverse.
 8 * @return node at {@code numLinks} links beyond {@code node}.
 9 */
10public static Node getNode(Node node, int numLinks) {
11    throw new UnsupportedOperationException("not yet implemented");
12} // getNode
Code Writing 3

Write a method called getItem that returns with the item reference value stored in the node that is numLinks beyond the starting node (instead of a reference to the node itself).

Can you write the method body in one line?

Implementing the Stack ADT

Implementing the Stack ADT

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Getting Started
Warmup

Answer the following questions on your exit ticket:

  1. What is an Abstract Data Type (ADT)?

    1. A low-level description of a data structure's implementation.

    2. A predefined class in the Java library.

    3. A high-level description of the operations available on a collection of data.

    4. A specific method for implementing data structures in Java.


  2. How does polymorphism relate to ADTs in Java?

    1. Polymorphism allows multiple ADTs to be defined within the same class.

    2. Polymorphism enables the List interface to be implemented by different classes, like ArrayBasedList and LinkedBasedList.

    3. Polymorphism is only applicable when using arrays as underlying structures.

    4. Polymorphism is not used in conjunction with ADTs.


  3. Why is it beneficial to have different implementations of an ADT like the List interface?

    1. It allows the programmer to access more methods.

    2. It simplifies the process of writing new code.

    3. It eliminates the need for interfaces in Java.

    4. It provides flexibility in choosing an implementation that is more efficient for the specific application.

Code Writing 1: Sample Solutions
  1. C

  2. B

  3. D

What is a Stack?

We will implement the Stack ADT according to the following specification:

Starter Code (for instructors)

Bundle

Execute the command below to download and extract the files:

bundle1302 stack-starter
- downloading cs1302-stack-starter bundle...
- verifying integrity of downloaded files using sha256sum...
- extracting downloaded archive...
- removing intermediate files...
subdirectory cs1302-stack-starter successfully created
  • cs1302.adt: Stack interface and implementations.

  • cs1302.test: Stack test code.

  • Compile script is in the directory. It compiles everything and runs StackTester.

Starter Code (for those not on Odin)

Execute the git clone command shown below to download the files for this lesson into a directory named cs1302-adt-lesson:

git clone https://github.com/cs1302uga/cs1302-adt-lesson.git
Starter Code (for students)

Execute the adt1302 command shown below on Odin to download the files for this lesson using Git into a directory named cs1302-adt-lesson:

adt1302
+ git clone https://github.com/cs1302uga/cs1302-adt-lesson.git
Cloning into 'cs1302-adt-lesson'...
remote: Enumerating objects: 46, done.
remote: Counting objects: 100% (46/46), done.
remote: Compressing objects: 100% (26/26), done.
remote: Total 46 (delta 12), reused 40 (delta 8), pack-reused 0 (from 0)
Receiving objects: 100% (46/46), 11.58 KiB | 697.00 KiB/s, done.
Resolving deltas: 100% (12/12), done.
UML (No Tests)
Unit Testing

The code below is a slightly modified test case from our StackTester class.

 1public void unitTest() {
 2
 3   Stack stack = new OracleStack();
 4   stack.push("a");
 5   stack.push("b");
 6   stack.push("c");
 7
 8   // ...
 9
10} // unitTest

The code above could be the setup for many, separate unit tests. For each of the scenarios below, we would create a separate method (unit test) in our test class. What code could we add to the end of this method to test the following:

  • If our stack contains the correct number of elements.

  • If the correct value is at the top of the stack.

  • If the stack contains the correct values throughout.

In practice, these would be three separate test methods, even though they share the same test scenario.

UML (With Tests)
Part 1: BaseStack
Code Tracing

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new ArrayStack();
Sample Solution
Code visualization diagram for lectures/lesson8:354 (end of main)

Final captured memory state. [download] [open]

Inspecting the Tests

Important

If you do not have the cs1302-adt-lesson directory that was downloaded in a previous part of this lesson, then run the adt1302 command on Odin to download it using Git.

Execute the following command on Odin within the cs1302-adt-lesson directory

git checkout -b activity part1

With your groups, inspect StackTester.java in the cs1302.test package and carefully review the following methods:

  • newStack

  • stackTest01

  • stackTest02

On your exit ticket, answer the following questions about those methods:

  1. What are these methods testing?

  2. What methods will we need to implement to make sure we pass these tests?

Implementation

To pass the current set of tests, implement the following methods with your group:

Class

Method

Note

BaseStack

default constructor

Initialize instance variables appropriately.

BaseStack

int size()

This a "getter" method without "get" in its name.

BaseStack

boolean isEmpty()

Try calling the int size() method when writing this.

ArrayStack

default constructor

Do not forget to call super(), and please initial the array so that its length is 3.

Then, compile and run the code using the provided interpreter script:

./compile_and_run.sh

You should see "PASS" printed on the screen multiple times. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Warning

If you have placed Emacs into the background, then make sure that you have saved any files under src that are currently open to avoid accidentally adding backup files when adding and committing using Git.

git add src
git commit -m "Finished part 1"
git merge part2
Part 2: ArrayStack Push
Code Tracing 1

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new ArrayStack();
stack.push("a");
Solution
Code visualization diagram for lectures/lesson8:475 (end of main)

Final captured memory state. [download] [open]

Code Tracing 2

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new ArrayStack();
stack.push("a");
stack.push("b");
stack.push("c");
Solution
Code visualization diagram for lectures/lesson8:508 (line 5)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:508 (line 6)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:508 (line 7)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:508 (line 8)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 8. [download] [open]

Code Tracing 3

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new ArrayStack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
Solution
Code visualization diagram for lectures/lesson8:546 (line 5)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:546 (line 6)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:546 (line 7)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:546 (line 8)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 8. [download] [open]

Code visualization diagram for lectures/lesson8:546 (line 9)

This shows ONE way to implement the ADT. Note: The debugger breakpoint is on line 9. [download] [open]

Discussion Opportunity

Should element 0 be the top of the stack or should the top be at the end of the array?

Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package.

Carefully review the new methods (stackTester03 through stackTester05) and answer the questions below:

  1. What are these methods testing?

  2. Why is stackTest05 needed?

Implementation

To pass the current set of tests, implement the following methods with your group:

In ArrayStack:

  • push

Then, compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen multiple times. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 77 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 2"
git merge part3
Part 3: ArrayStack Peek
Code Tracing

Write the expected output of the following code on your exit ticket:

Stack stack = new ArrayStack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.peek());
Solution

The output will be:

d
d
d
Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package.

Carefully review the new methods (stackTester06 through stackTester08) and answer the questions below:

  1. What are these methods testing?

  2. Can you think of any additional tests that might be beneficial?

Implementation

To pass the current set of tests, implement the following methods with your group:

In ArrayStack:

  • peek

Then, compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen multiple times. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 78 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 3"
git merge part4
Part 4: ArrayStack Pop
Code Tracing

Draw a memory map for the code below on your exit ticket. Use the memory map from the last part as a starting point. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new ArrayStack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
Solution
Code visualization diagram for lectures/lesson8:726 (line 5)

Memory state at the breakpoint on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 6)

Memory state at the breakpoint on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 7)

Memory state at the breakpoint on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 8)

Memory state at the breakpoint on line 8. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 9)

Memory state at the breakpoint on line 9. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 10)

Memory state at the breakpoint on line 10. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 11)

Memory state at the breakpoint on line 11. [download] [open]

Code visualization diagram for lectures/lesson8:726 (line 12)

Memory state at the breakpoint on line 12. [download] [open]

Discussion Opportunity

Should we mark the elements null within the array when we remove from the stack?

Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package.

Carefully review the new methods (stackTester09 through stackTester17) and answer the questions below:

  1. What are these methods testing?

  2. Can you think of any other tests that might be beneficial to add?

Implementation

To pass the current set of tests, implement the following methods with your group:

In ArrayStack:

  • pop

Then, compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen multiple times. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 79 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 4"
git merge part5
Part 5: ArrayStack Additional Testing
Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package.

Carefully review the new methods (stackTester18 through stackTester20) and answer the questions below:

  1. What are these methods testing?

  2. What other tests might be beneficial?

Implementation

To pass the current set of tests, make sure you are throwing the appropriate exceptions within your ArrayStack implementations.

Then, compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen multiple times. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 80 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 5"
Part 6: LinkedStack Constructor
Code Tracing

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new LinkedStack();
Solution
Code visualization diagram for lectures/lesson8:860 (end of main)

Final captured memory state. [download] [open]

Implementation

Implement the following methods with your group:

In LinkedStack:

  • Constructor

Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package and answer the following questions:

  1. How do we reuse this code to test our LinkedStack implementation?

  2. How many methods should we expect to pass after implementing the LinkedStack constructor?

Compile and Run

Compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen for the first few tests and then an exception for the next method we need to implement. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 81 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 6"
Part 7: LinkedStack Push
Code Tracing 1

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new LinkedStack();
stack.push("a");
Solution
Code visualization diagram for lectures/lesson8:937 (line 5)

Memory state at the breakpoint on line 5. [download] [open]

Code Tracing 2

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new LinkedStack();
stack.push("a");
stack.push("b");
stack.push("c");
Solution
Code visualization diagram for lectures/lesson8:971 (line 5)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:971 (line 6)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:971 (line 7)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:971 (line 8)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 8. [download] [open]

Code Tracing 3

Draw a memory map for the code below on your exit ticket. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new LinkedStack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
Solution
Code visualization diagram for lectures/lesson8:1009 (line 5)

Memory state at the breakpoint on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:1009 (line 6)

Memory state at the breakpoint on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:1009 (line 7)

Memory state at the breakpoint on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:1009 (line 8)

Memory state at the breakpoint on line 8. [download] [open]

Code visualization diagram for lectures/lesson8:1009 (line 9)

Memory state at the breakpoint on line 9. [download] [open]

Discussion Opportunity

Should head be the top of the stack or should the end of the list be the top?

Implementation

Implement the following methods with your group:

In LinkedStack:

  • push

Inspecting the Tests

With your groups, inspect StackTester.java in the cs1302.test package and answer the following question:

  1. How many methods should we expect to pass after implementing the LinkedStack constructor?

Compile and Run

Compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen for the first few tests and then an exception for the next method we need to implement. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 82 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 7"
Part 8: LinkedStack Peek and Pop
Code Tracing

Draw a memory map for the code below on your exit ticket. Use the memory map from the last part as a starting point. Your diagram should include all variables (including instance variables) and objects created.

Stack stack = new LinkedStack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
Solution
Code visualization diagram for lectures/lesson8:1102 (line 5)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 5. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 6)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 6. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 7)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 7. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 8)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 8. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 9)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 9. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 10)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 10. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 11)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 11. [download] [open]

Code visualization diagram for lectures/lesson8:1102 (line 12)

This is ONE possible implementation of the ADT. Note: The debugger breakpoint is on line 12. [download] [open]

Implementation

Implement the following methods with your group:

In LinkedStack:

  • peek

  • pop

Compile and Run

If we've done everything correctly, all of the tests should pass for LinkedStack!

Compile and run the code using the provided script:

./compile_and_run.sh

You should see "PASS" printed on the screen for all tests. If you see "FAIL", don't panic, carefully read the error message and update your code. Once it compiles and you get all "PASS" messages from the tester, stage and commit your work to Git and then merge into the main branch with the following commands:

Listing 83 Commands to stage, commit, and merge
git add src
git commit -m "Finished part 8"
Part 9: toString

If we want to write a toString method to print the size of the stack and the top item, where should it go?