CS1027b Computer Science Fundamentals II
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
and understand the linked list implementation of the Stack ADT.
- 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
toString. (Note that the String representation returned by toString should contain all the items in the stack.)
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.)
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.