Lab 04

Double Double Linked List

Objective:

Write a doubly linked list of type double.  This link list is similar to the singly linked list except that each node in addition to having data and a next link it now has a previous link. 

Lab Solution

Requirements:

• Functionality. (80pts)
• No Syntax, Major Run-Time, or Major Logic Errors. (80pts*)
• *Code that cannot be compiled due to syntax errors is nonfunctional code and will receive no points for this entire section.
• *Code that cannot be executed or tested due to major run-time or logic errors is nonfunctional code and will receive no points for this entire section.
• Set up the Project. (10pts)
• First download the driver file and include it in your project.
• Do not modify the driver.
• Create a class and name it, exactly, DoubleDoubleLL.
• Create Doubly Linked List Node. (10pts)
• An internal class must be used to represent a Node in the linked list.
• This node must contain both data and two links.
• One link must point forward to the next item in the list.
• The other link must point backwards to the previous item in the list.
• All the above must apply for full credit.
• Create methods gotoNext, gotoPrev, reset, gotoEnd, and hasMore. (10pts)
• The method “gotoNext” must move the current reference forward by one node. If the current reference is null, then the method does nothing.
• The method “gotoPrev” must move the current reference backwards by one node. If the current reference is null, then the method does nothing.
• The method “reset”, must move the current reference to the head reference.
• The method “gotoEnd”, must move the current reference to the last node in the list.
• The method “hasMore”, must return true if the current reference is not null or false if it is.
• All methods must have the public scope and their identifiers must match exactly what is defined above.
• Create methods getCurrent and setCurrent. (10pts)
• The method “getCurrent” must return the data at the current reference. If the current reference is null, then it must return null.
• The method “setCurrent” must modify the data at the current reference given new data. If the current reference is null, then it must do nothing.
• All methods must have the public scope and their identifiers must match exactly what is defined above.
• Create methods add and addAfterCurrent. (10pts)
• The method “add”, must create a new node with data provided via a parameter and add it to the end of the list. If the head reference is null, then it adds the new node to the start of the list.
• The method “addAfterCurrent”, must create a new node with the data provided via a parameter and add it after the current reference. If the current reference is null, then do not add the data to the list. See images below for the concept.
• All methods must have the public scope and their identifiers must match exactly what is defined above.
• After either “add” or “addAfterCurrent” the integrity of the list must be maintained, and all links and references need to be properly set.
• All the above must apply for full credit.
• Create methods remove and removeCurrent. (10pts)
• The method “remove”, must search for data provided via a parameter, and remove the node if it is found.
• The method “removeCurrent”, must remove the node that is at the current reference. If the current reference is null, then this method does nothing. See images below for the concept.
• All methods must have the public scope and their identifiers must match exactly what is defined above.
• After either “remove” or “removeCurrent” the integrity of the list must be maintained, and all links and references need to be properly set.
• All the above must apply for full credit.
• Create the method print. (10pts)
• This method must print all the data in the linked list to the console.
• The method must have the public scope and their identifiers must match exactly what is defined above.
• All the above must apply for full credit.
• Create the method contains. (10pts)
• This method returns true only if data provided via a parameter is contained in the list, and otherwise it returns false.
• The method must have the public scope and their identifiers must match exactly what is defined above.
• All the above must apply for full credit.
• Coding Style. (10pts)
• Code functionality organized within multiple methods other than the main method, and methods organized within multiple classes where appropriate. (5pts)
• Readable Code (5pts)
• Meaningful identifiers for data and methods.
• Proper indentation that clearly identifies statements within the body of a class, a method, a branching statement, a loop statement, etc.
• All the above must apply for full credit.
• Comments. (10pts)
• Your name in the file. (5pts)
• At least 5 meaningful comments in addition to your name. These must describe the function of the code it is near. (5pts)

Additional Notes:

Add Node After Current Visual Concept

Remove Current Node Visual Concept

Example Dialog:

------------------------------------------------------

Double Double Linked List Tester

------------------------------------------------------

------------------------------------------------------

Inserting and Contains Test

------------------------------------------------------

SUCCESS: true

------------------------------------------------------

Removing Test

Removing first item, third item, and last item

------------------------------------------------------

SUCCESS: true

------------------------------------------------------

Modified Values Test

Changing all even values to negative values

------------------------------------------------------

SUCCESS: true

------------------------------------------------------

Printing the list

------------------------------------------------------

1.0

3.0

-4.0

5.0

-6.0

7.0

-8.0

Print last element: -8.0

Solutions Tests:

1. Is your name written as a comment in all source files?
2. Does the solution compile (No Syntax Errors)?
3. Do all the tests work with the provided code?

a. Insert and Contains Test?

b. Delete Test?

c. Modifying Values Test?

d. Prints the correct last element?

Lab Report

1. Create a section named “Problem” and describe this lab’s problem in your own words. (10pts).
2. Create a section named “Solution Description” and describe how the code solves the problem in your own words. (10pts).
3. Create a section named “Problems Encountered” and describe the various syntax, run-time, and logic errors that were encountered while implementing the solution. (10pts).
4. If the reference to an object is lost and thus the object is now unreachable, what does the Java Virtual Machine (JVM) do with said object? (10pts).
5. Describe the advantages and disadvantages for using a Linked List instead of an Array. (10pts).
6. What are some advantages and disadvantages of using a doubly linked list versus a singly linked list? (10pts).

For Questions 07-10 you may assume the following String linked list code is provided.

7. Using the provided code and assuming the linked list already has the data “Abc”, “efG”, “HIJ”, “kLm”, “noP”, the following code snippet’s purpose is to print all the values in the String linked list. Does this method work as described and if so, what does it print to the console? If the method does not work as described, then detail all syntax, run-time, and logic errors and how they may be fixed. (10pts)

8. Using the provided code and assuming the linked list already has the data “Abc”, “efG”, “HIJ”, “kLm”, “noP”, the following code snippet’s purpose is to return the longest String in the linked list. Does this method work as described and if so, what String does this return? If the method does not work as described, then detail all syntax, run-time, and logic errors and how they may be fixed. (10pts)

9. Using the provided code and assuming the linked list already has the data “Abc”, “efG”, “HIJ”, “kLm”, “noP”, the following code snippet’s purpose is to replace all “target” Strings with another String (the parameter “rValue”). Does this method work as described and if so, if we assume the value “Abc” is given as the target, then what is the resulting linked list values? If the method does not work as described, then detail all syntax, run-time, and logic errors and how they may be fixed. (10pts)

10. Using the provided code and assuming the linked list already has the data “Abc”, “efG”, “HIJ”, “kLm”, “noP”, the following code snippet’s purpose is to remove the first five elements of the linked list. Does this method work as described and if so, what is the resulting linked list values? If the method does not work as described, then detail all syntax, run-time, and logic errors and how they may be fixed. (10pts)

Finally

Upload the Lab Solution’s source code (.JAVA file(s)) and the Lab Report’s text file to the CSCE Dropbox.