AP Java Assignment 13: Linked Lists

Background

You've been using the ArrayList class from Java on the previous assignments. In this assignment, you will write your own list data structure.

Forming lists is something that all of us do. Before we go grocery shopping, we often write down a list of items that we want to purchase. When we plan out a day in the morning, we write down a list of things to do. During December, many children prepare Christmas wish lists. To plan a party, we list the people we want to invite. In short, arranging information in the form of lists is a ubiquitous part of our life, and we should learn to represent lists in Java. First we’ll learn to create lists and then move on to developing methods that modify lists.

Let’s say we want to make a list of planets. We need a class for each node in the list: 


class Planet
{
     String myName;
     Planet nextPlanet;
     Planet(String sName, Planet next){myName = sName; nextPlanet = next;}
}

When we form a list, we always start out with the empty list. In Java,
null
represents the empty list. From here, we can construct a longer list with the operation new. Here is a simple example:
new Planet("Mercury", null);

In this example, we constructed a list from the null list and the String "Mercury". The picture above shows one way we can imagine this list. The box for each Planet has two fields: myName and nextPlanet. In this specific example the myName field contains "Mercury" and the nextPlanet field contains null.

Once we have a list with one item on it, we can construct lists with two items by using new again:
new Planet("Venus", new Planet ("Mercury", null))
The middle row of the picture above shows how we should imagine the second list. It is also a box of two fields, but this time the nextPlanet field contains a box. Indeed, it contains the box from the top row of the same figure.

Finally, we construct a list with three items:
new Planet ("Earth", new Planet("Venus", new Planet("Mercury", null)))
The last row of the picture above illustrates the list with three items. Its nextPlanet field contains a box that contains a box again. So, as we create lists we put boxes into boxes into boxes, etc. While this may appear strange at first glance, it is just like a set of Chinese gift boxes or a set of nested drinking cups, which we sometimes get for our early birthdays. The only difference is that Java programs can nest lists much deeper than any artist could nest physical boxes.

Here is another way to imagine the list:

We can also make lists of numbers. We'll need a class for each node in the list. 

 
class ListNode
{
     int myNum;
     ListNode nextNumber;
     ListNode(int nNum, ListNode next){myNum = nNum; nextNumber= next;}
}

As before, null is the list without any items. Here is a list with 10 numbers: 

 
new ListNode (0,
  new ListNode (1, 
    new ListNode (2, 
      new ListNode (3, 
        new ListNode (4, 
          new ListNode (5, 
            new ListNode (6, 
              new ListNode (7, 
                new ListNode (8, 
                  new ListNode (9, null))))))))))

To build it requires 10 list constructions and one null list. Each node in the list can be one of two things:

There is a profound idea at heart of programming: The shape of the method is determined by the shape of the data it operates on. In this case, a ListNode is either

  1. null (empty)
  2. or it has an int myNum and a ListNode nextNumber
The "shape" of a method that takes a ListNode argument will reflect this. This leads us to a "fill-in-the-blank" outline for all methods that take a ListNode argument: 

/* Fill in the blank outline for methods with ListNode arguments
. . . . someMethod (ListNode node)
{
     if (node == null)
        . . .
     else
     {
        . . .node.myNum. . .
        . . .someMethod(node.nextNumber). . .
     }
}
Fill in the . . . . (blanks)*/

Learning to make a fill in the blank outline for member methods of a list class can GREATLY simplify the code writitng process. Let's say we want to write a method that displays all of the numbers in the list. 


void displayNodes (ListNode node)
{
     if (node == null)
        System.out.println("End");
     else
     {
        System.out.println(node.myNum);
        displayNodes(node.nextNumber);
     }
}

Only three things (shown in italics) need to be added to the outline. Easy!

Here's another one, let's say we wanted to count all the nodes in the list. 


int count (ListNode node)
{
     if (node == null)
        return 0;
     else
     {
        return 1
        + count(node.nextNumber);
     }
}

Exercises

    Create Java classes and lists that represent
  1. the list of all planets in our solar system;
  2. the following meal: steak, pommes-frites, beans, bread, water, juice, brie cheese, and ice-cream.
  3. the list of all computer operating systems you've ever heard of (e.g. Windows, Linux, etc.)

    Questions 4 - 6 use the following code:

     
class Number
{
     int myNum;
     Number nextNumber;
     Number(int nNum, Number next){myNum = nNum; nextNumber = next;}
} 

Number head = new Number(10, new Number(20, new Number(5, null)));
    What are the values of the following expressions?
  4. head.myNum
  5. head.nextNumber.myNum
  6. head.nextNumber.nextNumber.myNum
  7. Write the method countNodes, which takes one ListNode argument and returns the number of items in the list. Use the following code to test your method: 
    
            
            ListNode head = new ListNode(3,null);
            System.out.println(countNodes(head));
            head = null;
            System.out.println(countNodes(head));
            head = new ListNode (17,
                        new ListNode (-51, 
                            new ListNode (2,null)));
            System.out.println(countNodes(head));
  8. Write the method MaxNum, which takes a ListNode argument and returns the largest number in the list. (Hint: you should first write a function Max which returns the maximum of two ints.) Use the following code to test your method: 
    

              head = new ListNode (17,
                       new ListNode (-51, 
                         new ListNode (2,null)));
              System.out.println(MaxNum(head));
              head = null;
              System.out.println(MaxNum(head));
              head = new ListNode (-323,
                      new ListNode (-51, 
                       new ListNode (-2,
                           new ListNode (-1, null))));
             System.out.println(MaxNum(head));
  9. Write a class WishListNode that represents a node in a list of items on a Christmas Wish List.
  10. Write a fill in the blank outline for method that takes a WishListNode argument.
  11. Write the method isContained, which takes both a WishListNode argument and a String argument. IsContained determines whether or not the item occurs in the list. Use the following function prototype and function calls: 
    
           WishListNode head = new WishListNode("Barbie", 
                                    new WishListNode("G. I. Joe", null));
           System.out.println(isContained(head,"X-Box"));
           head = null;
           System.out.println(isContained(head,"X-Box"));
           head = new WishListNode("Barbie", 
                          new WishListNode("Bicycle",
                              new WishListNode("X-Box", null)));
           System.out.println(isContained(head,"X-Box"));
  12. Modify the WishListNode class you wrote for problem 9 so it each node contains the name and price of an item.
  13. Modify the fill in the blank function outline you wrote in problem 10 for your new class
  14. Write the method isCheap which takes a WishListNode argument and returns true if all the items in the less are less than $1 and false otherwise. Test your method on three different lists.
  15. Write the method totalCost which takes a WishListNode argument and returns the total price of all the items in the list. Test your method on three different lists.
  16. Write the method countItems which takes a WishListNode argument and returns the total number of items in the list. Test your method on three different lists.
  17. Write the method averagePrice which takes a WishListNode argument and returns the average price of all the items in the list. Test your method on three different lists.

You do not need to put an applet on your website for this assignment. Just email your answers to the questions above to mrsimon@lycos.com.

Acknowledgement: Most of this assignment was adapted from the book "How to Design Programs"