Add the following methods to the ArrayList class that we wrote during lecture. Y
ID: 3603258 • 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
Explanation / Answer
Complete Program:
/*
* File: ListsDemo.java
*/
public class ListsDemo
{
public static void main(String[] args)
{
ArrayList<Integer> list1 = new ArrayList<Integer>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(3);
list1.add(6);
list1.add(2);
list1.add(2);
list1.add(3);
list1.add(1);
list1.add(4);
System.out.println("Array List Initially...");
System.out.println(list1);
System.out.println("Test trimToSize() method on Array List...");
list1.trimToSize();
System.out.println(list1);
System.out.println("Test slice() method on Array List...");
ArrayList<Integer> list2 = list1.slice(4, 7);
System.out.println(list2);
System.out.println("Test addAll() method on Array List...");
list1.addAll(list2);
System.out.println(list1);
LinkedList<Integer> list3 = new LinkedList<Integer>();
list3.add(44);
list3.add(88);
list3.add(22);
list3.add(66);
list3.add(33);
list3.add(11);
list3.add(99);
list3.add(77);
System.out.println("Linked List Initially...");
System.out.println(list3);
System.out.println(" Test remove() method on Linked List...");
System.out.println(list3.remove(new Integer(4)));
System.out.println(list3);
System.out.println(" Test reverse() method on Linked List...");
list3.reverse();
System.out.println(list3);
System.out.println(" Test toArrayList() method on Linked List...");
ArrayList<Integer> list4 = list3.toArrayList();
System.out.println(list4);
}
} // end of ListsDemo class
/*
* File: ArrayList.java
*/
public class ArrayList<E> implements List<E>
{
private E[] data;
private int size;
public ArrayList()
{
data = (E[]) (new Object[3]);
size = 0;
}
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();
}
}
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();
}
}
public void add(E newValue)
{
if(size == data.length)
{
E[] newData = (E[]) (new Object[data.length * 2]);
for(int i = 0; i < data.length; i++)
newData[i] = data[i];
data = newData;
}
data[size] = newValue;
size++;
}
public E remove(int index)
{
if(index >= 0 && index < size)
{
E thingToReturn = data[index];
for(int i = index; i < size - 1; i++)
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;
}
// addAll method implementation
public boolean addAll(ArrayList<E> anotherList)
{
for(int i = 0; i < anotherList.size; i++)
add(anotherList.get(i));
return true;
}
// trimToSize method implementation
public void trimToSize()
{
E[] newData = (E[]) (new Object[size]);
for(int i = 0; i < size; i++)
newData[i] = data[i];
data = newData;
}
// slice method implementation
public ArrayList<E> slice(int beginIndex, int endIndex)
{
if(beginIndex < 0 || endIndex > size || beginIndex >= endIndex)
throw new IndexOutOfBoundsException("Invalid index values.");
ArrayList<E> newList = new ArrayList<E>();
for(int i = beginIndex; i < endIndex; i++)
newList.add(data[i]);
return newList;
}
} // end of ArrayList class
/*
* File: LinkedList.java
*/
public class LinkedList<E> implements List<E>
{
private static class Node<E>
{
private E data;
private Node<E> next;
public Node(E data, Node<E> next)
{
super();
this.data = data;
this.next = next;
}
}
private Node<E> head;
private int size;
public LinkedList()
{
head = null;
size = 0;
}
public E get(int index)
{
return nodeAt(index).data;
}
public void set(int index, E newValue)
{
nodeAt(index).data = newValue;
}
public void add(E newValue)
{
if(size == 0)
head = new Node<>(newValue, null);
else
nodeAt(size - 1).next = new Node<>(newValue, null);
size++;
}
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;
}
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;
}
// remove method implementation
public E remove(E item)
{
int index = 0;
for(Node<E> temp = head; temp != null; temp = temp.next)
{
if((temp.data).equals(item))
return remove(index);
else
index++;
}
return null;
}
// reverse method implementation
public void reverse()
{
Node<E> currNode = head;
Node<E> prevNode = null;
Node<E> nextNode = null;
while (currNode != null)
{
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
}
// toArrayList method implementation
public ArrayList<E> toArrayList()
{
ArrayList<E> newList = new ArrayList<E>();
for(Node<E> temp = head; temp != null; temp = temp.next)
newList.add(temp.data);
return newList;
}
} // end of LinkedList class
/*
* File: List.java
*/
public interface List<E>
{
E get(int index);
void set(int index, E newValue);
void add(E newValue);
E remove(int index);
} // end of List interface
Sample Output:
Array List Initially...
ArrayList (size = 10, capacity = 12), containing the following:
1
2
3
3
6
2
2
3
1
4
Test trimToSize() method on Array List...
ArrayList (size = 10, capacity = 10), containing the following:
1
2
3
3
6
2
2
3
1
4
Test slice() method on Array List...
ArrayList (size = 3, capacity = 3), containing the following:
6
2
2
Test addAll() method on Array List...
ArrayList (size = 13, capacity = 20), containing the following:
1
2
3
3
6
2
2
3
1
4
6
2
2
Linked List Initially...
LinkedList (size = 8), containing: head -> 44 -> 88 -> 22 -> 66 -> 33 -> 11 -> 99 -> 77 -> null
Test remove() method on Linked List...
null
LinkedList (size = 8), containing: head -> 44 -> 88 -> 22 -> 66 -> 33 -> 11 -> 99 -> 77 -> null
Test reverse() method on Linked List...
LinkedList (size = 8), containing: head -> 77 -> 99 -> 11 -> 33 -> 66 -> 22 -> 88 -> 44 -> null
Test toArrayList() method on Linked List...
ArrayList (size = 8, capacity = 12), containing the following:
77
99
11
33
66
22
88
44
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.