Java代写：CSCI1933ArrayListsvsLinkedLists

使用 ArrayList 和 LinkedList 分别实现List接口。

Instructions

Please read and understand these expectations thoroughly. Failure to follow
these instructions could negatively impact your grade. Rules detailed in the
course syllabus also apply but will not necessarily be repeated here.

• Identification: Place you and your partner’s x500 in a comment in all files you submit. For example, //Written by shino012 and hoang159.
• Submission: Submit a zip archive on Canvas containing all your java files. You are allowed to change or modify your submission, so submit early and often, and verify that all your .java files are in the submission. Failure to submit the correct files will result in a score of zero for all missing parts. Late submissions and submissions in an abnormal format (such as .rar) will be penalized. Only submissions made via Canvas are acceptable.
• Partners: You may work alone or with one partner. Failure to tell us who is your partner is indistinguishable from cheating and you will both receive a zero. Ensure all code shared with your partner is private.
• Code: You must use the EXACT class and method signatures we ask for. This is because we use a program to evaluate your code (more on this later). Code that doesn’t compile will receive a significant penalty. Code should be compatible with Java 11, which is installed on the CSE Labs computers.
• README: You must include a README.txt in your submission that contains the following information:
  • Group member’s names and x500s
  • Contributions of each partner (if applicable)
  • How to compile and run your program
  • Any assumptions
  • Additional features that your project had (if applicable)
  • Any known bugs or defects in the program
• Questions: Questions related to the project can be discussed publicly on Discord in abstract. This relates to programming in Java, understanding the writeup, and topics covered in lecture and labs. Do not post any code or solutions on any public channels. Do not e-mail the TAs your questions when they can be asked on Discord. Individual questions can be addressed on Discord via help tickets.
• Grading: Grading will be done by the TAs, so please address grading problems to them privately.
  IMPORTANT: You are only allowed to use import statements that are specified
  for this project, plus common libraries such as Math, Scanner, etc. You are
  NOT permitted to use Java’s built-in libraries for LinkedLists or ArrayLists.
  If you are unsure whether an import statement will be allowed, ask a TA!

Code Style

Part of your grade will be decided based on the “code style” demonstrated by
your programming. In general, all projects will involve a style component.
This should not be intimidating, but it is fundamentally important. The
following items represent “good” coding style:

• Use effective comments to document what important variables, functions, and sections of the code are for. In general, the TA should be able to understand your logic through the comments left in the code.
  Try to leave comments as you program, rather than adding them all in at the
  end. Comments should not feel like arbitrary busy work - they should be
  written assuming the reader is fluent in Java, yet has no idea how your
  program works or why you chose certain solutions.
• Use effective and standard indentation.
• Use descriptive names for variables. Use standard Java style for your names: ClassName, functionName, variableName for structures in your code, and ClassName.java for the file names.
  Try to avoid the following stylistic problems:
• Missing or highly redundant, useless comments. int a = 5; //Set a to be 5 is not helpful.
• Disorganized and messy files. Poor indentation of braces ({ and }).
• Incoherent variable names. Names such as m and numberOfIndicesToCount are not useful. The former is too short to be descriptive, while the latter is much too descriptive and redundant.
• Slow functions. While some algorithms are more efficient than others, functions that are aggressively inefficient could be penalized even if they are otherwise correct. In general, functions ought to terminate in under 5 seconds for any reasonable input.
  The programming exercises detailed in the following pages will both be
  evaluated for code style. This will not be strict - for example, one bad
  indent or one subjective variable name are hardly a problem. However, if your
  code seems careless or confusing, or if no significant effort was made to
  document the code, then points will be deducted.

Project Structure

Your project submission must adhere to the following rules. Failure to do so
will impact your grade.

1. Your submission should be one ZIP file named [partner1 x500]_[partner2 x500]_Project3.zip
2. The ZIP file should contain a single directory (folder) named [partner1 x500]_[partner2 x500]_Project3
3. This directory should contain only these 4 files:
   * ArrayList.java
   * LinkedList.java
   * README.txt
   * analysis.txt or analysis.pdf
   For example, the following would be a valid project structure:

• shino012_hoang159_Project3.zip
  • shino012_hoang159_Project3
    • ArrayList.java
    • LinkedList.java
    • README.txt
    • analysis.txt or analysis.pdf
      If you are working alone, just include your single x500 in the naming of the
      ZIP file and directory. If you have any questions about this structure, ask a
      TA.
      As always, make sure to include an academic honesty statement in your README.
      Failure to do so will result in a 10 point deduction.

Introduction

IMPORTANT: This project utilizes interfaces and generics. For brevity, this
write-up omits discussions of such topics. For more information, please see a
TA, review the lecture notes, or review other related literature (e.g.
official Java documentation).
In this project you will implement a list in two different ways: as an
ArrayList and as a LinkedList. You will then compare the time complexities of
a select few List methods when implemented as an ArrayList and as a
LinkedList.
The List class contains descriptions of what each List methods should do.
Following the instructions found in that interface file is just as important
as following the instructions in this write-up.

