CISC Sorted Linked List

For this assignment, you will implement an acyclic, recursive, singly linked list data structure. Elements should be added directly to their sorted index in the list. Because we need to compare our data elements for this purpose, our CiscSortedLinkedList class must store data that can be compared with one another. In Java, tis means that the element type must implement the Comparable interface. Our version implements the provided "CiscList" interface, which is a subset of java.util.List.

CiscSortedLinkedList

head: Node< E >

A reference to the first node in the list (if it exists).

size : int

The size of the CiscLinkedList (the number of elements it contains).

iterator() : Iterator< E >

Creates and returns a new instance of the CiscLinkedListIterator class.

size() : int

Returns the number of elements in this list.

add(element : E) : boolean

Inserts the specified element to the its sorted position in this list and returns true. This method should call a recursive private helper method add(element : E, n : Node< E >) : void.

remove(o : Object) : boolean

Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that Objects.equals(o, get(i)) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call). This method should call a recursive private helper method remove(o : Object, n : Node< E >) : boolean. This helper method should stop searching as soon as possible.

contains(o : Object) : boolean

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that Objects.equals(o, e). You may call the indexOf method, or create a recursive private helper method contains(o: Object, n: Node< E >): boolean (in which case the helper method should stop searching as soon as possible).

isEmpty() : boolean

Returns true if the list is empty.

clear() : void

Effectively removes all of the elements from this list. The list will be empty after this call returns.

add(index : int, element : E) : void

This implementation throws an UnsupportedOperationException.

toArray() : Object[]

Returns an array containing all the elements in the list, in the same order, stored in consecutive elements of the returned array, starting with index 0. The length of the returned array is equal to size. This method should call a recursive private helper method.

toArray(arr : Object[], index : int, Node< E >) : void.

get(index : int) : E

Returns the element at the specified position in this list. Throws an IndexOutOfBoundsException if index is invalid. This method should call a recursive private helper method get(index : int, currentIndex : int, n : Node< E >) : E, where "currentIndex" is the index of the "n" parameter (e.g. currentIndex should be 0 when n points to the head).

indexOf(o : Object) : int

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that Objects.equals(o, get(i)), or -1 if there is no such index. This method should call a recursive private helper method indexOf(o : Object, currentIndex : int, n : Node< E >) : int, where "currentIndex" is the index of the "n" parameter (e.g. currentIndex should be 0 when n points to the head). This helper method should stop searching as soon as possible

remove(index : int) : E

Removes the element at the specified position in this list. Throws an IndexOutOfBoundsException if index is invalid. This method should call a recursive private helper method remove(index : int, currentIndex : int, n : Node< E >) : E, where "currentIndex" is the index of the "n" parameter (e.g. currentIndex should be 0 when n points to the head).

set(index : int, element : E) : E

This implementation throws an UnsupportedOperationException.

toString() : String

Generates and returns a string representation of the linked list by calling the toString() method on each element in the list, in order, separating each value with a comma and a space, surrounding the output in square brackets, as in: "[2, 4, 6, 7]". This method should call a recursive helper method toString(n : Node< E >) : String. The public method should handle the case when the list is empty, otherwise it should delegate to the private helper to generate the string contents involving all node values.

Node< E >

This class should be private (CiscSortedLinkedList clients don't need to create instances of it) and static (it doesn't need to access CiscSortedLinkedList internals).

data : E

An element to be stored in the list.

next : Node< E >

A reference to the next node in the list (if it exists).

Node(data : E, next : Node< E >)

Constructs a node with the provided data and next reference.

CiscLinkedListIterator

This class should be private (CiscSortedLinkedList clients don't need to create instances of it directly) and non-static (it needs to access CiscSortedLinkedList internals).

nextNode : Node< E >

A reference to the next node in the list (if it exists) containing the data to be returned by the next call to next().

nextNodeIndex : int

The index of the next node in the list (if it exists) containing the data to be returned by the next call to next().

CiscLinkedListIterator()

Constructs a CiscLinkedListIterator that can be used to iterate over the containing CiscSortedLinkedList instance. Ensures that the initial values of nextNode and nextNodeIndex are appropriate.

hasNext() : boolean

Returns true if the iterator has yet to return all data contained in the list.

next() : E

Returns the next element in the list, and updates nextNode and nextNodeIndex appropriately