# CS1027b Computer Science Fundamentals II

## Lab 5

### General lab instructions to help labs run smoothly

• Read through the lab instructions before coming to the lab.
• Do the pre-lab preparation.

### Overview and preparation

Upon completion of this lab, you should be able to understand how nodes work in a linked list, using the `LinearNode` class and understand the linked list implementation of the Stack ADT.

Pre-lab Preparation:

• Review lecture notes on linked lists: Make sure you understand how the class `LinearNode` represents a node of a linked list.
• Review lecture notes on implementing stacks using linked lists: Make sure you understand what a stack looks like, when implemented as a linked list.

### Exercise 1: Building a Linked List, revisited

• Download the file BuildLinkedList.java from the course webpage. It contains a main method that builds a linked list of integers from 1 to 10. In order to run this program, you will also need to download LinearNode.java.
• Run the program and see what is printed out as the contents of the linked list.
• What would happen if you changed the first for loop to `for (int i = 1; i <= 10; i++) `, and why? If you are not sure, try making the change and see what happens.
• The code that traverses the linked list and displays each data item works specifically for (and only for) a linked list with exactly ten nodes. In order to make the code more general, we can use the fact that the last node always points to null. We can use a while loop that stops looping when the next field of the current node is null. Make this change to your code: change the for loop to a while loop that will work for any linked list. Run your BuildLinkedList program to make sure it still displays the contents of the linked list correctly.

### Exercise 2: Completing the LinkedStack class

• Download LinkedStack.java and fill in the missing code in the methods `isEmpty`, `size`, and `toString`. (Note that the String representation returned by toString should contain all the items in the stack.) The `isEmpty` and `size` methods are trivial; model your `toString` method on the code you wrote in Exercise 1, using a loop to traverse the linked list. (The main difference is that you are forming a string rather than printing each data item.)
• Download from the course webpage all the files you will need in order to use LinkedStack.java
• Download the code in the file TestLinkedStack.txt and cut and paste this at the end of your `LinkedStack` class as a test harness (as explained in Lab 2). Run this as the `main` method, to show that your new methods in `LinkedStack` work correctly.