代写Circular Doubly Linked Lists、代做Java程序语言、JUnit代写、代做Java

日期：2018-10-19 09:32

Project 2: Circular Doubly Linked Lists, 100 pts

Due:10/16/2018, at 11:59:59 pm

Overview

1. In Programming Assignment 2, you will implement a Circular Doubly Linked List, a List

Iterator and create JUnit tests to verify their proper operation and implementation.

2. For implementing the Circular Doubly Linked List, you will implement the List

interface and additional methods.

3. You will develop a ListIterator to traverse over the Circular Doubly Linked List.

4. You will use existing JUnit tests and also write your own JUnit tests to test your

implementation of a Circular Doubly Linked List and the List Iterator.

As you get started, please pay attention to the following:

● Please read the ENTIRE write-up before getting started.

● For this homework and all homework in CSE 12, you may not change any public

class/method or variable names given in the write-up or starter code.

● No slip days allowed

You will submit the following files for this assignment:

● MyLinkedList.java -- Provided for you as a starter file.

Where to find the starter code (You should all know how to use cp and scp command now

after we post the tutorial on Piazza)

● From ieng6 server at

○ <accountname>@ieng6.ucsd.edu:/home/linux/ieng6/cs12f/public/pa2/*

Part 1 - Understanding and Testing First

In this homework assignment you will be developing a Circular Doubly Linked List as well as an

Iterator for this list. Of course, these data structures are already supported in the Java

Collections Framework (LinkedList and ListIterator). But as we’ve mentioned in class,

implementing data structures is one of the best ways to become a better programmer and to

really understand what’s going on “under the hood”.

1. First Understand what MyLinkedList and MyListIterator will do

In order to write a good tester, you will need a deep understanding of how the classes and

methods you are testing are supposed to work. So before you start writing your tester, you

should read part 2 and part 3 in order to understand what your LinkedList and ListIterator

classes are supposed to do. You may refer to the documentation for LinkedList and

AbstractList.

2. MyLinkedListTester.java

● Download the supplied file MyLinkedListTester.java. This is a starter file the defines a

small number of tests against MyLinkedList. Observe and check how each test is written and

what it tests for.

● Feel free to add more test, as the provided starter test is not comprehensive, and your

program will later be tested against our master test.

● You should make sure to include tests to check that your method throw the correct

exceptions when they are expected to throw them. There are more sophisticated ways to do

this (feel free to investigate and use them), but simple approach is to do the following

approach (from https://github.com/junit-team/junit4/wiki/Exception-testing):

@Test

public void testExceptionMessage() {

try {

new ArrayList<Object>().get(0);

fail("Expected an IndexOutOfBoundsException to be

thrown");

} catch (IndexOutOfBoundsException anIooBException) {

assertThat(anIooBoundsException.getMessage(),

is("Index: 0, Size: 0"));

}

}

Note: If you cannot get the assertThat to work on the lab machines (or your machine) it’s

sufficient to assume that any IndexOutOfBoundsException is correct, and to simply pass in

that case (i.e. fail if you do NOT enter the catch block, and leave the catch block empty).

● After final submission, we will be running more extensive tests on your code. The

points awarded from these tests will make up your final grade.

● You must not change any method names/ method signatures provided in the starter

code.

Part 2 - Circular Doubly Linked Lists

Empty list (size = 0)

List with size 1 (one node with data 1):

List with size 2 (two node with data 1 and 2):

Once you understand what the behavior of your list and its iterator is supposed to be, your

next task is to implement a Circular Doubly Linked List called MyLinkedList and a

corresponding MyListIterator for your class.

● Download the starter file MyLinkedList.java. This MyLinkedList class will only be a subset

of the Java Collection’s Framework LinkedList and you only need to implement the methods

stubbed out in the starter code. In addition to the stubbed out methods which you will be

fully implementing yourself, make sure to also look in the source code for the string

“XXX-CHANGE-XXX”. These indicate method returns that need to be changed to reflect

proper function. The method returns have been included to allow for compilation, however

you should update them to reflect proper implementation. The methods to be implemented

are also listed in the table below. However, the behavior of each method must exactly match

that given in the LinkedList javadoc, unless specified otherwise.

● To make your life easier make sure that your class extends AbstractList, If you are not

sure where @Override tag came from, then you need to read the online documentation on

AbstractList. What happens if you do not override the add() method?

● There are various ways to implement a LinkedList - with only dummy reference, with

both dummy head and dummy tail nodes, with or without dummy nodes. You must use a

single "dummy" node in this homework. Refer to the three diagrams above to get a better

idea of how the list would look like with dummy node. Think about how having dummy node

simplifies add/remove operations in the list.

● The Java's LinkedList allows "null" objects to be inserted to the list. However, your

MyLinkedList will differ from this behavior. You should not allow “null” objects to be

inserted into the list and instead throw a NullPointerException if the user attempts to do

so.

● Your program will be graded using an automatic script. Please try your best to

implement more JUnit tests to push your circular doubly linked list to be perfect even though

we will not collect your MyLinkedListTester.java, because we sincerely promise that our

automatic script will do our worst!

● Constructors: You should only need to have a single public 0-argument constructor that

creates an empty list and initializes all the necessary variables.

● Method comments: You must provide method/class/inline comments, following the

style guideline posted on Piazza. Some methods have already been provided with these

comments for your reference.

The following are the methods of the inner class Node.

Method Name Method Description

Node (E element) Initializes the node with element

Node( E element, Node prevNode, Node

nextNode )

Initializes the node with element, prevNode

as its predecessor node and nextNode as its

successor node.

public void remove() Removes this node from the list. Links this

node’s predecessor and successor nodes.

public void setPrev( Node p ) Set p as the predecessor node.

public void setNext( Node n ) Set n as the next node

public void setElement( E e ) Set e as the node’s data

public Node getPrev() Return the node’s predecessor

public Node getNext() Return the node’s successor

public E getElement() Return the node’s data

The following are the methods of the MyLinkedList class.

Tip 1: Make sure to implement all the helper methods (like getNth(int index)) first!

Tip 2: Make sure you refer to the table below, comments in the starter code as well as the

javadoc description of the method to understand the correct behavior of the method. The

behavior of your method must exactly match its specification in order to pass the Master Tests.

PRIVATE METHODS:

Method Name Method Description Exceptions

to throw

Node getNth(int

index)

a method that returns the Node at a specified

index, not the content. The input index can be any

integer in interval [Integer.MIN_VALUE,

Integer.MAX_VALUE] due to our Linkedlist’s circular

nature.

none

This method will return dummy node when the

Linkedlist’s is empty.

E.g say you only have the dummy node (Figure 1)

dummyNode <-> (dummyNode) //it point to itself

getNth(0) -> //return dummyNode

getNth(100) -> //return dummyNode

E.g: Say you have a circular doubly linkedlist with 2

elements, node a and node b. (Figure 3)

dummyNode <-> a <-> b <-> (dummyNode)

getNth(0) -> // return node a

getNth(1) -> // return node b

getNth(2) -> //return node a (because its circular)

getNth(3) -> //return node b

getNth(-1) -> //return node b (going backwards)

Note: You might also want a removeNode(Node n) method that allows you to keep from

duplicating code in your Iterator. But you aren't required to implement one unless you want

to.

PUBLIC METHODS:

Method

Name

Method Description Exceptions to throw

boolean

add(T data)

add a node at the end into this list

Note: the boolean add method will presumably

always return true; it is a boolean function due to

the method definition in AbstractList

1. throw a

NullPointerExcep

tion if the user

tries to add a null

pointer

void

add(int

index, T

data)

add a node into this list by index. The input index

can be any integer in interval [Integer.MIN_VALUE,

Integer.MAX_VALUE] due to our linkedlist’s circular

nature.

E.g Say you have a circular doubly linkedlist with 2

nodes, node a and node b. (Figure 2)

dummy <-> a <-> (dummy)

add(0, val1) -> //dum <-> b <-> a <->(dum) , and

node b contains val1

add(2, val2) -> //dum <-> b <-> a <-> c <-> (dum),

and node c contains val2

add(-1, val3) -> //dum <-> b <-> a <-> c <-> d

<->(dum)

add(10, val4) -> //dum <-> e <-> b <-> a <-> c <-> d

<->(dum)

2. throw a

NullPointerExcep

tion if the user

tries to add a null

pointer

T get(int i) Get data within the node at position i. The input

index can be any integer in interval

[Integer.MIN_VALUE, Integer.MAX_VALUE] due to our

linkedlist’s circular nature.

Throw

IndexOutOfBoundsE

xception

If list is empty

T set(int

i,T data)

set the value at index i to data. The input index can

be any integer in interval [Integer.MIN_VALUE,

Integer.MAX_VALUE] due to our linkedlist’s circular

nature.

It returns data within the node that was previously at

this index.

1. throw

NullPointerExcep

tion if data is null

2. throw

IndexOutOfBounds

Exception If list is

empty

T

remove(int

i)

Remove the node from position i in this list. The

input index can be any integer in interval

[Integer.MIN_VALUE, Integer.MAX_VALUE] due to our

linkedlist’s circular nature.

Throw

IndexOutOfBoundsExcepti

on If list is empty

It returns the data within the removed node.

void clear() Remove all nodes from the list none

boolean

isEmpty()

Determine if the list is empty none

int size()

Return the number of nodes being stored

none

PROGRAMMING HINTS:

● You'll probably want to use a nested class (that is, a class inside a class) to represent a

node in your linked list. To accomplish this, you can't declare a Node class as public, but you

can include it in the same file (and even in the same class) as MyLinkedList. If it is contained

within MyLinkedList<T>, then it can just use the generic label T because it is within the

class. This nested node class is already present in the starter code.

public class MyLinkedList<T> extends AbstractList<T> {

class Node { // this is called a Nested Class. Only usable within MyLinkedList

T data;

Node next;

Node prev;

// more code here

}

/* Lots more code will go here */

}

