Add the following methods to the ArrayList class that we wrote during lecture. Y
ID: 3607019 • Letter: A
Question
Add the following methods to the ArrayList class that we wrote during lecture. You may call the existing methods in ArrayList if you want, but do not use anything from the built-in java.util.ArrayList class.
1. (3 pts) Write a new method named addAll(ArrayList anotherList) that adds all the elements in anotherList to the back of the calling list. Be sure to reallocate the data array if necessary. anotherList should not be modified.
2. (4 pts) Write a new method named trimToSize() that changes the capacity of the calling list to the list’s current size. Example: If list1 is an ArrayList with 4 elements and a capacity of 7, calling list1.trimToSize() should change its capacity to 4.
3. (5 pts) Write a new method named slice(int beginIndex, int endIndex) that returns a new ArrayList object containing the elements of the calling list between beginIndex (inclusive) and endIndex (exclusive). The calling list should not be modified. This method should throw an IndexOutOfBoundsException if an invalid index is supplied, or if beginIndex is not at least 1 less than endIndex. Example: If list1 is an ArrayList object containing {1, 2, 3, 3, 6, 2, 2, 3, 1, 4}, then calling list1.slice(4,7) should return a new ArrayList object containing the values at indices 4, 5, and 6. The returned list would contain the elements {6, 2, 2}.
Add the following methods to the LinkedList class that we wrote during lecture (code posted on Oct. 25). You may call the existing methods in LinkedList if you want, but do not use anything from the built-in java.util.LinkedList class.
4. (3 pts) Write a new method named remove(E item) that removes and returns the first item in the list that is equivalent to the specified object. If the list does not contain such an item, the method should return null.
5. (6 pts) Write a new method named reverse() that reverses the order of the nodes in the calling list. (There are several ways you can do this, some of which are more efficient than others! As long as your solution works, it’s acceptable for this assignment. But if possible, try to make your solution run in O(n) time.)
6. (4 pts) Write a new method named toArrayList() that returns an ArrayList object containing all elements in the calling list, in the same order (i.e., the head node’s data should be stored in index 0 of the returned array list). Use your ArrayList class from the first part of this assignment. If the calling list is empty, just return an ArrayList of size 0.
#protips
As usual, be sure to test all of your methods thoroughly. When working with lists, you should always consider cases of performing an action on:
• An empty list • A list containing exactly one element • Something at the front of the list • Something at the back of the list • Something in the middle of the list
This is the Java Code I am supposed to modify
public class ArrayList<E> implements List<E> { // The type parameter E is a placeholder for what kind of data will be stored in this list
private E[] data = (E[])(new Object[3]); // The array where the data is stored -- Java doesn't allow generic array creation, so we just create an array of Objects and cast it to E[]
private int size = 0; // The number of elements actually stored in the list
// Returns the item stored at the specified list index
// Big-O: O(1)
public E get(int index) {
if (index >= 0 && index < size)
return data[index];
else {
System.out.println("You can't do that!");
throw new IndexOutOfBoundsException();
}
}
// Replaces the item at the specified list index with newValue
// Big-O: O(1)
public void set(int index, E newValue) {
if (index >= 0 && index < size)
data[index] = newValue;
else {
System.out.println("You can't do that!");
throw new IndexOutOfBoundsException();
}
}
// Adds the newValue to the end of the list
// Big-O: O(1) if an array resize is not needed
// O(n) if an array resize is needed
// If we double the array length every time a resize is needed, then this becomes "amortized constant time"
// (basically, "constant time on average")
public void add(E newValue) {
if (size == data.length) { // Array has reached its capacity
E[] newData = (E[])(new Object[data.length * 2]); // Create a new, larger array
for (int i = 0; i < data.length; i++) // Copy the old elements to the new array
newData[i] = data[i];
data = newData; // Point data at the new array
}
data[size] = newValue; // Add the newValue at the end of the array
size++;
}
// Removes and returns the list item at the specified index
// Big-O: O(n)
public E remove(int index) {
if (index >= 0 && index < size) {
E thingToReturn = data[index];
for (int i = index; i < size - 1; i++) // Shift (to the left) all array elements starting from index
data[i] = data[i+1];
size--;
return thingToReturn;
} else {
System.out.println("You can't do that!");
throw new IndexOutOfBoundsException();
}
}
public String toString() {
String r = "ArrayList (size = " + size + ", capacity = " + data.length + "), containing the following: ";
for (int i = 0; i < size; i++)
r += data[i] + " ";
return r;
}
public static void main(String[] args) {
// When we create the ArrayList object, replace E with the data type to be
// stored in the list (in this case, String)
ArrayList<Integer> theList = new ArrayList<>();
System.out.println(theList);
theList.add(-3);
System.out.println(theList);
theList.add(0);
System.out.println(theList);
theList.add(43);
System.out.println(theList);
theList.add(812903218);
System.out.println(theList);
theList.remove(1);
System.out.println(theList);
}
}
public class LinkedList<E> implements List<E> {
// Node is written as a private nested class of LinkedList, since we don't
// intend to use Node outside of this class. This way, LinkedList has
// direct access to the instance variables of Node.
private static class Node<E> { // "static" means that Node does *not* have access to the instance variables of LinkedList
private E data;
private Node<E> next;
// Constructor (generated automatically through Eclipse)
public Node(E data, Node<E> next) {
super();
this.data = data;
this.next = next;
}
}
private Node<E> head; // Maintains the location of the head node
private int size = 0; // Number of elements in the list
// Big-O: O(n) due to the call to nodeAt
@Override
public E get(int index) {
return nodeAt(index).data;
}
// Big-O: O(n) due to the call to nodeAt
@Override
public void set(int index, E newValue) {
nodeAt(index).data = newValue;
}
// Big-O: O(1) if adding to the head of the list, O(n) if adding to the tail
@Override
public void add(E newValue) {
if (size == 0)
head = new Node<>(newValue, null);
else
nodeAt(size - 1).next = new Node<>(newValue, null);
size++;
}
// Big-O: O(1) if removing from the head of the list, O(n) for other locations
@Override
public E remove(int index) {
E temp;
if (index == 0) {
temp = head.data;
head = head.next;
} else {
Node<E> nodeBefore = nodeAt(index - 1);
temp = nodeBefore.next.data;
nodeBefore.next = nodeBefore.next.next;
}
size--;
return temp;
}
// Returns the Node object at the specified index in the list.
// Throws an IndexOutOfBoundsException if the index is invalid.
// Big-O: O(n)
private Node<E> nodeAt(int index) {
if (index >= 0 && index < size) {
Node<E> temp = head;
for (int i = 0; i < index; i++)
temp = temp.next;
return temp;
} else
throw new IndexOutOfBoundsException();
}
public String toString() {
String r = "LinkedList (size = " + size + "), containing: head -> ";
for (Node<E> temp = head; temp != null; temp = temp.next)
r += temp.data + " -> ";
r += "null";
return r;
}
public static void main(String[] args) {
LinkedList<String> myList = new LinkedList<>();
System.out.println(myList);
myList.add("stuff");
myList.add("four");
myList.add("for");
myList.add("fore");
myList.add("fo");
myList.add("faux");
myList.add("4");
System.out.println(myList);
myList.remove(4);
myList.remove(0);
myList.remove(1);
System.out.println(myList);
}
}
public interface List<E> { // The type parameter E is a placeholder for what kind of data will be stored in this list
// Returns the item stored at the specified list index
E get(int index);
// Replaces the item at the specified list index with newValue
void set(int index, E newValue);
// Adds the newValue to the end of the list
void add(E newValue);
// Removes and returns the list item at the specified index
E remove(int index);
}
Please follow all the instructions given in this assignment and do not give an answer that is irrelevant to it or is incomplete.
Explanation / Answer
Hi Students;
merge following function with your current assingments and about function functanality i have added comments their so please review that.
if you are facing any problem please let me know.
i have tested code and its working fine.
/* Ratnesh Comments */
/*1)
* addAll function (ArrayList anotherList) that adds all the elements in anotherList to the back of the calling list
*/
public void addAll(List<E> anotherArrayList){
if(size==0) {
System.out.println("You can't do that!");
return;
}
for(int i=0; i<size(); i++) {
anotherArrayList.add(data[i]);
}
}
/*
* 2) we can not trim array size, either question is wrong or there is different scenario need more clarity.
*/
/*
*3) function slice(int beginIndex, int endIndex) that returns a new ArrayList object containing the elements of the calling list between beginIndex (inclusive) and endIndex (exclusive).
*/
public ArrayList<E> slice(int beginIndex, int endIndex){
ArrayList<E> newList=new ArrayList<>();
if(size==0) {
System.out.println("You can't do that!");
return null;
}
if(beginIndex >= endIndex) {
System.out.println("You can't do that!");
throw new IndexOutOfBoundsException();
}
else {
for(int i=beginIndex; i<endIndex; i++) {
newList.add(data[i]);
}
}
return newList;
}
/*
* 4) function remove(E item) that removes and returns the first item in the list that is equivalent to the specified object. If the list does not contain such an item, the method Will return null.
*/
public E removeItem(E item) {
int flag = 0,index = 0;
E thingToReturn = data[0];
if(size==0) {
System.out.println("You can't do that!");
return null;
}
for(int i = 0; i < size; i++) {
if(item == data[i]) {
flag = 1;
index = i;
break;
}
}
if(flag==1) {
for (int i = index; i < size - 1; i++) // Shift (to the left) all array elements starting from index
data[i] = data[i+1];
size--;
return thingToReturn;
}
else {
System.out.println("Item not found");
return null;
}
}
/*
* 5)Function reverse() that reverses the order of the nodes in the calling list.
*/
public void rverese()
{
int start=0,end=size;
E temp;
if(size==0) {
System.out.println("You can't do that!");
return;
}
while (start < end)
{
temp = data[start];
data[start] = data[end];
data[end] = temp;
start++;
end--;
}
}
/*
* Function toArrayList() that returns an ArrayList object containing all elements in the calling list, in the same order.
* If the calling list is empty, just return an ArrayList of size 0.
*/
public List<E> toArrayList(){
ArrayList<E> newList=new ArrayList<>();
if(size <= 0) {
return null;
}else {
for(int i=0; i<size; i++) {
newList.add(data[i]);
}
return newList;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.