Task: Implementation of a List interface and two concrete subclasses: ArrayList
ID: 3917025 • Letter: T
Question
Task: Implementation of a List interface and two concrete subclasses: ArrayList and LinkedList.
The ADT of the List interface is given below: Implement the ArrayList and LinkedList classes as well as the List interface as we discussed in the lectures. Your implementation has to follow the specification given. Any other implementation (there are tons of List code on the Internet) will not receive any credit. In particular Your ArrayList class does not need to consider the array epansion case, you can always assume the initial constructed array has sufficient space. Data fields of ArrayList: Object[] items; int size; Data fields of LinkedList: Link head; int size; Link class has the following data field: Object e; Link next; Test: write a performance comparison program to compare the performance of the remove operation of the two list classes in running time. To do that, you need to construct a big ArrayList and a big LinkedList with a large number of elements in your test program, such as 10,000. In the performance comparison test, try to do the removing from the tail until the list if empty. Assume we initially have a list with 10,000 elements (in the test, you have to manually add 10,000 elements to the list though), first you remove the 10,000th element, followed by removing the 9,999th element, then 9,998th, and so on, until you have an empty list. Compare their running time by recording the timestamps before and after the operation. Demonstrate your result in your test program.
Submission:
Each student submits one copy of the source code: List.java, ArrayList.java, LinkedList.java, Link.java, OutRangeException.java and Test.java. Create a folder and name it as your Linux user account, e.g., hwang_hw5, by the following command: Copy all your source code to the above folder (clean your source code folder and remove all class files). Linux copy command is "cp filename destination_folder". Compile a README file (in text format only, do not use Microsoft, use gedit instead) and provide the following: Your name and CSUID Compiling instruction A sample test run (again in text) Existing bug (things not finished) Log in grail, go to the parent director of the folder you created, and run (suppose the your folder is "hwang") If there is no error message, your submission is successful.
Task: Implementation of a List interface and two concrete subclasses: ArrayList and LinkedList.
The ADT of the List interface is given below: Implement the ArrayList and LinkedList classes as well as the List interface as we discussed in the lectures. Your implementation has to follow the specification given. Any other implementation (there are tons of List code on the Internet) will not receive any credit. In particular Your ArrayList class does not need to consider the array epansion case, you can always assume the initial constructed array has sufficient space. Data fields of ArrayList: Object[] items; int size; Data fields of LinkedList: Link head; int size; Link class has the following data field: Object e; Link next; Test: write a performance comparison program to compare the performance of the remove operation of the two list classes in running time. To do that, you need to construct a big ArrayList and a big LinkedList with a large number of elements in your test program, such as 10,000. In the performance comparison test, try to do the removing from the tail until the list if empty. Assume we initially have a list with 10,000 elements (in the test, you have to manually add 10,000 elements to the list though), first you remove the 10,000th element, followed by removing the 9,999th element, then 9,998th, and so on, until you have an empty list. Compare their running time by recording the timestamps before and after the operation. Demonstrate your result in your test program.
Submission:
Each student submits one copy of the source code: List.java, ArrayList.java, LinkedList.java, Link.java, OutRangeException.java and Test.java. Create a folder and name it as your Linux user account, e.g., hwang_hw5, by the following command: Copy all your source code to the above folder (clean your source code folder and remove all class files). Linux copy command is "cp filename destination_folder". Compile a README file (in text format only, do not use Microsoft, use gedit instead) and provide the following: Your name and CSUID Compiling instruction A sample test run (again in text) Existing bug (things not finished) Log in grail, go to the parent director of the folder you created, and run (suppose the your folder is "hwang") If there is no error message, your submission is successful.
Explanation / Answer
/* Task: Implementation of a List interface and two concrete subclasses: ArrayList and LinkedList.*/
public class ArrayList implements List {
private Object items[];
private int size;
/**
* below is constructor
*/
public ArrayList(int cp) { // here parameter vairable cp is the capaciy of array
items = new Object[cp];
size = 0;
}
@Override
public boolean isArrayNull() { // cheking the empty
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public Object getting(int i) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
return items[i];
}
@Override
public void setting(int i, Object o) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
items[i] = o;
}
@Override
public void adding(int i, Object o) throws OutRangeException {
if (i < 0 || i > size) {
throw new OutRangeException("Invalid i " + i);
}
if (size < items.length) {
for (int i = size - 1; i >= i; i--) {
items[i + 1] = items[i];
}
items[i] = o;
size++;
}
}
@Override
public Object removing(int i) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
Object item = items[i];
for (int i = i; i < size - 1; i++) {
items[i] = items[i + 1];
}
size--;
return item;
}
@Override
public String toString() {
String data = "[";
for (int i = 0; i < size; i++) {
data += items[i];
if (i != size - 1) {
data += ",";
}
}
data += "]";
return data;
}
}
public class LinkedList implements List {
private Link h;
private int size;
public LinkedList() {
h = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isArrayNull() {
return size == 0;
}
@Override
public Object getting(int i) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
Link reference = h;
int i = 0;
while (i < i) {
reference = reference.gettingNext();
i++;
}
return reference.gettingData();
}
@Override
public void setting(int i, Object o) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
Link reference = h;
int i = 0;
while (i < i) {
reference = reference.gettingNext();
i++;
}
reference.settingData(o);
}
@Override
public void adding(int i, Object o) throws OutRangeException {
if (i < 0 || i > size) {
throw new OutRangeException("Invalid i " + i);
}
if (i == 0) {
Link link = new Link(o);
link.settingNext(h);
h = link;
size++;
} else {
Link reference = h;
int i = 0;
while (i < i - 1) {
reference = reference.gettingNext();
i++;
}
Link link = new Link(o);
link.settingNext(reference.gettingNext());
reference.settingNext(link);
size++;
}
}
@Override
public Object removing(int i) throws OutRangeException {
if (i < 0 || i >= size) {
throw new OutRangeException("Invalid i " + i);
}
if (i == 0) {
Object data = h.gettingData();
h = h.gettingNext();
size--;
return data;
}
Link reference = h;
int i = 0;
while (i < i - 1) {
reference = reference.gettingNext();
i++;
}
Object data = reference.gettingNext().gettingData();
reference.settingNext(reference.gettingNext().gettingNext());
size--;
return data;
}
@Override
public String toString() {
String data = "[";
Link reference = h;
for (int i = 0; i < size; i++) {
data += reference.gettingData();
if (i != size - 1) {
data += ",";
}
reference = reference.gettingNext();
}
data += "]";
return data;
}
}
public class Link {
private Object e;
private Link next;
public Link(Object e) {
this.e = e;
next = null;
}
public Link gettingNext() {
return next;
}
public void settingNext(Link next) {
this.next = next;
}
public Object gettingData() {
return e;
}
public void settingData(Object e) {
this.e = e;
}
}
// List.java
public interface List {
public boolean isArrayNull();
public int size();
public void adding(int i, Object o) throws OutRangeException;
public void setting(int i, Object o) throws OutRangeException;
public Object getting(int i) throws OutRangeException;
public Object removing(int i) throws OutRangeException;
}
public class CheckProgram {
public static void main(String[] args) {
int SIZE = 10000;
ArrayList arrayList = new ArrayList(SIZE);
LinkedList linkedList = new LinkedList();
try {
for (int i = 0; i < SIZE; i++) {
arrayList.adding(arrayList.size(), "Random Element");
linkedList.adding(linkedList.size(), "Random Element");
}
System.out.println("Testing remove operation on ArrayList");
long startingTime = System.currentTimeMillis();
while (!arrayList.isArrayNull()) {
arrayList.removing(arrayList.size() - 1);
}
long endingTime = System.currentTimeMillis();
double arrayListTime = (endingTime - startingTime) / 1000.0;
System.out.println("Testing removing operation on LinkedList");
startingTime = System.currentTimeMillis();
while (!linkedList.isArrayNull()) {
linkedList.removing(linkedList.size() - 1);
}
endingTime = System.currentTimeMillis();
double linkedListTime = (endingTime - startingTime) / 1000.0;
System.out.println("ArrayList Time: " + arrayListTime
+ " sec.");
System.out.println("LinkedList Time: " + linkedListTime
+ " sec.");
} catch (OutRangeException e) {
e.printStackTrace();
}
}
}
/* here is the output that we can get by compile the above program*/
ArrayList Time: 0.0 sec.
LinkedList Time: 0.187 sec.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.