Part 3 - ListIterator

Once your MyLinkedList class is working, you will need to create a ListIterator which is

returned by the listIterator() method.

The approach to create this class is to use an inner helper class (contained inside the

definition of the MyLinkedList class). This is the approach you should use to create your

ListIterator. I.e. follow what’s already in the starter code. ListIterators are relatively

complex classes.

class MyListIterator implements ListIterator<T> {

// class variables here

public boolean hasNext() {

// your code here

}

// more methods, etc.

}

The ListIterator is able to traverse the list by moving a space at a time in either direction

(make certain to write a test to verify). It might be helpful to consider that the iterator has

size+1 positions in the list: just after the sentinel head node (i.e. just before the first node

containing data), between the 0 and 1 index, ..., just before the sentinel tail node (i.e., just

after the last node containing data). After one call to next(), the iterator is logically in the

state shown below

Implementation:

● Your methods should properly throw IllegalStateException, NoSuchElementException,

and NullPointerException exceptions. This means you DO NOT HAVE TO IMPLEMENT throwing

ALL exceptions as the javadoc would indicate. Please refer to the table below.

● You may assume that the methods of the MyLinkedList and Iterator will be tested

separately. Do not use iterator methods to write MyLinkedList methods, and vice versa. I’d

like you to practice writing them.

