For this assignment, you will implement a cyclic doubly linked list data structure. Our version implements the provided "CiscList" interface, which is a subset of java.util.List.
| CiscDoublyLinkedList< E > implements CiscList< E > |
| - head: Node< E > - size: int |
| + iterator(): Iterator< E > + size(): int + add(element: E): boolean + remove(o: Object): boolean + contains(o: Object): boolean + isEmpty(): boolean + clear(): void + toArray(): Object[] + add(index: int, element: E): void + get(index: int): E + indexOf(o: Object): int + remove(index: int): E + set(index: int, element: E): E |
| Node< E > |
| - data: E - next: Node< E > - prev: Node < E> |
| - Node(data: E, next: Node< E >, prev: Node< E >) |
| CiscDoublyLinkedListIterator implements Iterator< E > |
| - nextNode: Node< E > - nextNodeIndex: int |
| + CiscDoublyLinkedListIterator() + hasNext(): boolean + next(): E |
head: Node< E >
A reference to the first node in the list (if it exists).
size: int
The size of the CiscDoublyLinkedList (the number of elements it contains).
Iterator(): Iterator< E >
Creates and returns a new instance of the CiscDoublyLinkedListIterator class.
size(): int
Returns the number of elements in this list.
add(element: E): boolean
Appends the specified element to the end of this list and returns true.
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).
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 Object.equals(o, e).
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.
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.
add(index : int, element : E) : void
Inserts the specified element at the specified position in this list. Throws an IndexOutOfBoundsException if index is invalid.
get(index : int) : E
Returns the element at the specified position in this list. Throws an IndexOutOfBoundsException if index is invalid.
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.
remove(index : int) : E
Removes and returns the element at the specified position in this list. Throws an IndexOutOfBoundsException if index is invalid.
set(index : int, element : E) : E
Replaces the element at the specified position in this list with the specified element. Returns the element previously at the specified position in the list. Throws an IndexOutOfBoundsException if index is invalid.
This class should be private (CiscDoublyLinkedList clients don't need to create instances of it) and static (it doesn't need to access CiscDoublyLinkedList 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).
prev : Node< E >
A reference to the previous node in the list (if it exists).
Node(data : E, next : Node< E >, prev : Node< E >)
Constructs a node with the provided data, next reference, and prev reference.
This class should be private (CiscDoublyLinkedList clients don't need to create instances of it directly) and non-static (it needs to access CiscDoublyLinkedList 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().
CiscDoublyLinkedListIterator()
Constructs a CiscDoublyLinkedListIterator that can be used to iterate over the containing CiscDoublyLinkedList 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.