Project 1 linked list

Introduction - The Problem
In this project your program demonstrates two applications of the linked list based sequence ADT. The first stores Rectangle objects, the second stores String objects. Your program must test all the sequence operations at least in one of the two data structures created. The rectangle objects are created and added to the list with random field values, the string objects (names) you choose directly or read them from a file you create for input, or you may generate names randomly, too. Must document your choice.

 Design, Implementation
The implementation of the data structure ADT will be based on two user defined classes: Node and LinkedSequence, both generic. A Rectangle class must

also be added to project, since in one of the applications the stored data are Rectangle objects. The other application utilizes the String class from the Java library. For testing purposes two more classes will be needed: TestNode to test the Node class methods, and LinkedApplications to use the data structure. 

1. The Rectangle class (not generic) has two fields named width and length, both of type int. You may use package access to the fields. The class has 

•      a constructor taking two parameters to initialize the fields

•      a toString( ) method which returns a String message that specifies the data field values

•      an equals( ) method which returns true if each of the corresponding field values are equal in two given rectangles

2. Node
This class is generic, yet as for a template, you are advised to study the IntNodeClass specifications (pp 208-211, Figure 4.11 in Ch 4) in the book, as well as the implementations in the previous sections and on pages 212-214. As for a generic Node class there are some hints in the book on pages 283-285 (Sec 5.4 in Ch 5).  

Our Node class is similar but not identical to the template. We may discard or modify some methods and we may include new methods which are practical in our applications.

 

 Partial class documentation:

 

•      Fields: as usual, but with the generic type parameter

•      Constructor: takes two parameters to initialize the fields

 

Instance methods
•      addNodeAfter() as in the book, but not void, returns the link it creates.

•      removeNodeAfter() as in the book, but returns the link it creates (that is, the node after the removed element)

•      toString() creates and returns a string message which reveals the stored value (data) but not the link (this method is not recursive, it overrides Object toString)

•      toString(int dum) creates and returns a string message which reveals the stored value (data) and the links (recursive). This method overloads toString, this is why a dummy parameter is needed. The method is applicable for shorter lists only, needed for testing purposes and not supposed to be in a reusable class. See HW 4 discussing both the recursive and non-recursive versions of toString().

 

Static methods
•      listCopy() as in the book, but, since our addNodeAfter( ) returns the link, you should assign the return value directly to copyTail . That is, combine the two copyTail statements of the while loop in one statement, see the slide from the lecture.

•      listPosition() as in the book

•      listLength()as in the book

•      getTail() This is a new method! Starting at a node given as

the parameter, the method iterates through the list until arrives at the tail, then it returns the tail. The iteration is the same as in the listCopy method. This method helps to maintain the tail reference, and combined with the listCopy method, the listCopyWithTail becomes superfluous

•      listCopyWithTail() omitted

•      listPart()  omitted

•      listSearch()omitted

3.  LinkedSequence 
This class is also implemented as a generic class. The specification of a nongeneric DoubleLinkedSeq class is fairly well detailed in your reading, pp 232 – 238, it helps to design the generic class. It is a marked difference that the book does not apply a dummy node. Also, the LinkedBag implementation in the book can be helpful, but the analogy is rather weak.

 

        Fields

•      The field manyNodes is optional. 

It can be convenient to have direct access to the size of the sequence, but this variable needs careful update in each method that manipulates the size, and this can be a source of errors. For instance, the removeNodeAfter() method changes the size most of the time, but there is no change when tail is the reference. The listLength() method of the Node class makes the field dispensable, but the length algorithm is O(n).

 

There are five private variables of type Node:

•      head

•      tail

•      cursor

•      precursor

•      dummy

 

                            The LinkedSequence invariant
For your convenience the invariant as part of the class documentation is supplied. When you design and implement the methods, it is important that you pay attention to the invariant. 

 

1.    manyNodes is the number of nodes in the sequence; in particular the value is 0 for an empty sequence

2.    For a non-empty sequence head is the reference to the first, and tail is a reference to the last node of the sequence; for an empty sequence head and tail are null

3.    For a non-empty sequence cursor can be a reference to any of the nodes of the sequence, it cannot reference dummy. The cursor can be null; for an empty sequence cursor is null

4.    If cursor is not null, precursor is a reference to a node such that cursor is precursor.link. If cursor is null, precursor is null; in particular precursor does not reference tail

