Background
This lab will introduce you to linked lists using the LinkedList class from the Java Collections framework. Recall that a linked list is made up of nodes, each of which stores one element. The nodes may be linked together into chains. A doubly linked list has pointers from each node to its immediate neighbors to the left and right. However, in LinkedList these details are hidden from the programmer.
Take a look at ListLab.java, and download it to your lab folder. You will modify this file during the lab, adding code where the comments say to FILL IN. The text below gives more detail.
Exercises
Compile and run the code you downloaded. The modifications you will make are divided into three parts: list access, list modification, and list processing.
In the first part (list access), you will practice how to access the values stored in a list. Examine the diagram below. It shows how a list is stored in memory, although many of these details are hidden by the LinkedList implementation. Nevertheless you may refer to this diagram as you complete the assigned tasks. Keep in mind that a ListIterator keeps track of a location between the elements in the diagram below.
The code in ListLab.java is heavily commented. You will notice places where comments say FILL IN. You should add the appropriate code at these points to make the program match the comments.
In the second part (list modification), you will practice changing the elements of a list. At the beginning of this part, you will have the chance to see the practical differences between a reference copy, a shallow copy, and a deep copy. (Note that shallow copies are dangerous because they can easily create inconsistent data structures. Java attempts to protect you from such situations by detecting them and generating an exception. You will see an example of this when you run the program.)
Before performing any modifications, the program makes one of each kind of copy. Then it changes some of the elements in each. At the end, the three lists are printed. The reference copy reflects all the changes made to list1, since it is really the same list. On the other hand, the deep copy includes none of the modifications made to list1 after the copy, because it is actually a separate structure in memory. The shallow copy refuses to cooperate because its status is undefined once changes are made to the original backing list. The rest of part two focuses on additional modifications that can be made to a list through an iterator.
In the third part, you will practice working with lists as a whole. In most cases, you can do the same sorts of things with lists as with arrays. To illustrate this, several examples are shown. The first sums the list element by element, and the second computes the minimum of all the elements (and the index where that minimum appears). Note the format of the loops used in each case; the first uses a for-each loop while the second uses an iterator. Both are standard forms for looping through all the elements of a list. Which one you choose will depend on what you wish to do. The iterator form, while slightly more complicated, allows you to more easily modify the list or recover an index.
As an exercise, you are asked to write several more loops. The first few will be closely analogous to the examples, while the last few will require a little more thought and planning. (Hint: for some, you may need to move the iterator forward and/or backward more than once per loop iteration.)
To Submit
- ListLab.java with your changes
- typescript showing the output of the final program