Task: Implementation of a List interface and two concrete subclasses: ArrayList
ID: 3914475 • 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.
Your implementation has to follow the specification given.
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.
Each student submits a copy of the source code: List.java, ArrayList.java, LinkedList.java, Link.java, OutRangeException.java and Test.java.
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Make sure that you maintain proper indentations while pasting the below code into your program, I’m also attaching the code in both text and image formats, so in case if the indentation is messed up, you can refer the image and maintain proper spacing in each and every line. Thanks
EDIT: I’m getting troubles submitting the answer without losing the format. Showing character limit exceeded error. So I have to paste it as a plain text, which will cause the loss of code formatting and indentations. Sorry for the trouble. If you are using eclipse ,copy the code and press ctrl+shift+F to format the code
// ArrayList.java
public class ArrayList implements List {
// attributes
private Object items[];
private int size;
/**
* constructor with argument to set the capacity of array
*/
public ArrayList(int capacity) {
items = new Object[capacity];
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Object get(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// returning element at given index
return items[index];
}
@Override
public void set(int index, Object o) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// setting new element at given index
items[index] = o;
}
@Override
public void add(int index, Object o) throws OutRangeException {
if (index < 0 || index > size) {
throw new OutRangeException("Invalid index " + index);
}
if (size < items.length) {
/**
* shifting following elements to the right
*/
for (int i = size - 1; i >= index; i--) {
items[i + 1] = items[i];
}
/**
* Adding element at index
*/
items[index] = o;
size++;
}
}
@Override
public Object remove(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
Object item = items[index];
/**
* Shifting remaining elements to the left to occupy the vacant space
*/
for (int i = index; i < size - 1; i++) {
items[i] = items[i + 1];
}
size--;
return item;
}
@Override
public String toString() {
/**
* returns a String representation of list
*/
String data = "[";
for (int i = 0; i < size; i++) {
data += items[i];
if (i != size - 1) {
data += ",";
}
}
data += "]";
return data;
}
}
// LinkedList.java
public class LinkedList implements List {
private Link head;
private int size;
/**
* constructor to initialize the list
*/
public LinkedList() {
head = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Object get(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// getting a reference
Link reference = head;
int i = 0;
/**
* looping until the required index is found
*/
while (i < index) {
reference = reference.getNext();
i++;
}
// returning element at given index
return reference.getData();
}
@Override
public void set(int index, Object o) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
Link reference = head;
int i = 0;
while (i < index) {
reference = reference.getNext();
i++;
}
reference.setData(o);
}
@Override
public void add(int index, Object o) throws OutRangeException {
if (index < 0 || index > size) {
throw new OutRangeException("Invalid index " + index);
}
if (index == 0) {
/**
* Adding head element
*/
Link link = new Link(o);
link.setNext(head);
head = link;
size++;
} else {
Link reference = head;
int i = 0;
while (i < index - 1) {
reference = reference.getNext();
i++;
}
/**
* adding new element in the middle of current reference and next
* node (if exists)
*/
Link link = new Link(o);
link.setNext(reference.getNext());
reference.setNext(link);
size++;
}
}
@Override
public Object remove(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
if (index == 0) {
Object data = head.getData();
head = head.getNext();
size--;
return data;
}
Link reference = head;
int i = 0;
while (i < index - 1) {
reference = reference.getNext();
i++;
}
Object data = reference.getNext().getData();
/**
* making current reference point to the next of next element (if
* exists), hereby dropping the middle element
*/
reference.setNext(reference.getNext().getNext());
size--;
return data;
}
@Override
public String toString() {
String data = "[";
Link reference = head;
for (int i = 0; i < size; i++) {
data += reference.getData();
if (i != size - 1) {
data += ",";
}
reference = reference.getNext();
}
data += "]";
return data;
}
}
// Link.java
public class Link {
private Object e;
private Link next;
/**
* constructor
* @param e data
*/
public Link(Object e) {
this.e = e;
next = null;
}
//getters and setters
public Link getNext() {
return next;
}
public void setNext(Link next) {
this.next = next;
}
public Object getData() {
return e;
}
public void setData(Object e) {
this.e = e;
}
}
// OutRangeException.java
public class OutRangeException extends Exception {
/**
* Exception class handling out of range exceptions
*/
public OutRangeException(String str) {
super(str);
}
}
// Test.java
public class Test {
public static void main(String[] args) {
int SIZE = 10000;
ArrayList arrayList = new ArrayList(SIZE);
LinkedList linkedList = new LinkedList();
try {
/**
* constructing a big array list and a big linked list containing
* 10,000 elements
*/
for (int i = 0; i < SIZE; i++) {
arrayList.add(arrayList.size(), "Random Element");
linkedList.add(linkedList.size(), "Random Element");
}
/**
* recording start time and removing elements from the rear until
* the list is empty, then recording end time. Doing this for both
* lists seperately
*/
System.out.println("Testing removing operation on ArrayList");
long startTime = System.currentTimeMillis();
while (!arrayList.isEmpty()) {
arrayList.remove(arrayList.size() - 1);
}
long endTime = System.currentTimeMillis();
double arrayListTime = (endTime - startTime) / 1000.0;
System.out.println("Testing removing operation on LinkedList");
startTime = System.currentTimeMillis();
while (!linkedList.isEmpty()) {
linkedList.remove(linkedList.size() - 1);
}
endTime = System.currentTimeMillis();
double linkedListTime = (endTime - startTime) / 1000.0;
/**
* Displaying the comparison results
*/
System.out.println("Time taken for ArrayList: " + arrayListTime
+ " seconds");
System.out.println("Time taken for LinkedList: " + linkedListTime
+ " seconds");
} catch (OutRangeException e) {
e.printStackTrace();
}
}
}
// List.java
public interface List {
public int size();
public boolean isEmpty();
public Object get(int index) throws OutRangeException;
public void set(int index, Object o) throws OutRangeException;
public void add(int index, Object o) throws OutRangeException;
public Object remove(int index) throws OutRangeException;
}
/*OUTPUT*/
Time taken for ArrayList: 0.0 seconds
Time taken for LinkedList: 0.187 seconds
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.