Hi There!

I'm Dan Schlegel, an Assistant Professor in the Computer Science Department at SUNY Oswego

Lab 5 – Linked Lists

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:

  1. 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.
  2. Rename the file to DoublyLinkedList.java and update the contents of the file as appropriate.
  3. Modify your Node class to also have a reference to the previous node, called prev.
  4. Update the 2-argument constructor in Node to appropriately set the prev of next.
  5. Update your DoublyLinkedList class to correctly allow prepending/appending nodes, maintaining the prev and next references properly.
  6. 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:

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.

You will need to modify your iterator() method to return a ListIterator. Now modify your BrowserHistoryTest to do the following:

  1. Ask users to enter some website URLs, and to type ‘done’ when they have finished.
  2. 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.

When you’ve completed the lab, show it to your TA so that she may check you off.