CS101 Lab 6: Linked Lists

Purpose

This Lab

Download the program files for this lab and load them into a new project called Train.

[15 minutes] Program understanding: Without actually running the program, try to predict what it will output. Explain the program and its behavior to a partner. Find a different partner who will explain the code to you. After everyone understands the program, run it to see that it does what you predicted.

The concept of linking objects together and of linked lists:There are two very interesting and important new ideas here. First, a Car has a variable of type Car as a data member! To be precise, a Car has a (possibly null) reference to another Car. A null reference refers to no Car. You have already seen null references. If you declare a variable Car c; without assigning to it a new Car then the variable c contains a null reference. The new Car function creates a new Car object, which you would then store in c – which would now contain a non-null reference.

When one object contains a reference to another (even another object of the same type) we often say that the first object contains a link to the second. Note: there is no recursion here. It’s not that one Car contains another Car (it’s not a case of Russian Dolls). Rather, each car contains a possibly null reference to another Car.

Think of it like this: Each car has a hidden, unique numerical address: literally the place in the computers memory where the data for the object is stored. Each Car thus contains the address of another Car. If the address stored in a given Car is null, then the Car isn’t linked to another car. If the address is non-null (if it contains the address of another car) then you can think of the first Car as having a link, or connection, to another Car.

Of course, having a reference to an object means that you can operate on the object. If you write Car c = new Car(); then c is nothing other than a reference to a car. And if c.next (the link to a car contained in c) is not null, then you can treat c.next as being the equal of any other variable of type Car! You should now understand exactly what the program we’ve provided is doing: first it creates a linked list of cars, then it uses a loop, starting with the first element: as long as the current element is not null, the loop body prints its contents and then updates the current reference to be the currentCar’s next link. If the link is null, the loop has reached the end of the list, and the loop terminates.

[15 minutes] The concept of self-references and circularly-linked lists: It’s even possible for an object (e.g., a Car) to have a reference to itself. Within any non-static member function of a class, you have a variable that is a reference to the object being operated on. What is that reference called? Add code just before the for loop in your program to create a new Car c4  (that’s the first line of code) and then link it to itself (the second line of code).

What would happen if you were to start the for loop running on this self-referencing Car?  Think about it. Discuss it with your neighbor. Trace the program execution manually through all the details of loop execution. Go ahead and give it a try. Be sure you know where the little red button is in Eclipse to stop a runaway train!

[15 minutes] Making a circularly linked list: Add code at the bottom of the main routine to create train that looks in which c1 is linked to c2, c2 to c3, c3 to c4, and c4 back to c1. This is a circularly linked list. What will happen if you start the for loop running on c1? Give it a try (but be ready to terminate a runaway train).

(1) Now work with the TA’s to develop a for loop that knows how to traverse such a list, terminating immediately if given a null reference, and otherwise processing each Car in the list, and terminating upon returning to the beginning!

(2) Create a new Car object c5, and adjust the references stored in your Car objects in order to cause c5 to beinserted into the train in between c2 and c3. Print out the result.

SUBMISSION

Submit Test.java as usual.