● You may refer the ListIterator JavaDoc for details, but there are notes below.

Method Name Method Description Exceptions to throw

public

MyListIterator()

Constructor that is used to

initialize the iterator.

none

boolean

hasNext()

Return true if there are more elements

other than dummy when going in the

forward direction.

none

T next()

Return the next element in the list

when going forward, and move the

iterator forward for one node.

Throw NoSuchElementException if

there is no such element

boolean

hasPrevious()

Return true if there are more elements

other than dummy when going in the

reverse direction.

none

T previous()

Return the next element in the list

when going backward, and move the

iterator backward for one node.

Throw NoSuchElementException if

there is no such element

int nextIndex()

Return the index of the element that

would be returned by a call to next()

Return the list size if at the end of the

list

none

int

previousIndex()

Return the index of the element that

would be returned by a call to

previous()

Return -1 if at the start of the list

none

void set(T x)

Change the value in the node returned

by the most recent next/previous with

the new value.

1. Throw a

NullPointerException if x is

null.

2. Throw an

IllegalStateException if

neither next nor previous

were called

3. Throw an

IllegalStateException if add

or remove have been called

since the most recent

next/previous

void remove()

Remove the last element returned by

the most recent call to either

next/previous

1. Throw an

IllegalStateException if

neither next nor previous

were called

2. Throw an

IllegalStateException if add

or remove has been called

since the most recent

next/previous

void add(T x)

Insert the given item into the list

immediately before whatever would

have been returned by a call to next()

The new item is inserted before the

current cursor, so it would be returned

by a call to previous() immediately

following.

The value of nextIndex or

previousIndex both are increased by

one

Throw an NullPointerException if x

is null.

Programming Hints

● It is useful to have a number of state fields to simplify the writing of the various

methods above. Since the cursor of the ListIterator exists logically between 2 nodes, It is

useful to just keep references to the next Node and the previous Node.It may also be helpful

to keep an int value of the index of the next node.

● If you construct your MyLinkedList to use sentinel (or dummy) nodes as discussed in

class, and you properly throw exceptions for going out of range, you shouldn't have to worry

about checking for null values at the ends of the list since the sentinel nodes are there.

● Since set() and remove() both change based on what direction was last being traversed,

it makes sense to keep a boolean flag to indicate a forward or reverse direction.

Submission

Turning in your code

Look through your programs and make sure you've included your

name, ID and login at the top of each of them.

Files

Along with your name and cse12sxx account name at the top of each program you wrote, you

also need the appropriate comments at the top of your MyLinkedListTester.java file. We are

expecting you to hand in the following files:

● MyLinkedList.java

Important: Even if your code does not pass all the tests, you will still be able to submit your

homework to receive partial points for the tests that you passed.

How your assignment will be evaluated

● Coding Style

○ Check piazza resource on coding style guidelines

● Correctness

○ Does your code compile?

○ Does it pass all of the provided unit tests (MyLinkedListTester.java)?

○ We only provided you with 9 out of 20 tests, and you are going to make sure that you

program run correctly under all possible situations.

Turn in command

To submit your programming assignment:

under your pa2 working directory, run “turnin”, and follow the instructions prompted in console.