QuestionQuestion

The Assignment
For this assignment, you will create an implementation of the ArrayListADT interface (below). A 'list' is a sequence of values, which may include duplicates. The ordering of the items in the list is not specified but does matter and is in fact problem dependent. No insertion ever occurs at an arbitrary location. When an item is removed from the list, the ordering of the remaining elements in the list is unchanged. There may not be any empty or unused cells between the front and rear of the list.
Your implementation of the ArrayListADT offers a meaningful improvement over basic arrays for list-based operations. Inserting or removing an element at index [0] is a time-consuming operation for arrays. If you wish to insert an element at index [0] and the array is not empty, then you must shift all the existing elements out of the way before the insertion can occur. Similarly, if you remove the element at index [0] from a non-empty array, you must shift elements down to 'fill in the hole'. Your implementation must be able to insert or remove elements from either end of the array in constant time, with no shifting of elements necessary. A circular array strategy offers this capability. "Circular" is an abstraction; the underlying array doesn't form a circle but rather will be a standard linear array.
A solution to this problem can be found if you abandon the notion that the first element in the list must be at index [0]. Instead, you maintain a class level variables that hold the index of the 'front' and 'rear' of the list. The front and rear indices move independently, allowing insertion and deletion to happen without shifting anything.

This list (in order) is: 4, 9, 12, 7, 8, 3, 6, 10. The 'front' and 'rear' indices simply wrap around when they run off the end.
We want to segregate our data structures and separate them from any application programs. Accordingly, you must place all data structures in a package named data_structures.
Your ArrayLinearList class must implement the LinearListADT interface. Your project will consist of exactly the following two files, both of which must be in a data_structures/ package:
• • LinearListADT.java The linear list interface (provided below)
• • ArrayLinearList.java Your implementation of the interface
Both of the above files must go in package data_structures. Any driver/tester programs will go in the level above the data_structures subdirectory. Sample tester programs will be provided.
IMPORTANT: The package organization is of critical importance. If your project fails to compile during the grading process due to package errors, your grade for this project will be zero.

The LinearListADT interface:
package data_structures;
public interface LinearListADT<E> extends Iterable<E> { public static final int DEFAULT_MAX_CAPACITY = 100;

import java.util.Iterator;

import java.util.NoSuchElementException;

/* Outputs “Front: indexFront Rear: indexRear”

*/

public void ends();

/* Adds the Object obj to the beginning of list and returns true if the list is not

* full.

* returns false and aborts the insertion if the list is full.

*/

public boolean addFirst(E obj);

/* Adds the Object obj to the end of list and returns true if the list is not full.

* returns false and aborts the insertion if the list is full.

*/

public boolean addLast(E obj);
/* Removes and returns the parameter object obj in first position in list if the list
* is not empty, null if the list is empty.
*/
public E removeFirst();
/* Removes and returns the parameter object obj in last position in list if the list
* is not empty, null if the list is empty.
*/
public E removeLast();
/* Removes and returns the parameter object obj from the list if the list contains
* it, null otherwise. The ordering of the list is preserved. The list may contain
* duplicate elements. This method removes and returns the first matching element
* found when traversing the list from first position.
* Note that you may have to shift elements to fill in the slot where the deleted
* element was located.
*/
public E remove(E obj);

/* Returns the first element in the list, null if the list is empty.

* The list is not modified.

*/

public E peekFirst();

/* Returns the last element in the list, null if the list is empty.

* The list is not modified.

*/

public E peekLast();

/* Returns true if the parameter object obj is in the list, false otherwise.

* The list is not modified.

*/

public boolean contains(E obj);
/* Returns the element matching obj if it is in the list, null otherwise.

* In the case of duplicates, this method returns the element closest to front.

* The list is not modified.

*/

public E find(E obj);

/* The list is returned to an empty state.

*/

public void clear();

/* Returns true if the list is empty, otherwise false

*/

public boolean isEmpty();

/* Returns true if the list is full, otherwise false

*/

public boolean isFull();

/* Returns the number of Objects currently in the list.

*/

public int size();

/* Returns an Iterator of the values in the list, presented in

* the same order as the underlying order of the list. (front first, rear last)

*/

public Iterator<E> iterator();

}
Additional Important Details
• The ordering of the elements in the list is user defined. Thus, you must never alter the ordering of items in the list internally. For instance, a call to the method remove(E obj) will leave a 'hole' in the array if it is in the middle of the list. It would be simple to just copy the last element to the location of the removed item and decrease the size. But this would alter the order of elements. This is forbidden.
• Your ArrayLinearList class will have two constructors, one that takes a maxCapacity parameter, and one with no arguments that creates an array of DEFAULT_MAX_CAPACITY.
• Since this is an array based implementation, there is a maximum capacity which cannot be exceeded. If an insertion into a full array is attempted, then the insertion method returns false and aborts the insertion. An exception is NOT thrown in such cases.
• The ArrayLinearList.java file specified in this assignment must have the exact public names and signatures as given in the interface.
• You must not make any changes to the LinearListADT interface; I will use my copy to compile and run your program.
• You will submit only your ArrayLinearList.java file; do not submit a copy of the interface provided, nor any drivers/testers that you have written.
• You may import only classes needed for the Iterators. You may use any class in java.lang (the default package). You may not use any data structure or class in java.util other than those specified. You will need java.util.Iterator, and java.util.NoSuchElementException.
• Every class file must begin with your name and edoras class account number.
• Each method should be as efficient as possible. For example, your size() method should not loop through the array and count the elements.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

package data_structures;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayLinearList<E> implements LinearListADT<E> {

/* Points to first element of array */
int front = -1;

/* Points to last element of array */
int rear = -1;

/* Maximum size of array */
int maxSize = 0;

/* Number of objects array contains */
int arraySize = 0;

private Object[] arr;

/* Constructs an empty array with the size specified in parameter */
public ArrayLinearList(int maxCapacity) {
arr = new Object[maxCapacity];
maxSize = maxCapacity;
}

/* Constructs an empty array with the DEFAULT_MAX_CAPACITY */
public ArrayLinearList() {
arr = new Object[LinearListADT.DEFAULT_MAX_CAPACITY];
maxSize = LinearListADT.DEFAULT_MAX_CAPACITY;
}

// Method will output the front and rear position
@Override
public void ends() {
System.out.println("Front: " + front + " Rear: " + rear);
}

/*
* Add the object obj at the beginning of the array. If arraySize is 0 then set
* the front and rear to mid of array and add element, otherwise move the front
* to previous available position in circular order and add element.
*
* returns false and aborts the insertion if the list is full, otherwise return
* true if the insertion is success.
*/
@Override
public boolean addFirst(E obj) {
if (arraySize == maxSize) {
return false;
} else {
if (rear == -1 && front == -1) {
front = maxSize / 2;
rear = maxSize / 2;
} else {
front = (front - 1 + maxSize) % maxSize;
}
}
arr[front] = obj;
arraySize++;
return true;
}...

By purchasing this solution you'll be able to access the following files:
Solution.java.

50% discount

Hours
Minutes
Seconds
$50.00 $25.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats