Linked List Lab

Download linkedlistlab.zip, which contains all the files you will need for this assignment.

Is your code good enough to defeat the dreaded ListMonster? Download ListMonster.java to find out!

Reference

class ListNode<E>

ListNode(E value, ListNode<E> next)

E getValue()

ListNode<E> getNext()

void setValue(E value)

void setNext(ListNode<E> next)

Exercises

Compile and run the ListDisplay class (or simply construct a ListDisplay). (Do not make any changes to this code.)

Try out the top two buttons. The other buttons won't work until you complete the corresponding exercises.

Now open Lab.java. All of the code you write for this assignment will go in this file. Complete each of the following methods in any order. Be sure to consider edge cases (such as empty lists). Do not construct any more ListNode objects than necessary. Do not use any other data structures unless specifically directed to do so.

size

Returns the number of nodes in the given linked list.

contains

Returns true if and only if the given String value matches any of the elements in the linked list.

For example, the list ["apple", "banana", "cherry"] contains "banana" but does not contain "anan".

add

Adds the given String value to the end of the given linked list if it was not already in the list. Returns true if successful. Returns false if the value was already in the list.

For example, adding "cherry" to the list ["apple", "banana"] will modify the list to contain ["apple", "banana", "cherry"] and will return true.

On the other hand, adding "apple" to the list ["apple", "banana"] will not modify the list and will return false. Note that the given list will never be empty.

remove

Removes the given String value from the list if present, and returns true if successful. Returns false if the value is not in the list.

For example, removing "banana" from the list ["apple", "banana", "cherry"] will modify the list to contain ["apple", "cherry"] and will return true.

On the other hand, removing "orange" from the list ["apple", "banana", "cherry"] will not modify the list and will return false.

Note that the value you are asked to remove will never occur more than once in the list, and will never be the first value in the list.

toList

Returns a linked list containing the same String values as the given array in the same order as the given array.

For example, if the given array contains ["apple", "banana", "cherry", "banana"], then the linked list returned will also contain ["apple", "banana", "cherry", "banana"] in that order.

Hints: Decide whether which order you want to build the list: first-to-last, or last-to-first. Both ways are possible. Think about which node you need to keep track of as you attach each node, and think about what you need to return.

In case you've forgotten array syntax, the following sample code prints each value in an array.

for (int i = 0; i < a.length; i++)

System.out.println(a[i]);

Additional Credit

To earn credit for completing some or all of the following exercises, you must also write code that thoroughly tests any methods you write to demonstrate that they work correctly. For example, for the hasDuplicate method, you would also code a method called testHasDuplicate, which would take in nothing and return nothing. Inside, testHasDuplicate might print the results of calling hasDuplicate on an empty list, a one-element list [A], a two-element list with a duplicate [A, A] and without [A, B], a long list with no duplicates [A, B, C, D, E], and long lists with duplicates in various places, such as [A, B, C, D, A]  and [A, B, C, B, D]  and [A, B, C, C, D].

public static <E> boolean hasDuplicate(ListNode<E> list)

Returns true if any value appears more than once in the given list (as determined using the equals method).  Your code cannot modify the list.

public static ListNode<Integer> insert(ListNode<Integer> list, int value)

Given a list of integers that already appears in increasing order (and may contain duplicate values), this method inserts the given value into that list so that it remains in sorted order.  Returns a reference to the first node in the resulting list.  Your code should create only one new node, and cannot change the value in any existing node.  Your code cannot examine any more nodes than necessary.

Precondition:  the given list is sorted in increasing order.

public static ListNode<Integer> sort(ListNode<Integer> list)

Returns a list where all the integers in the given list appear in increasing order.

public static <E> ListNode<E> reverse(ListNode<E> list)

Reverses the order of the nodes in the given list, and returns a reference to the first node of the resulting list.  Your code cannot create any new nodes or change the value in any existing node.  Your method must loop through the nodes exactly once.

public static <E> boolean hasLoop(ListNode<E> list)

Returns true if the given linked list contains a loop. Returns false if the given linked list does not contain a loop (i.e. It's a valid linked list terminated with a null). Your code cannot create any new nodes or modify the given list in any way.