LinkedList Implementation

The first part of this project will be to implement a linked list. Create a
class LinkedList that implements all the methods in List interface (found in
List.java). Recall that to implement the List interface and use the generic
compatibility with your code, LinkedList should have following structure:
public class LinkedList<T extends Comparable> implements List {
…
}
—|—
The underlying structure of a linked list is a node. This means you will have
an instance variable that is the first node of the list. The provided
Node.java contains a generic node class that you should use for your linked
list implementation.
You may implement your linked list as a headed list, i.e., the first node in
the list is a ‘dummy’ node and the second node is the first element of the
list, or a non-headed list, i.e., the first node is the first element of the
list. Depending on how you choose to implement your list, there will be some
small nuances.
Your LinkedList class should have a single constructor:
public LinkedList() {
…
}
—|—
that initializes the list to an empty list.

Implementation Details

• In addition to the methods described in the List interface, the LinkedList class should contain a private class variable isSorted. This should be initialized to true in the constructor (because it is sorted if it has no elements) and updated when the list is sorted, more elements are added, the list is rotated, and more. For the purposes of this class, isSorted is only true if the list is sorted in ascending order. More details about isSorted can be found in the description of methods in the List interface.
• Initially and after a call to clear(), the size should be zero and your list should be empty.
• In sort(), do not use an array or ArrayList to sort the elements. You are required to sort the values using only the linked list data structure. You can move nodes or swap values but you cannot use an array to store values while sorting.
• Depending on your implementation, remember that after sorting, the former first node may not be the current first node.

Array List Implementation

The second part of this project will be to implement an array list. Create a
class ArrayList that implements all the methods in List interface. Recall that
to implement the List interface and use the generic compatibility with your
code, ArrayList should have following structure:
public class ArrayList<T extends Comparable> implements List {
…
}
—|—
The underlying structure of an array list is (obviously) an array. This means
you will have an instance variable that is an array. Since our implementation
is generic, the type of this array will be T[]. Due to Java’s implementation
of generics , you CANNOT simply create a generic array with:
T[] a = new T[size];
—|—
Rather, you have to create a Comparable (since T extends Comparable) array and
cast it to an array of type T.
T[] a = (T[]) new Comparable[size];
—|—
Your ArrayList class should have a single constructor:
public ArrayList() {
…
}
—|—
that initializes the underlying array to a length of 2.

Implementation Details

• In addition to the methods described in the List interface, the ArrayList class should contain a private class variable isSorted. This should be initialized to true in the constructor (because it is sorted if it has no elements) and updated when the list is sorted, more elements are added, the list is rotated, and more. For the purposes of this class, isSorted is only true if the list is sorted in ascending order. More details about isSorted can be found in the description of methods in the List interface.
• When the underlying array becomes full, both add methods will automatically add more space by creating a new array that is twice the length of the original array, copying over everything from the original array to the new array, and finally setting the instance variable to the new array. Hint: You may find it useful to write a separate private method that does the growing and copying
• When calling the remove method, the underlying array should no longer have that spot. For example, if the array was [“hi”, “bye”, “hello”, “okay”, …] and you called remove with index 1, the array would be [“hi”, “hello”, “okay”, …]. Basically, the only null elements of the array should be after all the data.
• Initially and after a call to clear(), the size method should return 0. The “size” refers to the number of elements in the list , NOT the length of the array. After a call to clear(), the underlying array should be reset to a length of 2 as in the constructor.

Unit Tests

As mentioned at the beginning of the project writeup we will be using a
program to evaluate your code. Specifically, we will be using JUnit (unit
tests) to test each method that you implement. You will be provided the same
tests that will be used for grading so you can verify the accuracy of the
methods you write. Along with this project write-up, a document will be
provided that discusses how to run these JUnit tests (in IntelliJ).
Read the comments in the Junit test files carefully - when a test fails, you
will see a line number associated with an assertionError that caused that test
to fail. Examine the comments associated with the failed test, as they will
indicate what specific case your method is failing, including edge cases.

Analysis

Now that you have implemented and used both an array list and linked list,
which one is better? Which methods in List are more efficient for each
implementation?
For a few of the methods (specified below) in List, compare the runtime
(Big-O) for each method and implementation. Ignore any increased efficiency
caused by the flag isSorted. Include an analysis.txt or analysis.pdf with your
submission structured as follows.
Write an analysis of the complexity of these four methods:

• add(T element) method.
• rotate(int n) method.
• merge(List otherList) method.
• reverse() method.
  Your explanation for each method only needs to be a couple sentences briefly
  justifying your runtimes.
  NOTE: As stated in the List class, the initial calls to sort this list and
  other list for the merge function should be ignored when determining the
  runtime of the method. Only consider the merging portion of that function.