First, create a lab09 directory:
$ cd cs190m $ mkdir lab09 $ cd lab09
Then, download Lab09.java and SafeLinkedList.java into the folder you just created.
As you learned in class, linked lists usually have several fundamental operations; we'll be implementing some of them today in a linked list that stores objects. The implementation details are explained below:
As you know, linked lists consist of nodes which typically have pointers to other nodes, as well as an element of some type. One interesting design decision that dictates how your code will look is whether or not an empty linked list should use a "dummy" head node that doesn't actually store an element rather than a null node. In our implementation, we'll be using a dummy node as the head, which will hopefully result in much cleaner code, notably less need for checking whether or not nodes are null (hint: always examine the "current" item with node.next.element rather than node.element).
The three operations you'll be implementing are add(), remove(), and get(). Some other operations are provided to you, which you can review in the skeleton code. A Node class is also provided for you at the bottom of the file as an inner class. You should use this for storing references to next nodes and elements.
The add() method is used to add a new item at a certain index. The index is treated similar to array indices; therefore, if the index is 0, then it adds the element to the beginning of the list. Remember that since the first Node object is a dummy node, the "beginning" of the list is actually head.next. If the index is the size of the list, then it adds the element to the end of the list. If the index is larger than the size of the list, then a run-time exception is thrown (which is provided in the skeleton code). This method must also increment the size variable when adding an element.
The remove() method removes an element from a list. If the element doesn't exist in the list, then nothing happens. Otherwise, it removes the node containing the element and decrements the size.
Note: This is not the same as a "remove at" method, which removes the item at an index. This searches for an item in the list and then removes it if it finds it.
The get() method retrieves an item at a given index. If the index specified is outside of the list dimension, then an error is thrown.
Making this list thread-safe is a relatively straightforward task. Consider the bank account solution in Section 6.5 in your book. In this case, the reader methods and writer methods can never be executed in parallel; however, multiple readers can be executed in parallel. There are several reader methods provided for you. You should identify them and write similar code such that multiple readers can be executed while no writer is executed, and only one writer can be executed at a time. It may be easier to write the synchronization code in different methods and simply call them to avoid code duplication.
The Lab09.java file can be used for testing your program. The main method creates a list of integers that tests your linked list. You should read the file to see if you get the expected output. You can test your program by compiling and running the command java Lab09. You can see that the test does not cover threaded execution; if you want to test your thread-safety implementation, you should write your own test file. The test case should print something like this:
0: 0 0: 1 1: 0 0: 1
To turn in your lab:
$ cd ~/cs190m/lab09 $ turnin -v -c cs190m -p lab09 *.java
Many of you will probably run across problems while programming at some point during a lab. If that's the case, here are the resources you should use, in order:
Lab created by: Daniel Tang