GNU Java Training Wheels 2.0: Tutorial 14 Linked lists

Dr Seuss’ story “Yertle the Turtle” describes how a turtle called Yertle sits at the top of a pile of other turtles. In this example, the pile of turtles is represented by a linked list of Turtle objects, with the down property serving to connect one Turtle object to another. If a Turtle object has a non-null down property, then this represents the fact that it is sitting on top of another turtle. The last turtle in the linked list is the turtle that is at the bottom of the pile, which has a null value for its down property. Note that you cannot use the superfor construct for iterating through a linked list. In this case the for construct is the most sensible.

class Turtle
begin

    private property String     name;   // Turtle's name
    private property int        age;    // Turtle's age in years
    private property double     weight; // Turtle's weight in kg

    // NOTE: this property allows for linked lists
    property Turtle down;

    constructor Turtle(String aName, int anAge, double aWeight)
    begin
        name   = aName;
        age    = anAge;
        weight = aWeight;
    end

    /** Getter method for name property */
    method String getName()
    begin
        return name;
    end

    /** Useful method for debugging */
    public method String toString()
    begin
        return name;
    end
end

class TurtleTest
begin
    beginMain

        var Turtle yertle = new Turtle("Yertle", 103, 20);
        var Turtle zippy  = new Turtle("Zippy",  102, 30);
        var Turtle bungle = new Turtle("Bungle", 101, 40);

        // *** see later
        yertle.down = zippy;
        zippy.down = bungle;
        bungle.down  = null; // NOTE: not needed as bungle.down is null by default

        var int totalWeight = 0;
        // NOTE: demonstrates how to iterate through a linked list:
        for (var Turtle current = yertle; current != null; current=current.down)
        begin
            totalWeight = totalWeight + current.getWeight();
        end
        System.out.println("The total weight is " + totalWeight);
    endMain
end

The code in the main function after the *** sets down the following relationships between the three Turtle objects (Yertle, Bungle and Zippy). The following diagram shows the relationship between the different turtles. When you traverse the list of turtles you must always start at the top turtle (known as the head of the linked list). If you give a different value for the top turtle, your code will think that the given turtle is the one at the top of the pile and you will get the wrong result.

Question 4.14.2: Move the code for calculating the total weight of the turtles from the main function to a function called function void printTotalWeight(Turtle bottom) in the Turtle class that prints out the total weight of the turtles. Then call that function from the main function to get the same result as before. Note that that if printTotalWeight was a method then calling that method using null (representing an empty list) like so: null.printTotalWeight() would be an error, whereas Turtle.printTotalWeight(null) wouldn’t be and therefore is better. This is one example of how methods and functions differ.

Question 4.14.3: Revision question for getters. By copying the pattern established by the getName method, add two getter methods to the Turtle class: getAge which returns the current turtle’s age and getWeight which returns the current turtle’s weight. Then call these methods on the Yertle object in the main function. Note that the toString method would be more appropriate as it handles nulls better but you know that the yertle reference is not null so you know it is safe to call the getAge and getWeight methods on the yertle reference.

Question 4.14.4: Write a function Turtle findBottomTurtle(Turtle top) that returns the Turtle object that is at the top of the pile, and returns null if there isn’t one.

Question 4.14.5: Then call this function from the main function using System.out.println() and the top turtle Yertle.

Question 4.14.6: Write a function Turtle findOldestTurtle(Turtle top) that returns the oldest turtle or null if there isn’t one.

Question 4.14.7:Then call this function from the main function using System.out.println() and the top turtle Yertle.

Question 4.14.8: Write a function Turtle findHeaviestTurtle(Turtle top) returns the heaviest turtle, or null if there isn’t one.

Question 4.14.9: Then call this function from the main function using System.out.println() and the top turtle Yertle.

Question 4.14.10: Write a function sayPile(Turtle top) that prints the names of the turtles in the pile starting from the top turtle and finishing at the bottom turtle. Then call this function from the main function.

Question 4.14.11: Under what circumstances would it be okay to change the visibility of the down property to private, like the name, age and weight properties?

Question 4.14.12: Add an extra parameter to the constructor which is a reference the to the turtle on below the current one. Then remove all occurrences of the down property from the main function. Note that you will need to reverse the order that the turtles are created so the bottom turtle is constructed first and so on. The advantage of this is that it enables you to change the visibility of the down property to private.

4.14 Tutorial 14 Linked lists