Goals and Background
This lab consists of some problems for you to practice programming with the Java LinkedList class, and in particular get practice programming with iterators. You can only get the lab points for your solution to an exercise if you write code so that it takes no more than O(n) to traverse a list. As we discussed in class, using the
LinkedList get method for traversal takes O(n2) to traverse a list.
You will probably have to refer to the Java API documentation for LinkedList and ListIterator to complete the problems. We have provided links directly to those pages below.
Advanced preparation
There is more code to write in this lab than most, so you may want to spend some time before the lab preparing handwritten solutions to the problems, especially the last problem.
Reading and reference material
Java API LinkedList documentation
Java API ListIterator documentation
Horstmann, Section 15.2 Using Linked Lists
2/26 CSCI455 Lecture on Java LinkedList class
Exercise 1 (1 checkoff point)
Write a static method printAlt that prints every other element in a list, starting with the first one. For example
list
printAlt(list) output
2
4
7
2
7
2
4
2
2
4
7
9
3
2
2
7
3
2
4
7
9
3
2
7
3
We have provided a test driver for your method that tests it on several hard-coded cases. The test driver source file, PrintAltTester.java, contains the stub for the printAlt method.
Exercise 2 (1 checkoff point)
Write a static method after7 that removes all the values after the last 7 in a list. Note: this problem is adapted from an array problem on the codingbat.com website. Here are some examples
list
list after
call to after7(list)
2
4
7
2
4
7
2
4
2
4
2
4
7
9
3 2
2
4
7
247973712
2479737
7
5
4
7
We have provided a test driver for your method that tests it on several hard-coded cases, and compares the actual results with the expected results. The test driver source file, After7Tester.java, contains the stub for the
bytes.usc.edu/cs455/curr/labs/lab8/lab8.html 1/2
Lab 8 CS 455
after7 method.
Hint: you can initialize an iterator positioned at the end of the list (i.e., after the last element) as follows:
ListIterator<Integer iter = list.listIterator(list.size());
Exercise 3 (1 checkoff point)
Write a static method hasPeak that returns true if its list argument has a single peak, and false otherwise. This means that the sequence of values consists wholly of an increasing part followed by a decreasing part. You may assume no two consecutive values in the array are the same (i.e., no flat areas).
list
hasPeak(list)
2
4
7
false
2
7
4
true
7
4
2
false
2
4
false
2
false
2
4
7
9
3 2
true
2
4
7
9
7 3
7 1
false
7
5
4
false
2
4
2
3
false
5
4
3
false
We have provided a test driver for your method that tests it on several hard-coded cases, and compares the actual results with the expected results. The test driver source file, PeakTester.java, contains the stub for the hasPeak method.
Checkoff for DEN students
Make sure you put your name and NetID in all the files you submit. No README required for this lab. When you click the Submit button, it will be looking for and compiling (for source code) the files
PrintAltTester.java, After7Tester.java, and PeakTester.java.
bytes.usc.edu/cs455/curr/labs/lab8/lab8.html 2/2
