Computer Science II -- Week 9
Introduction
This week we will look at how container classes in Java work, and at linked lists in particular.
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
Quiz
Data Structures
Container Classes
Review of Programming Assignment 3
Programming Assignment 3 Design Due
Linked Lists
Java Classes
Algorithms Available
Linked List Exercise
Vectors
Exam Review
Next Week
This will be a short quiz asking you to design an inheritance hierarchy based on a problem description. To fully model the problem, you will need to use both inheritance and interfaces. You may not use your book, notes, or the student manual. This is an individual activity.
A data structure is simply a way of holding more than one element of data. For example, an array is an example of a simple data structure. Every data structure has certain characteristics; for example, an array has a fixed size that must be declared when the array is created.
Arrays are not always the right data structure to use for solving a problem. If you do not know how many elements you might need, then you cannot easily use an array. We would rather use a data structure that can have an unlimited number of elements (called a dynamic data structure).
Arrays are also not very efficient. Consider the problem of finding one element in an array. We might have to look at every element in the array before either finding the element or deciding that it is not in the array. There are data structures that are more efficient for searching. Also consider the problem of inserting a new element in the middle of an array. Assuming that our array has enough space for a new element, we would still have to copy all the higher numbered elements up one space to make room. This is a lot of copying for large arrays! There are data structures that are more efficient for inserting or removing elements from the middle.
Java uses the phrase "container classes" or "collections" to talk about data structures. Consider trying to design an interface in Java for a container class. For example, let's say we want a container class that can hold as many Strings as we want. We might design an interface like this:
interface StringContainer
{
public void addString (String item);
public void removeString (String item);
public String getString (String item);
public boolean isStringPresent (String item);
}
Now think about designing a container class that can hold Students. We might end up with an interface that is identical to our StringContainer, except that everywhere we had String, we would have Student. This is clearly a duplication of code and effort.
Java allows us to reuse one container class for holding multiple types of items by taking advantage of the fact that all classes in Java are inherited from Object. Using polymorphism, we can use a reference to the class Object to point to an instance of any other class. So we could redesign our container class like this:
interface Container
{
public void add (Object item);
public void remove (Object item);
public Object get (Object item);
public boolean isPresent (Object item);
}
We have one interface that can now hold any type of object. This is how container classes in Java work, so you will see Objects being passed and returned by them.
What do you do with the Object once you get it back? Let's say that we were using our Container to hold Strings. We might create a Container and put a String into it like this:
Container c = new Container ();
c.add ("Hello");
c.add ("Goodbye");
Later, we might want to get a String back out of the Container, like this:
Object obj = c.get ("Hello");
But we cannot do much with an Object; we cannot call any of the String methods using a reference to Object. What we really need is a reference to String. We know that we put a reference to String into the container, so we can tell Java to convert the reference to Object the container gives us into a reference to a String.
String s = (String) c.get ("Hello");
This tells Java to treat the reference to an Object as a reference to a String. This is called "casting" the reference to an Object to a reference to a String. This only works if the reference to an Object really does point to a String instance. If it does not, then you will get an exception.
This idea of storing references to Objects and then casting them back to their real type will be used in all Java container classes.
Review of Programming Assignment 3
You will form into pairs and exchange programming assignment 3 designs. You must turn in a peer review form for the design you review.
Programming Assignment 3 Design Due
You must turn in your programming assignment 3 design today for full credit. Turning it in later than tonight will result in a 10% penalty.
A linked list is a data structure, which means it can hold other objects. The objects that are being held in a linked list are called nodes. Each node contains some data, and it also contains a reference to the next node in the list. Linked lists can hold an unlimited number of elements.
(Draw simple linked list diagram)
This is a singly linked list, because each node contains one link to the next node.
(Show inserting in the middle of the list, and removing from the middle of the list, and compare with inserting into the middle of an array)
Consider what the insert code would look like.
void insert (node where, Object data)
{
node newNode = new node (data);newNode.next = where.next;
where.next = newNode;
}
Now consider what the remove code would look like:
void remove (node whichOne)
{
node previous = ???;previous.next = whichOne.next;
}
How do we locate the previous node?
This can be made more efficient by creating a doubly linked list. Each node will contain a reference to both the next node and the previous node. So our remove would look like:
void remove (node whichOne)
{
node previous = whichOne.prev;
node next = whichOne.next;previous.next = next;
next.previous = previous;
}
This is more efficient, because we do not have to search for the previous node. We have a direct reference to it. But does this work for removing at the beginning and the end of the list? If not, how would we fix it?
One way is to add an if statement to the remove method. But we would prefer to keep our code as simple as possible. So we can make the linked list concept a little more complicated, and keep our code simpler (this is a common theme in computer science...if you spend more time working on the solution to a problem, often your code becomes simpler).
We can create a circular linked list. A circular linked list is one where the last node has a reference to the first node, and (if it is a doubly linked list) the first node has a reference to the last node. This will allow our remove code to work without being changed.
Java has many classes for using data structures. One of these classes is the Arrays class. This class contains helpful methods you can use when you are using arrays. For example, you can use the Arrays class to compare two arrays using the equals method.
int [] a1 = new int [5];
int [] a2 = new int [5];...put some values into both arrays...
if (Arrays.equal (a1, a2))
System.out.println ("arrays have same contents");
There are also methods for sorting the array and for filling all the elements of the array with the same value. Look at the Java API documentation for details on all the methods.
Collection and Collections
Java has an interface named Collection. This provides methods that all data structures in Java can implement. This provides some consistency between data structures.
The Collections class is a set of utility methods for dealing with Collections and Lists. For example, Collections allows you to find the min element in a Collection, and allows you to sort a List. For full details on everything you can do with Collections, look at the Java API documentation.
List and LinkedList
The List interface in Java specifies the methods that an implementation of a linked list must provide. The List interface extends the Collection interface, so it is a type of Collection.
The LinkedList class is one implementation of the List interface. This is the one that behaves like the linked lists we have been discussing in class. There are methods for adding data to the list, for seeing if data is in the list, for getting the number of items in the list, etc.
For example, to add items to a LinkedList:
LinkedList l = new LinkedList ();
l.add ("Hello");
l.add ("Bye");
The add method adds the new item to the end of the list. You can also add items at some other point in the list by passing in the index of where to put the new item:
l.add (0, "Hello");
l.add (0, "Bye");
Passing in 0 adds the items to the beginning of the list.
A common task in any data structure is doing something with every element in the data structure. In the LinkedList class we can do this by using the iterator () method. iterator () returns a reference to an Iterator instance. The Iterator has methods to move through the list, both forward and backward. For example:
LinkedList l = new LinkedList ();
...add Strings to the list...
Iterator iter = l.iterator ();
while (iter.hasNext ())
{
String item = (String) iter.next ();System.out.println (item);
}
This is a very common loop for doing something with all the elements of a list.
There are many more methods available on the LinkedList class. Look at the Java API documentation for full details.
The Collections class has several common algorithms implemented that you can use. We'll look at a couple of them in more detail here.
A common task is sorting a collection (since the List is a type of Collection, this means we can sort Lists, too). For example:
LinkedList l = new LinkedList ();
...add some items to the list...
Collections.sort (l);
This will sort the list. Seems easy, right? There is actually a little more that you may need to do. In order to sort the list, the Collections class must compare two items in the list to see if they are equal to each other, or if one is less than the other. This requires that all items in the list implement the Comparable interface.
The Comparable interface has only one method: compareTo. This method is supposed to return a negative number if the object is less than the object passed into it, zero if they are equal, and a positive number if the object is greater than the object passed into it.
The String class already implements the Comparable interface, so you can sort a list of Strings without doing any additional work. If you have a list of a class you wrote (such as Instrument), you would need to implement the Comparable interface and write the compareTo method, to be able to sort a list of Instruments.
The compareTo method is similar to the equals method in that the parameter passed in is an Object. You must make certain that the Object passed in is really what you are expecting, and then compare the contents of the objects to see if they are less than, equal to, or greater than.
Using the sort method sorts the collection in order from smallest element to largest element. What if you want some other way of sorting?
There is another version of the sort method that allows you to specify a way of comparing items that is different from the results of the compareTo method. You do this by writing a class that implements the Comparator interface. This allows you to use a different comparison method than what is natural for the objects being sorted. For example, instead of sorting Strings in alphabetical order, you could sort them according to the length of the String.
If you want to sort something in reverse order (largest to smallest), you can use the Collections class to give you a built in Comparator that will do the job.
LinkedList l = new LinkedList ();
...add some items to the list...
Collections.sort (l, Collections.reverseOrder ());
The reverseOrder () method of Collections gives you a Comparator that will order items from largest to smallest, exactly the reverse of the natural ordering of the items.
Another algorithm available in the Collections class is the shuffle algorithm. This randomly reorders the items in the list. This might be a useful method if you were writing a card playing program.
Another algorithm is the reverse algorithm. This reverses the order of items in the list; the last item becomes the first item, the first item becomes the last item, and so on.
Again, look at the Java API documentation for the full details of other algorithms available.
This is a group exercise. I will pass out a problem description, and you will write an algorithm to solve the problem. Your algorithm must use a linked list.
The LinkedList class is useful when we need the benefits of being able to insert into the middle efficiently. But if we do not need that benefit, then the LinkedList class is less efficient at randomly accessing items. An array is very efficient at randomly accessing items, but it has a fixed size.
The solution is the Vector class. The Vector class holds its data in an array, so it can randomly access items efficiently, but it can also allocate a larger array if it runs out of room so it can hold an unlimited number of items.
The Vector class implements the List interface, so any of the algorithms we talked about for lists will also work with Vectors. In fact, using Vectors will seem quite similar to using Lists.
Vector v = new Vector ();
v.add ("Hello");
v.add ("Bye");
v.add (0, "See you");
These are the same add methods we used with a List. To see if a Vector contains a specific item:
if (v.contains ("Okay"))
System.out.println ("Found it!");
Additionally, the Vector allows us to access any item in the Vector efficiently using the elementAt method:
String s = v.elementAt (5);
where 5 is the index of the item we want. If 5 is not a valid index in the Vector, we will get an exception. Usually elementAt is used as part of a loop over all the elements in the Vector, very similar to looping over all the elements in an array:
for (i = 0; i < v.size (); i++)
{
System.out.println (v.elementAt (i));
}
How many other ways can we do something with every element in a Vector? Well, Vector implements the List interface, so we can also use the iterator method on a Vector just like we used it on a LinkedList.
Vector also provides us with an elements method. The elements method returns an Enumeration reference. We would use Enumeration like this:
Vector v = new Vector ();
...put items in vector...
Enumeration e = v.elements ();
while (e.hasMoreElements ())
{
String s = (String) e.nextElement ();System.out.println (s);
}
If this looks very similar to using an Iterator, it is. The Enumeration interface was what was originally in Java. In later versions the Java programmers thought the method names were too long, so they created the Iterator interface so they wouldn't have to type as much. The preferred interface to use is the Iterator interface.
There are also other ways to do something with every element of a Vector. However, we only need one way that works, so we will generally use the Iterator interface since this is available in every class that implements Collection.
We will review for the midterm in class by going over the list of topics and types of questions that may be on the midterm.
Next week will be the second midterm. There will be no lecture.
Remember that your completed design for programming assignment 3 is due next week.