5.    dummy is a node reference and it is never null (dummy is not an element of the sequence); dummy.link is always head (null or not). If cursor is the head, then precursor is dummy 

 

                            Methods and Constructors

 

All the fields except dummy require accessor and mutator methods. 

You should instantiate dummy at the declaration with two null parameters.

 

                            Constructor
 Takes one node parameter to initialize the head. To initialize tail, head is assigned. Assigns dummy’s link the head (setLink() must be used). Note that dummy does not store any info data but null, and it is not part of the data structure. Its link is always the head, see that ADT invariant. 

                        Instance Methods
 

•      addAfter( ) Takes a parameter for the new data  value to be added to the structure and returns the currently added node. Cursor reference is always updated to the added node. A call to the addNodeAfter method of the Node class shall add the new node to the list

(i)           after dummy if head is null

(ii)         after tail if cursor is null but head is not

(iii)       after cursor if cursor is not null

 

Build the selection logic carefully and update the relevant fields as necessary

 

•      addBefore( ) Takes a parameter for the new data value to be stored in the structure and returns the currently added node. Cursor reference is always updated to the added node. A call to the addNodeAfter method of the Node class shall add the new node to the list

(i)           after dummy if precursor is null

(ii)after precursor if precursor is not null

 

•      addAll( )Takes another linked sequence for parameter (‘other’) and joins the parameter list to this list after this tail. If the parameter is null or empty, the method returns. Otherwise, if the calling list is empty (head is

null) this head assigned other head and this tail assigned other tail; else tail link assigned other head and tail assigned other tail.

 

•      advance() advances the cursor forward one step, if the cursor is not null and not the tail; precursor is updated accordingly. Null cursor is advanced to head, tail cursor advanced to null. 

 

•      start() if the sequence is empty, the method returns; otherwise assigns cursor the head and precursor the dummy

 

•      clone( ) Returns a copy of the calling sequence. See the specifications in the book. 

 

•      concatenate( ) static method; takes two linked sequence parameters and creates a third sequence by adding the second after the first. You have to use the listCopy( ) and getTail( ) static methods from Node. Do not use listCopyWithTail( ).

  

•      removeCurrent() removes the cursor if cursor is not null and returns the removed node. The new cursor is the following node if there is one, and precursor updated accordingly. If tail was removed, the new new cursor is head if there is head, if so precursor is dummy. If cursor is null, the method returns null.

 

•      displayList( ) convenience method. Prints all the nodes to the console; use the toString( ) call with respect to head for the recursive version and run a loop for the non-recursive version.

 

4. TestNode
Create three-node long list(s) of String type and test all the Node methods. This part of the Project is an extension of HW 4, you may use your code from that assignment.

5. LinkedApplications
Requirements
•      Create short (three to five long) String type linked list to test all the methods.

•      The displayList( ) method must be tested on Rectangle type list

•      Add two static fields of type long to the application class named squares and occurrences

•      Add a static void method named counting to the applications class. The method takes a Rectangle array named boxes and a Rectangle object named target for parameters.

•      The method counts the number of squares among the array element, and stores the value in the squares field, and it also counts the number of array elements that are equal to the target and stores the result in the occurrences field.

•      Step 1: Create a LinkedSequence of 100 000 Rectangle objects each having integer dimensions randomly selected between 1 and 30.

•      Step 2: Verify that the listPosition() method returns the tail reference for position number 100 000.

•      Step 3: instantiate a Rectangle array to the list length (do not use literals) and load the Rectangles from the list to the array.

•      Step 4: Create a target Rectangle with side 15, 15 and call the counting method passing your array and target as parameters.

•      Step 5: Measure the running time of each step above as well as the combined time and record the results. Hint: use the method call System.nanoTime() to record the current real time in nanoseconds (the return type of the method is long); note that 109 nanos make one second.   Step 6: Repeat Steps 1- 5 for 1 000 000 Rectangle objects  Step 7: Repeat Steps 1 – 5. 10 000 000 Rectangle objects.

•      Step 8: Repeat Step 7 by adding the non-random target rectangle of step 4 to the empty list 10 000 000 times. Check out if the random selection in step 7 is a significant overhead for the running time of the algorithm or not.

•      Analyze your running time observations, deduce Big-Oh estimates and advise about the expected time for the case of 100 000 000 rectangles. Attach your report as a comment to the source code following the application class.  

       Documentation:  Each method in Node and LinkedSequence must be fully documented (specification). You may use the assignment description itself as a help to compile the specifications.