8. ADTs and Lists Lesson

Lesson Objectives

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

The Node Class

The Node Class

Show notes Show Solutions Show collapsed Full page Max width Print Reset

To see sample solutions, toggle "Show Solutions" above.

Sample solutions not included, because "Show Solutions" was not toggled 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

SVG PNG

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

public static void main(String[] args) {

    Node node = new Node("Billy");
    node.setItem("Susan");
    node.setNext(new Node("Sally"));
    node.getNext().setNext(new Node("Barry"));

    Node end = new Node("Supa Mike", node);
    Node n = node.getNext();
    n.setNext(new Node("Simon"));

    System.out.println(node.getItem());                     // Output 1
    System.out.println(node.getNext().getItem());           // Output 2
    System.out.println(end.getItem());                      // Output 3
    System.out.println(node.getNext().getNext().getItem()); // Output 4

} // 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.

|< < Prev Step 1 of 14: Driver.java:4 Next > >|

1234567891011121314

Listing 71 Code visualization for Code Tracing 1.

Node node = new Node("Billy");
node.setItem("Susan");
node.setNext(new Node("Sally"));
node.getNext().setNext(new Node("Barry"));

Node end = new Node("Supa Mike", node);
Node n = node.getNext();
n.setNext(new Node("Simon"));

System.out.println(node.getItem());                     // Output 1
System.out.println(node.getNext().getItem());           // Output 2
System.out.println(end.getItem());                      // Output 3
System.out.println(node.getNext().getNext().getItem()); // Output 4

System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

String lastItem = node.getNext().getNext().getNext().getItem();
System.out.println(lastItem);                           // Output 6 (reachable?)

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node node = new Node("Billy");
        node.setItem("Susan");
        node.setNext(new Node("Sally"));
        node.getNext().setNext(new Node("Barry"));

        Node end = new Node("Supa Mike", node);
        Node n = node.getNext();
        n.setNext(new Node("Simon"));

        System.out.println(node.getItem());                     // Output 1
        System.out.println(node.getNext().getItem());           // Output 2
        System.out.println(end.getItem());                      // Output 3
        System.out.println(node.getNext().getNext().getItem()); // Output 4

        System.out.println(node.getNext().getNext().getNext()); // Output 5 (what!?)

        String lastItem = node.getNext().getNext().getNext().getItem();
        System.out.println(lastItem);                           // Output 6 (reachable?)
    } // main

} // Driver

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

SVG PNG

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.

|< < Prev Step 1 of 4: Driver.java:4 Next > >|

1234

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("third", null); // line 4
        head = new Node("second", head);     // line 5
        head = new Node("first", head);      // line 6
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("third", null); // line 4
        head = new Node("second", head);     // line 5
        head = new Node("first", head);      // line 6
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("third", null); // line 4
        head = new Node("second", head);     // line 5
        head = new Node("first", head);      // line 6
    } // main

} // Driver

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("third", null); // line 4
        head = new Node("second", head);     // line 5
        head = new Node("first", head);      // line 6
    } // main

} // Driver

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.

|< < Prev Step 1 of 4: Driver.java:4 Next > >|

1234

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first", null);
        head.setNext(new Node("second", null));
        head.getNext().setNext(new Node("third", null));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first", null);
        head.setNext(new Node("second", null));
        head.getNext().setNext(new Node("third", null));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first", null);
        head.setNext(new Node("second", null));
        head.getNext().setNext(new Node("third", null));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first", null);
        head.setNext(new Node("second", null));
        head.getNext().setNext(new Node("third", null));
    } // main

} // Driver

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.

|< < Prev Step 1 of 7: Driver.java:4 Next > >|

1234567

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

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        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;
    } // main

} // Driver

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.

|< < Prev Step 1 of 2: Driver.java:6 Next > >|

12

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

public class Driver {

    public static void main(String[] args) {
        // Node head = new Node("first", new Node("second", new Node("third")));

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

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        // Node head = new Node("first", new Node("second", new Node("third")));

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

} // Driver

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.

|< < Prev Step 1 of 4: Driver.java:4 Next > >|

1234

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

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first");
        head.setNext(new Node("third"));
        head.setNext(new Node("second", head.getNext()));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first");
        head.setNext(new Node("third"));
        head.setNext(new Node("second", head.getNext()));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first");
        head.setNext(new Node("third"));
        head.setNext(new Node("second", head.getNext()));
    } // main

} // Driver

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

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("first");
        head.setNext(new Node("third"));
        head.setNext(new Node("second", head.getNext()));
    } // main

} // Driver

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

Code Tracing 2

SVG PNG

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

Node head = new Node("date");
head = new Node("cherry", head);
head = new Node("banana", head);
head = new Node("apple", head);

Node current = head;
while (current != null) {
   System.out.print(current.getItem() + " ");
   current = current.getNext();
} // while

Memory Maps

Note

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

|< < Prev Step 1 of 19: Driver.java:4 Next > >|

12345678910111213141516171819

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

> (no output yet)

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry date 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry date 

>_ Console Output

Driver.java

public class Driver {

    public static void main(String[] args) {
        Node head = new Node("date");
        head = new Node("cherry", head);
        head = new Node("banana", head);
        head = new Node("apple", head);

        Node current = head;
        while (current != null) {
           System.out.print(current.getItem() + " ");
           current = current.getNext();
        } // while
    } // main

} // Driver

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

apple banana cherry date 

>_ Console Output

Solution

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.

/**
 * Returns with a reference to the {@code Node} that can be
 * reached after traversing {@code numLinks}
 * many links starting at {@code node}.
 *
 * @param node the node where we begin the search.
 * @param numLinks the number of links to traverse.
 * @return node at {@code numLinks} links beyond {@code node}.
 */
public static Node getNode(Node node, int numLinks) {
    throw new UnsupportedOperationException("not yet implemented");
} // 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

Show notes Show Solutions Show collapsed Full page Max width Print Reset

To see sample solutions, toggle "Show Solutions" above.

Sample solutions not included, because "Show Solutions" was not toggled 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?

SVG PNG

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

• https://webwork.cs.uga.edu/~bjb211/adt-doc/cs1302/adt/Stack.html

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)

Stack UML

SVG PNG

Stack UML (Detailed)

SVG PNG

Unit Testing

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

public void unitTest() {

   Stack stack = new OracleStack();
   stack.push("a");
   stack.push("b");
   stack.push("c");

   // ...

} // 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)

SVG PNG

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

SVG PNG

Sample Solution

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

SVG PNG

Solution

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

SVG PNG

Solution

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

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

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

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

SVG PNG

Solution

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

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

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

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

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

SVG PNG

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

SVG PNG

Solution

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

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

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

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

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

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

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

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

SVG PNG

Solution

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

SVG PNG

Solution

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

SVG PNG

Solution

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

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

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

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

SVG PNG

Solution

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

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

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

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

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

SVG PNG

Solution

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

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

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

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

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

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

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

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?