In this exercise you will explore the concepts of linked lists by making modifications to the linked list code we wrote in class, and using it in a sample application. The program is designed to be completed over the course of three class periods. Feel free to use room 444 to meet to discuss and collaborate. You may work in pairs, as long as both team members contributes equally. At the end of each class hour, submit your progress on Blackboard in the appropriate Doubly Linked List item. Completion of this exercise will count as part of your Exam 2 score.
Day 1 – 11/5
First, you will implement a doubly linked list. Do the following:
- Create a new Gradle project for the project and create a copy of the LinkedList.java file which includes the iterator into your src folder.
- Rename the file to DoublyLinkedList.java and update the contents of the file as appropriate to match the new name.
- Modify your Node class to also have a reference to the previous node, called prev.
- Update the 2-argument constructor in Node to appropriately set the prev of next.
- Update your DoublyLinkedList class to correctly allow prepending/appending nodes, maintaining the prev and next references properly.
- Change your toString method to output the list both forward and backward (starting at the tail and using the prev links to go backward).
- Test your doubly linked list – write tests which examine whether all of the edge cases work.
- Submit your code on Blackboard.
Day 2 – 11/7
If you were unable to complete the Doubly Linked List from last class, work with a classmate to bring your code up to snuff before continuing. Be sure you understand all parts of the code.
The current version of your code has an iterator implementation. This allows moving forward through the list, but does not allow moving backward.
Alter the LLIterator to implement ListIterator instead of Iterator. Study the javadoc to see what you will need to implement. You don’t need to implement any of the optional operations (add, remove, set). For those you can use the below code.
|
1 2 3 4 5 6 7 8 9 10 11 |
public void add(U u) throws UnsupportedOperationException{ throw new UnsupportedOperationException(); } public void remove() throws UnsupportedOperationException{ throw new UnsupportedOperationException(); } public void set(U u) throws UnsupportedOperationException{ throw new UnsupportedOperationException(); } |
You will need to modify your iterator() method to return a ListIterator. Test your ListIterator with some dummy values to ensure it’s working properly. Submit your code on Blackboard.
Day 3 – 11/9
If you were unable to complete the ListIterator from last class, work with a classmate to bring your code up to snuff before continuing. Be sure you understand all parts of the code.
One use case for doubly linked lists is in maintaining browser history. Create a new class called Website which will store the name and address of a website. Add an appropriate constructor and appropriate getters. Add a toString method which, for now, just prints the web address.
Now, create a new class called BrowserHistory in which you will put only a main method. In that method, create a new doubly linked list, add some (3+) websites that you frequent, and print out the list. Here’s some sample output:
|
1 2 3 |
Doubly Linked List with 4 items Forward: google.com stackoverflow.com github.com Backward: github.com stackoverflow.com google.com |
Now modify your BrowserHistory class to do the following:
- Ask user to enter some website URLs and names, and to type ‘done’ when they have finished.
- Enter a command loop with the legal options being ‘next’ and ‘previous’ to move around the list. When the user types a command print out the visited item. If there is no item, or the command is invalid, be sure to print reasonable error messages. The user may type ‘quit’ to exit the program.
Below is a sample interaction. You should try it with some recent URLs you have visited.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
$ java BrowserHistoryTest Enter some website URLs, type 'done' when you've finished. google.com stackoverflow.com github.com done Type 'next' to print out the next url, 'prev' to print out the previous one, 'quit' to quit. next Now visiting: google.com next Now visiting: stackoverflow.com next Now visiting: github.com previous Now visiting: stackoverflow.com previous Now visiting: google.com previous No previous item. next Now visiting: stackoverflow.com next Now visiting: github.com next No next item. quit |
Modify the toString method of your Website class to print the name of the website as well, and test your code thoroughly.
When you’ve completed the exercise, submit the project on Blackboard.