CSC 212: Programming with Data Structures

Lab 4: Linked Lists

Due: Thursday, Feb. 18, 11:59pm

The goal of this lab is to give you experience with implementing data structures from scratch. If you were frustrated that there were parts of graphics that seemed mysterious, in this lab we'll be building everything from the ground up. There is not a lot of code, but make sure you understand everything you're writing, as well as the starter code (which we did in class).

You are welcome to start from the files from Class 7. Below are the same files, except CourseManager.java now contains all the code you'll add to main. So you can start with that version and comment out most of it to start. Then gradually add in the functionality as you write the methods (either way is fine).

To start, make a new lab4 package and add the following files:

Change the author field to be your name on each file. I would recommend having a piece of paper and pencil when you do this lab, to diagram what is happening with each of the functions.

Linked List Methods

  1. First, make sure you can run the program. It will create an empty linked list, add a few courses, and then get the number of courses. Note that right now our LinkedList class has only two methods (besides the constructor), both of which we are calling in main:

    • add(Object newData), which appends a new element to the end of the list

    • size(), which returns the number of elements in the list

    For the number of elements, note the difference from arrays:

    • Arrays: number of elements is .length, a FIELD

    • Lists: number of elements is .size(), a METHOD

    Note that arrays do not have any methods! When you run the program, it should say: 
    
Number of courses: 2
  2. Now implement the following method in your LinkedList class, which should return the element (i.e. data) at the specified index. (Hint: what should happen if the index is negative or outside the range of the list? You still need to return an object to fulfil the method contract... it might be a good time to use null.) 
    
public Object get(int index) {
    // TODO
}
    This method will have a similar structure to the add method, but there will be some differences. Now add the following code to your main (at the end of main) to test your method. 
    
// get a course at a specific index
System.out.println("Course 0: " + courses.get(0));
System.out.println("Course 1: " + courses.get(1));
System.out.println("Course 2: " + courses.get(2));
    What happens? If the printout looks strange, make sure you're not returning a Node object, but the actual data instead. You should write a method to accomplish this in the Node class.

  3. Next, we want to be able to add a course at a specific index in the list (think of this as insert). 
    
public void add(int index, Object newData) {
    // TODO
}
    For this method, there are a few cases. First, add the code below to your main to test your method. Before you write the method, what should happen? 
    
// add a course at a specific index
courses.add(1, "aerobics"); // feel free to change this
System.out.println("Course 0: " + courses.get(0));
System.out.println("Course 1: " + courses.get(1));
System.out.println("Course 2: " + courses.get(2));
System.out.println("Number of courses: " + courses.size());
    Think about how to update the references (you might also need a for loop to get to the right place). After that works, change the "1" index to "0", so that you're adding the element at the beginning of the list. What happens? If you get an error, how can you account for this special case?

    Test out your method in a range of scenarios by changing the index variable. Make sure to account for indices that are out of range. In that case, it might be nice to print out an error message or throw an exception. (Instead of receiving error messages all the time, you can give them out!)

  4. Further use your new add method to build up your own course schedule (you can order your courses by when they first appear in the week, or using any method you like). You can also add things that are not courses, like jobs, sports, music. In the end you should add 2-5 courses, in addition to the ones before.

    Here is some starter code to add to main to make sure this part is working: 

    
// add courses until you reach your schedule,
// in an order that makes sense for you
courses.add(3, "CSC 103");
courses.add(0, "yoga");
System.out.println("Number of courses: " + courses.size());
for (int i=0; i < courses.size(); i++) {
    System.out.println("Course " + i + ": " + courses.get(i));
}
    But now there might be courses in your list that you are not actually taking, we need to remove them!

  5. The last step is to write a remove method, that removes an element by its index (Python has a method that removes by value, but we're doing by index here). 
    
public void remove(int index) {
    // TODO
}
    For this method, make sure to diagram what is happening first on paper. Think about any special cases you'll have to consider, similar to the add method. You can add the code below to main to start: 
    
// remove courses you're not taking
courses.remove(3);
System.out.println("Number of courses: " + courses.size());
for (int i=0; i < courses.size(); i++) {
    System.out.println("Course " + i + ": " + courses.get(i));
}
    Try removing each course in turn to make sure it works (and out-of-range indices to make sure those don't do anything except print an error).

  6. (Optional) If you have time, investigate the built-in LinkedList class in Java. This part is to show you can you could be the one writing the Java System Library! Import this class and then change the way your list is initialized slightly. Then run your program again. Does it produce the same output? Are there lines you need to comment out to avoid errors? 
    
import java.util.LinkedList;

...

LinkedList courses = new LinkedList();

    If you do this part, make sure to change it back afterwards (and remove the import statement) so that you code is based on your own linked list class.

To Submit

Before submitting: make sure to update all your classes, methods, and fields with Javadocs (correct the author to your name, correct the version to the date, and document all your methods).
  • CourseManager.java with all changes

  • LinkedList.java with all changes

  • Node.java with all changes

  • typescript with a printout of everything that ran in main. If you don't submit a typescript showing the functionality of all the methods, I will assume your program doesn't work!

If you have more time, you may begin work on Homework 4.