In this lab 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.
First, you will implement a doubly linked list. Do the following:
- Create a new Gradle project for the lab and create a copy of the LinkedList.java file which includes the iterator in your src folder.
- Rename the file to DoublyLinkedList.java and update the contents of the file as appropriate.
- 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).
One use case for doubly linked lists is in maintaining browser history. Create a new class called BrowserHistoryTest in which you will put just 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 |
In order to really use our list for browser history we will need to be able to move backward and forward in the list. The Iterator already allows us to move forward, but doesn’t contain methods to move 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. Now modify your BrowserHistoryTest to do the following:
- Ask users to enter some website URLs, 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 |
When you’ve completed the lab, show it to your TA so that she may check you off.